数据结构与算法-队列

原创 Yew 程序员的面试题

2019年10月11日 08:53

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

队列基本用法：

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

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

继续滑动看下一个