数据结构（三）队列

• 队列--c++实现
• • 队列的原型（链表描述）
  • LinkQueue类的实现

在LinkQueue.h文件中直接定义了结构体node，声明了LinkQueue类。

templatestruct node{
    T data;
    node* next;
};
template
class LinkedQueue {
private:
    node *front;
    node *last;
    int size;
public:
    LinkedQueue();                             
    ~LinkedQueue();
    int getSize() const;                    //返回队列的长度
    bool isEmpty() const;                   //判断队列是否为空
    T& getFront() const;                    //返回队列头部元素引用
    T& getLast() const;                     //返回队列尾部元素引用
    void push(const T& element );           //压入队列尾部
    void pop();                             //删除队列头部元素
};

#include "LinkedQueue.h"
template
LinkedQueue::LinkedQueue() {
    front = new node;
    front->next = nullptr;
    last = front;
    size = 0;
}

template
LinkedQueue::~LinkedQueue() {
    while (size != 0) {
        node *p = front->next;
        delete front;
        front = p;
        size--;
    }
}

template
bool LinkedQueue::isEmpty() const {                 //判断队列是否为空
    return size == 0;
}

template
int LinkedQueue::getSize() const {                 //返回队列的长度
    return size;
}

template
T &LinkedQueue::getFront() const {                 //返回队列头部元素引用
    return front->data;
}

template
T &LinkedQueue::getLast() const {                 //返回队列尾部元素引用
    return last->data;
}

template
void LinkedQueue::push(const T &element) {         //压入队列尾部
    if(size == 0){
        front->data = element;
    }else{
    node *p = new node;
    p->next = nullptr;
    p->data = element;
    last->next = p;
    last = p;
    }
    size++;
}

template
void LinkedQueue::pop() {                          //删除队列头部元素
    node *p = front->next;
    delete front;
    front = p;
    size--;
}

测试程序如下：

#include 
int main(){
    LinkedQueue linkedQueue;
    for (int i = 0; i < 10; ++i) {
        linkedQueue.push(i);
    }
    std::cout << "size = " << linkedQueue.getSize() << std::endl;
    std::cout << "the queue's head is " << linkedQueue.getFront() << std::endl;
    std::cout << "the queue's last is " << linkedQueue.getLast() << std::endl;
    linkedQueue.pop();
    std::cout << "now, size = " << linkedQueue.getSize() << std::endl;
    std::cout << "the queue's head is " << linkedQueue.getFront() << std::endl;
    std::cout << "the queue's last is " << linkedQueue.getLast() << std::endl;
    return 0;
}

测试结果如图：