C++数据结构--队列
一.什么是队列
队列（Queue）是一种遵循先进先出（FIFO, First In First Out）原则的数据结构。队列通常有两种实现方式：顺序队列，环形队列与链式队列，各有优劣。但同时从底层来看队列并不是一种新的数据结构，环形队列的底层依靠数组，链式栈的底层依靠链表。（注意C++中的容器适配器queue，底层默认是deque（双向队列）是一个顺序队列，但是我们也可以将其设置成一个链式栈）
二.环形队列及其代码实现
原理：基于固定大小的数组实现，通过维护两个指针/索引，front（队头），和rear（队尾），核心思想：通过取模运算（%），使得当rear加到·队尾时，通过取模运算，能够将其回到队内存开始的地方存储，由此实现了类似于环的结构：rear = (rear + 1) % cap（cap是数组的容量），front = (front + 1) % cap，实际上的实现过程中，为了区分队空与满，我们需要空出一个存储空间，当front == rear，表示队空，(rear + 1) % 容量 == front表示队满;
优点：极高的空间利用率，操作效率极高，内存友好且稳定
缺点：容量固定，无法动态扩展，存在少量空间浪费
代码实现：如下图：
class Queue//环形队列 { public: Queue(int cap = 10) :m_cap(cap) ,m_front(0) ,m_rear(0) ,m_size(0) { pQue = new int[cap]; } ~Queue() { delete[]pQue; pQue = nullptr; } public: void push(int val)//入队 { if ((m_rear + 1) % m_cap == m_front) { expend(2 * m_rear); } pQue[m_rear] = val; m_rear = (m_rear + 1) % m_cap; m_size++; } void pop()//出队 { if (m_rear == m_front) throw "Queue is empty"; m_front = (m_front + 1) % m_cap; m_size--; } int front() const//获取队头元素 { if (m_rear == m_front) throw "Queue is empty"; return pQue[m_front]; } int back() const//获取队尾元素 { if (m_rear == m_front) throw "Queue is empty"; return pQue[(m_rear-1+m_cap)%m_cap]; } bool empty() const//判断是否为空 { return m_front == m_rear; } int size() const//获取元素个数 { return m_size; } void show()const//打印 { int p = m_front; while (p != m_rear) { cout << pQue[p] << " "; p = (p + 1) % m_cap; } cout << endl; } private: void expend(int val)//扩容 { int p = m_front; int* q = new int(val); int i = 0; while (p != m_rear) { q[i] = pQue[p]; p = (p + 1) % m_cap; i++; } delete[] pQue; pQue = q; m_cap = val; m_front = 0; m_rear = i; } private: int* pQue; int m_cap; int m_front; int m_rear; int m_size; };三.链式栈及其代码实现
原理：基于双向循环链表实现，需要定义一个头节点，入队操作相于当尾插，出队操作相当于头删。
优点：操作效率极高，动态扩容，支持双向遍历
缺点：空间开销大，缓存友好性差
代码实现：如下图：
class LinkQueue { public: LinkQueue() { head = new Node(); head->next = head; head->pre = head; } ~LinkQueue() { Node* p = head->next; while (p!=head ) { head->next = p->next; p->next->pre = head; delete p; p = head->next; } delete head; head = nullptr; } public: void push(int val)//入队 { Node* node = new Node(val); Node* p = head->pre; p->next = node; node->pre = p; node->next = head; head->pre = node; m_size++; } void pop()//出队 { if (head->next == head) throw "Queue is empty"; Node* p = head->next; head->next = head->next->next; delete p; head->next->next->pre = head; m_size--; } int front() const//获取队头元素 { if (head->next == head) throw "Queue is empty"; return head->next->data; } int back() const//获取队尾元素 { if (head->next == head) throw "Queue is empty"; return head->pre->data; } bool empty() const//判断队列是否为空 { return head->next == head; } void show()const//打印 { Node* p = head->next; while (p->next != head) { cout << p->data << " "; p = p->next; } cout << endl; } int size() const//获取队列元素个数 { return m_size; } private: struct Node { Node(int val=0) :data(val) ,next(nullptr) ,pre(nullptr) { } int data; Node* next; Node* pre; }; Node* head; int m_size; };四.典型问题
1. 用队列实现栈
class MyStack { public: MyStack() { } void push(int x) { q1.push(x); while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } queue<int> q3; q2=q1; q1=q3; } int pop() { int val=q2.front(); q2.pop(); return val; } int top() { return q2.front(); } bool empty() { return q2.empty(); } private: queue<int> q1; queue<int> q2; };2.用栈实现队列
class MyQueue { public: MyQueue() { } void push(int x) { s1.push(x); } int pop() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } int val=s2.top(); s2.pop(); return val; } int peek() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } return s2.top(); } bool empty() { return s1.empty()&&s2.empty(); } private: stack<int> s1; stack<int> s2; };