STL中的栈和队列是基于deque实现的，本质是在stack/queue类内存在一个deque对象，让后stack/queue的成员方法调用下deque的个别接口，就自定义出来了栈和队列。因此这个实现我算在前一章的chain中就做了，本文就基于数组来实现下栈和队列。

对于stack，只能对栈顶进行push和pop操作，算是最简单的。因此，我们可以把栈类的定义如下：

1 template
     
       2 class MyStacked{ 3     protected: 4         T* elements; 5         int size; 6         int capacity; 7     public: 8         MyStacked(int cap) : capacity(cap), size(0){elements = new T[cap];} 9         ~MyStacked() { if(!elements) delete[] elements;}10         void push(const T& x);11         T  pop();12         T& top();13         bool isEmpty() const {
   return size == 0;}14         int length() const { return size;}15         void show(std::ostream& os) const;16 };
     

可以看出，数据成员只要三个就行：elements用于new个数组存放数据，size表示大小，capacity表示栈的容量。

对于各个成员函数的实现，也是相对简单的， 主要就是看下show函数及<<的重载。对于要重载模板类的<<操作符，我推荐的做法是在类中定义一个接口，然后用一个全局的重载<<函数调用该接口就行。这样就能够避免很多问题，可以参见博文：http://www.cnblogs.com/xkfz007/articles/2534322.html 该作者是转载的，这里谢谢原作者。

template
     
      void MyStacked
      
       ::show(std::ostream& os) const{    for(int i=0; i
       
        std::ostream& operator<< (std::ostream& os, MyStacked
        
          s){    s.show(os);    return os;}template
         
          void MyStacked
          
           ::push(const T& x){ assert(size < capacity); elements[size++] = x;}template
           
            T MyStacked
            
             ::pop(){ assert(size>0); return elements[--size];}template
             
              T& MyStacked
              
               ::top(){ return elements[size-1];}
              
             
            
           
          
         
        
       
      
     

---

现在讲下队列的实现

我们这里使用的是循环队列，采用数组形式表示。在编程过程中，总结了几个小技巧，个人感觉能让代码长度精简下。

首先，我们明白，队列的操作是有入队和出对，是FIFO操作，因此需要维持head和tail两个域保存当前head和tail。 这里采用的是[)表示，因此tail是入队的位置。

第二，在频繁出入操作中，必然会导致tail越过队列容量大小，重新跑到下标为0的位置，head也是同理。这里，就可以使用%运算，就可以从容操作++操作而不担心越界。

第三，一直++肯定不行，这是一个隐含的bug, 要是越过了类型最大值，那将导致不可预料的错误。因此，需要再适当的时候重新将范围定到[0,capacity)内。重新规整范围会导致tail==capacity时进行规整，导致tail=0， 而后进行访问队尾元素时，输出的不是tail-1位置上的东西，而是capacity-1位置上的东西；因此我们要在tail>capacity时进行规整。而访问的索引也全都%capacity，这样就能保证一次循环就能遍历所有元素。

第四， 空条件的判定。 做好就是包含一个size成员，判断它是不是等于0就行

代码如下：

1 template
     
       2 class MyQueue{ 3     public: 4         T* elements; 5         int head; 6         int tail; 7         int size; 8         int capacity; 9     public:10         MyQueue(int cap): capacity(cap),head(0),tail(0),size(0){elements = new T[cap];}11         ~MyQueue(){
   if (!elements) delete[] elements;}12         bool isEmpty() const {
   return size==0;}13         int length() const {
   return size;}14         void enqueue(const T& x);15         T dequeque();16         T& first();17         T& last();18         void show(std::ostream& os) const;19 };20 21 template
      
       22 void MyQueue
       
        ::enqueue (const T& x)23 {24     assert(size
        
          capacity)28         tail%=capacity;29 }30 template
         
          31 T MyQueue
          
           ::dequeque ()32 {33 assert(size>0);34 int tmp = elements[(head++)%capacity];35 head%=capacity;36 --size;37 return tmp;38 }39 template
           
            40 T& MyQueue
            
             ::first()41 {42 assert(!isEmpty());43 return elements[head%capacity];44 }45 template
             
              46 T& MyQueue
              
               ::last()47 {48 assert(!isEmpty());49 return elements[(tail-1)%capacity];50 }51 template 
               
                52 void MyQueue
                
                 ::show(std::ostream& os) const53 {54 for(int i=0; i
                 
                  59 std::ostream& operator<< (std::ostream& os, MyQueue
                  
                    q)60 {61 q.show(os);62 return os;63 }
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

测试代码：

#include 
     
      #include "mystackedandqueue.h"using namespace std;int main(){    MyStacked
      
        s(4);    s.push(2);    s.push(3);    cout << "top is " << s.top() << endl;    cout << "length is " << s.length () << endl;    cout << "top is " << s.top() << endl;    cout << "length is " << s.length () << endl;    s.pop();    cout << "length is " << s.length () << endl;    cout << s << endl;    MyQueue
       
         q(3);    cout << " empty? "<< q.isEmpty () << endl;    cout << q.length() << endl;    q.enqueue (1);    q.enqueue (2);    q.dequeque ();    q.enqueue (3);    q.dequeque();    q.dequeque ();    q.enqueue(7);    q.enqueue(8);    q.enqueue (5);    cout << "first " << q.first() << endl;    cout << "last " << q.last() << endl;    cout << q << endl;}
       
      
     

总结： 成员数据域中最好有个size成员表示大小，这样能节省很多时间。另外，适当地方添加assert,能够保证代码更加健壮，当然，更好的办法是用exception， 这样更像C++。