数据结构与算法-队列

队列的操作原理是先进先出，后进后出；队列也是一种运算受限的线性表，从队列的头部出列，从队列的尾部入列。

队列基本用法：

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;}}

可关注公众号了解更多的面试技巧

如果觉得《数据结构与算法-队列》对你有帮助，请点赞、收藏，并留下你的观点哦！