数据结构与算法-队列
队列的操作原理是先进先出，后进后出；队列也是一种运算受限的线性表，从队列的头部出列，从队列的尾部入列。
队列基本用法：
empty():如果队列为空返回true，否则返回false
size():返回队列中元素的个数
pop():删除队列首元素但不返回其值
front():返回队首元素的值，但不删除该元素
push(x) :在队尾压入新元素 ，x为要压入的元素
back() :返回队列尾元素的值，但不删除该元素
用数组实现的队列叫做顺序队列
template<class T>class MyArrayQueue {public:MyArrayQueue();~MyArrayQueue();bool empty() const;int size() const;void pop();T front() const;T back() const;void push(T const&);protected:int nHead;int nTail;int nQueueSize;int* pQueue;private:};template<class T>MyArrayQueue<T>::MyArrayQueue() {nHead = 0;nTail = 0;nQueueSize = 2;pQueue = new T[nQueueSize];}template<class T>MyArrayQueue<T>::~MyArrayQueue() {delete[] pQueue;}template<class T>bool MyArrayQueue<T>::empty() const {if(nHead == nTail) {return true;}return false;}template<class T>int MyArrayQueue<T>::size() const {return (nTail - nHead);}template<class T>void MyArrayQueue<T>::pop() {if(nHead == nTail) return ;if((nQueueSize / 2) > (nTail - nHead)) {nQueueSize = nQueueSize / 2;T* pTmpArray = new T[nQueueSize];memcpy(pTmpArray, pQueue+nHead, (nTail - nHead) * sizeof(T));delete[] pQueue;pQueue = pTmpArray;nTail = nTail - nHead;nHead = 0;}nHead++;}template<class T>T MyArrayQueue<T>::front() const {return pQueue[nHead];}template<class T>T MyArrayQueue<T>::back() const {return pQueue[nTail-1];}template<class T>void MyArrayQueue<T>::push(T const& param) {if(nTail == (nQueueSize - 1)) {if(nHead == 0) nQueueSize = nQueueSize * 2;T* pTmpArray = new T[nQueueSize];memcpy(pTmpArray, pQueue+nHead, (nTail - nHead) * sizeof(T));delete[] pQueue;pQueue = pTmpArray;nTail = nTail - nHead;nHead = 0;}pQueue[nTail] = param;}
用链表实现的队列叫做链式队列
template<class T>struct Node {T nNum;Node<T>* pNext;Node() {pNext = NULL;}};template<class T>class MyListQueue {public:MyListQueue();~MyListQueue();bool empty() const;int size() const;void pop();T front() const;T back() const;void push(T const&);protected:Node<T>* pHead;Node<T>* pTail;private:};template<class T>MyListQueue<T>::MyListQueue() {pHead = NULL;pTail = NULL;}template<class T>MyListQueue<T>::~MyListQueue() {while(pHead != NULL) {Node<T> *pTmp = pHead->pNext;delete pHead;pHead = pTmp;}pTail = NULL;pHead = NULL;}template<class T>bool MyListQueue<T>::empty() const {if(pHead == NULL) return true;return false;}template<class T>int MyListQueue<T>::size() const {Node<T>* pTmp = pHead;int nSize = 0;while(pTmp != NULL) {pTmp = pTmp->pNext;nSize++;}return nSize;}template<class T>void MyListQueue<T>::pop() {if(pHead == NULL) return ;Node<T>* pTmp = pHead->pNext;delete[] pHead;pHead = pTmp;}template<class T>T MyListQueue<T>::front() const{if(pHead == NULL) return NULL;return pHead->nNum;}template<class T>T MyListQueue<T>::back() const{if(pTail == NULL) return NULL;return pTail->nNum;}template<class T>void MyListQueue<T>::push(T const& param) {Node<T>* pTmp = new Node<T>;pTmp->nNum = param;pTmp->pNext = NULL;if(pHead == NULL) {pHead = pTmp;pTail = pTmp;}else {pTail->pNext = pTmp;pTail = pTmp;}}
可关注公众号了解更多的面试技巧