本文共 3712 字，大约阅读时间需要 12 分钟。

何为队列？

队列(Queue)也是一种线性存储结构，它具有如下特点：

队列中的数据元素遵守“先进先出”(First In First Out)的原则，简称FIFO结构。在队尾添加元素，在对首删除元素。

队列的相关概念与操作

1.对头与队尾：允许元素插入的一端称为队尾，允许删除元素的一端称为对首。

栈是一种线性结构，能以数组或链表作为底层数据结构来实现。

基于数组的队列实现

以数组做为底层数据结构时，一般将队列实现为循环队列。这是因为：1.如果采用顺序存储，每次从数组头部删除元素后，其后的元素都要依次往前移一个位置，时间复杂度为O(n);2.对于上述问题，有人提议将对首标志往后移就不用移动元素了，可是这回造成空间的浪费。所以为了实现队列的插入删除都是O(1)的时间复杂度，同时不造成空间的流失，我们采用循环队列。何为循环队列？即把数组看成一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。

如上图所示，我们以begin和end分别代表队首和队尾标志，end后面还有一个空位但是我们不存储元素，那么如何判断队满或者队空呢？1.当begin==end时，表示队空。2.当(end+1)%maxsize==begin时，表示队满。

/*队列的抽象数据类型*/template 
   
    class ArrayQueue{public:    //构造函数    ArrayQueue(int s): maxsize(s),begin(0),end(0),array(NULL) {        array = new T[maxsize];    }    //析构函数    ~ArrayQueue()    {        delete []array;    }    T front();          //对首元素    bool pop();         //出对    bool push(T t);     //入队    bool isEmpty();     //判空    int size();         //队列的大小private:    int begin;      //对首元素    int end;        //对尾    T *array;       //数组    int maxsize;    //容量};
   

具体实现

template 
   
    T ArrayQueue
    
     ::front(){    if(begin != end)        return array[begin];};template 
     
      bool ArrayQueue
      
       ::pop(){    if(begin == end)        return false;    begin = (begin+1)%maxsize;    return true;};template 
       
        bool ArrayQueue
        
         ::push(T t){ if((end+1)%maxsize == begin) return false; array[end] = t; end = (end+1) % maxsize; return true;};template 
         
          bool ArrayQueue
          
           ::isEmpty(){ if(begin == end) return true; else return false;};template 
           
            int ArrayQueue
            
             ::size(){ return (end - begin + maxsize) % maxsize;};
            
           
          
         
        
       
      
     
    
   

主函数

int main(){    ArrayQueue
   
     queue(6);    queue.push("one");    queue.push("two");    queue.push("three");    queue.push("four");    queue.push("five");    cout << "队列长度：" << queue.size() << endl;    while(!queue.isEmpty())    {        cout << queue.front() << endl;        queue.pop();    }    return 0;}
   

输出结果：

基于链表的栈实现

基于链表的队列不存在上述问题，我们只需考虑哪头做队首，哪头做队尾。如下图所示，很清晰直观，不再啰嗦。

链表结点

/*链表结点，即队列中的元素*/template 
   
    struct Node{    Node(T t):value(t),next(NULL) {}    Node() = default;public:    T value;        //队列中元素的值    Node
    
     * next;  //链表节点指针};
    
   

队列的抽象数据类型

/*基于链表的队列的ADT*/template 
   
    class LinkQueue{public:    LinkQueue(): phead(NULL),pend(NULL),count(0){        phead = new Node
    
     ();        pend = phead;        count = 0;    }    T front();          //对首元素    bool pop();         //出对    bool push(T t);     //入队    bool isEmpty();     //判空    int size();         //队列的大小private:    Node
     
      * phead;    Node
      
       * pend;    int count;    //队列元素的数量};
      
     
    
   

具体实现

template 
   
    T LinkQueue
    
     ::front(){    if(count != 0)        return phead->next->value;};template 
     
      bool LinkQueue
      
       ::pop(){    if(count == 0)        return false;    Node
       
        * pdel = phead-> next;    phead -> next = pdel -> next;    delete pdel;    count--;    return true;};template 
        
         bool LinkQueue
         
          ::push(T t){ Node
          
           * pnode = new Node
           
            (t); pend -> next = pnode; pend = pnode; count++; return true;};template 
            
             bool LinkQueue
             
              ::isEmpty(){ if(count == 0) return true; else return false;};template 
              
               int LinkQueue
               
                ::size(){ return count;};
               
              
             
            
           
          
         
        
       
      
     
    
   

主函数实例

int main(){    LinkQueue
   
     lqueue;    lqueue.push("one");    lqueue.push("two");    lqueue.push("three");    lqueue.push("four");    lqueue.push("five");    cout << "队列长度：" << lqueue.size() << endl;    while(!lqueue.isEmpty())    {        cout << lqueue.front() << endl;        lqueue.pop();    }    return 0;}
   

输出结果：

　　用C++模板实现基于数组和链表的队列，和上节实现栈相似，希望对大家有所帮助。