数据结构与算法-队列

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

队列基本用法：

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

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