C++实现有哨兵的双向循环链表：
#include<iostream> #include<stack> using namespace std; template<class T> class Node { private: T data; Node<T>* next; public: Node() { Node=NULL; } Node(T d) { data=d; next=NULL; } }; template<class T> class myqueue { private: Node<T> *tail; public: myqueue() { tail=new Node<T>(); //tail->next=NULL; tail->next=tail; //这种表示采用的是循环队列，且队列头是一个哨兵为空，它的下一个才是队列的第一个数据 } bool empty() { //return (NULL==tail->next) return (tail->next==tail); } void push(T d) { Node<T> *p=new Node<T>(d); //p->next=NULL; p->next=tail->next; tail->next=p; tail=p; //始终标记出尾部的位置 } T front() //取队列的第一个元素 { if(empty()) { cout<<"queue is empty!"<<endl; exit(0); } Node<T> *p=tail->next; //这是一个循环链表构成的队列，尾部的链接的下一个就是队列头 T data=p->next->data; //队列头链接的下一个才是第一个数据 return data; } void pop() //队列的第一个元素出队列 { Node<T> *p=tail->next; Node<T> *q=p->next; p->next=q->next; if(q==tail) tail=p; delete q; q=NULL; } }; |
