数据结构与算法:队列

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

队列基本用法:

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;

}

}

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

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章