C++用数组和链表分别实现Queue
昨天写了《》，今天就是《》，
队列就是先来的先被处理掉，后来的就等，直到成为先来的，实现起来感觉和栈差不多。
模板好用的，功能强大，有些东东还是写成模板的好，废话昨天都说了，今天是不想说的，
博客园的哥们说我的博客不符合推荐到首页的要求，只好加几句废话。
链表版 template < typename T,typename container > class queue { public : bool empty() const { return len == 0 ;} void checkEmpty(){ if (empty()){ throw new exception( " 队列中没有数据 " );} }T & back(){ checkEmpty(); return cur -> val;} const T & back() const { return back();} void pop(){ checkEmpty(); if (head -> next == cur){ delete head -> next;head -> next = NULL;} else { node * tmp = head -> next;head -> next = tmp -> next;delete tmp;} -- len;}T & front(){ checkEmpty(); return head -> next -> val; } const T & front() const { return front();} void push( const T & val){ node * tmp = new node(val); cur -> next = tmp; cur = tmp; ++ len; }queue(){ initialize();} explicit queue( const container & cont){ initialize();vector < int > ::const_iterator iter = cont.begin(); while (iter != cont.end()){ push( * iter ++ );}} ~ queue(){ node * tmp; while (tmp != NULL){ tmp = head;head = head -> next;delete tmp;tmp = NULL;}delete cur;} int size(){ return len;} protected :typedef struct node1{ node1 * next;T val;node1(T v):val(v),next(NULL){} }node; private : int len; node * head; node * cur; void initialize(){ head = new node( - 1 );cur = head;len = 0 ;} };
数组版 template < typename T,typename container > class queue{ public : bool empty() const { return head == rail;} void checkEmpty(){ if (empty()){ throw new exception( " 队列中没有数据 " );} } // 队尾元素 T & back(){ checkEmpty(); return arr[rail - 1 ];} const T & back() const { return back();} // 出队 void pop(){ checkEmpty();arr[head ++ ] = 0 ;} // 队头元素 T & front(){ checkEmpty(); return arr[head];} const T & front() const { return front();} // 入队 void push( const T & val){ if (rail >= capacity){ capacity = (rail - head) * 2 ;T * tmp = new T[capacity]; int j = 0 ; for ( int i = head;i < rail;i ++ ){ tmp[j ++ ] = arr[i];}delete arr;arr = tmp;rail = rail - head;head = 0 ;}arr[rail ++ ] = val;}queue(){ initialize( 4 );}queue( int capacity){ initialize(capacity);} explicit queue( const container & cont){ initialize(cont.size());vector < int > ::const_iterator iter = cont.begin(); while (iter != cont.end()){ push( * iter ++ );}} ~ queue(){ delete arr;} // 队列中元素个数 int size(){ return rail - head;} protected :typedef struct node1{ node1 * next;T val;node1(T v):val(v),next(NULL){} }node; private : int capacity; int head; // 对头元素的位置 int rail; // 对尾元素的位置 int * arr; void initialize( int cap){ capacity = cap;arr = new int [capacity];head = rail = 0 ;}};
作者：