数据结构之队列：队列的实现

马谦马谦马谦

615
文章

17
评论

2018 年 3 月 25 日 12:49:05数据结构和算法评论170字数 271阅读 0 分 54 秒阅读模式

队列是一种先进先出的数据结构，因和平常生活中的排队流程一样因此被称为队列。操作逻辑和栈刚好相反。

常用操作：

enqueue: 元素入队
dequeue: 首元素出队
size: 返回队列中元素的个数
empty: 判断队列是否为空
front: 返回队首元素

它有两个指针分别指向队列开头和结尾，出队和入队的流程为：

队列的实现方式多样，也可以和栈一样通过数组、 vector 等方式实现，这里就采用最常用的链式节点实现。

一、队列节点

typedef unsigned int uint;

template <typename T>
class CQueueNode {
public:
    CQueueNode();
    CQueueNode(T data, CQueueNode<T>* next = 0);
    ~CQueueNode();
    T getData() const;
    CQueueNode<T>* getNext() const;
    void setData(T data);
    void setNext(CQueueNode<T>* next);
private:
    T data;
    CQueueNode<T>* next;
};

template <typename T>
CQueueNode<T>::CQueueNode() {
    next = 0;
}

template <typename T>
CQueueNode<T>::CQueueNode(T data, CQueueNode<T>* next) : data(data), next(next) {
}

template <typename T>
CQueueNode<T>::~CQueueNode() {
    // 如果需要删除节点时把后面的所有节点都删除可以添加下面语句
    //if (next) delete next;
    next = 0;
}

template <typename T>
T CQueueNode<T>::getData() const {
    return data;
}

template <typename T>
CQueueNode<T>* CQueueNode<T>::getNext() const {
    return next;
}

template <typename T>
void CQueueNode<T>::setData(T data) {
    this->data = data;
}

template <typename T>
void CQueueNode<T>::setNext(CQueueNode<T>* next) {
    this->next = next;
}

typedef unsigned int uint;

template <typename T>

class CQueueNode {

public:

CQueueNode();

CQueueNode(T data, CQueueNode<T>* next = 0);

~CQueueNode();

T getData() const;

CQueueNode<T>* getNext() const;

void setData(T data);

void setNext(CQueueNode<T>* next);

private:

T data;

CQueueNode<T>* next;

};

template <typename T>

CQueueNode<T>::CQueueNode() {

next = 0;

}

template <typename T>

CQueueNode<T>::CQueueNode(T data, CQueueNode<T>* next) : data(data), next(next) {

}

template <typename T>

CQueueNode<T>::~CQueueNode() {

// 如果需要删除节点时把后面的所有节点都删除可以添加下面语句

//if (next) delete next;

next = 0;

}

template <typename T>

T CQueueNode<T>::getData() const {

return data;

}

template <typename T>

CQueueNode<T>* CQueueNode<T>::getNext() const {

return next;

}

template <typename T>

void CQueueNode<T>::setData(T data) {

this->data = data;

}

template <typename T>

void CQueueNode<T>::setNext(CQueueNode<T>* next) {

this->next = next;

}

二、队列

#include "node.h"

template <typename T>
class CQueue {
public:
    CQueue();
    ~CQueue();
    T enqueue(const T data);
    T dequeue();
    uint size() const;
    bool empty() const;
    T front() const;
private:
    CQueueNode<T> *head, *tail;
    uint len;
};

template <typename T>
CQueue<T>::CQueue() : len(0), tail(0), head(0) {
}

// 入队操作
template <typename T>
T CQueue<T>::enqueue(const T data) {
    CQueueNode<T>* temp = new CQueueNode<T>(data);

    // 判断队列是否为空
    if (!tail)  head = tail = temp;
    else {
        tail->setNext(temp);
        tail = temp;
    }

    len++;
    return temp->getData();
}

// 析构函数
template <typename T>
CQueue<T>::~CQueue() {
    CQueueNode<T>* p = head, *q;
    // 删除所有的节点
    while (p) {
        q = p->getNext();
        delete p;
        p = q;
    }

    head = 0, tail = 0, len = 0;
}

// 出队操作
// 出队时，应先通过 empty() 判断队列是否为空然后再操作
template <typename T>
T CQueue<T>::dequeue() {
    // 实际不应有这一句，应该主动避免该问题
    // 因为当 T 是 string 时且 head==0 时，程序会崩溃
    if (!head) return 0;
    T data = head->getData();
    CQueueNode<T>* dNode = head;

    if (head == tail) 
        // 只有一个元素
        head = tail = 0;
    else // 有多个元素
        head = dNode->getNext();

    delete dNode;
    len--;
    return data;
}

template <typename T>
uint CQueue<T>::size() const {
    return len;
}

template <typename T>
bool CQueue<T>::empty() const {
    return len == 0;
}

// 返回第一个元素
template <typename T>
T CQueue<T>::front() const {
    // 和出队操作一样，此处应该主观避免 head 为空的情况
    return head ? head->getData() : 0;
}

#include "node.h"

template <typename T>

class CQueue {

public:

CQueue();

~CQueue();

T enqueue(const T data);

T dequeue();

uint size() const;

bool empty() const;

T front() const;

private:

CQueueNode<T> *head, *tail;

uint len;

};

template <typename T>

CQueue<T>::CQueue() : len(0), tail(0), head(0) {

}

// 入队操作

template <typename T>

T CQueue<T>::enqueue(const T data) {

CQueueNode<T>* temp = new CQueueNode<T>(data);

// 判断队列是否为空

if (!tail) head = tail = temp;

else {

tail->setNext(temp);

tail = temp;

}

len++;

return temp->getData();

}

// 析构函数

template <typename T>

CQueue<T>::~CQueue() {

CQueueNode<T>* p = head, *q;

// 删除所有的节点

while (p) {

q = p->getNext();

delete p;

p = q;

}

head = 0, tail = 0, len = 0;

}

// 出队操作

// 出队时，应先通过 empty() 判断队列是否为空然后再操作

template <typename T>

T CQueue<T>::dequeue() {

// 实际不应有这一句，应该主动避免该问题

// 因为当 T 是 string 时且 head==0 时，程序会崩溃

if (!head) return 0;

T data = head->getData();

CQueueNode<T>* dNode = head;

if (head == tail)

// 只有一个元素

head = tail = 0;

else // 有多个元素

head = dNode->getNext();

delete dNode;

len--;

return data;

}

template <typename T>

uint CQueue<T>::size() const {

return len;

}

template <typename T>

bool CQueue<T>::empty() const {

return len == 0;

}

// 返回第一个元素

template <typename T>

T CQueue<T>::front() const {

// 和出队操作一样，此处应该主观避免 head 为空的情况

return head ? head->getData() : 0;

}

数据结构之队列：队列的实现

一、队列节点

二、队列

二叉树的中序遍历

112-路径总和

数据结构之 B 树

《剑指 offer 》面试题 8：二叉树的下一个节点

POJ1220-NUMBER BASE CONVERSION（任意进制转换）

[leetcode]199-二叉树的右视图

【每日打卡】 [leetcode]72-编辑距离

【每日打卡】 [leetcode]460-LFU 缓存

[leetcode]125-验证回文串

【每日打卡】 [程序员面试宝典]17.16-按摩师

【每日打卡】 [leetcode]876-链表的中间节点

【每日打卡】 [剑指 offer] 面试题 40-最小的 k 个数

【每日打卡】 [leetcode]-409 最长回文子串

【每日打卡】 [leetcode] 面试题 1.6-字符串压缩

加载中...

发表评论

热门搜索

一、队列节点

二、队列

发表评论