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

​栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊在于栈和队列的基本操作是线性表操作的子集，他们是操作受限的线性表。但是从数据类型角度看，他们是和线性表大不相同的抽象数据类型。

与栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素，跟我们平时排队是一个道理。

队列也有两种存储表示方法：顺序存储和链式存储，顺序存储常见的就是环形队列，初始化时必须指定队列容量大小；普通队列基于链表。

以下是对队列抽象数据类的基本实现：

CQueue.hpp

1、环形队列 基于数组 初始化时必须指定队列容量大小

#include 
   
    #include "assert.h"using namespace std;​template
    
     class CircularQueue{private:  T *m_pQueue; //指向环形队列数据的指针  int m_iHead; //游标  int m_iLenth; //队列实际长度  int m_iCapacity; //队列容量大小public:  CircularQueue(int capacity); //构造函数，指定队列容量大小，初始化队列​  ~CircularQueue(); //析构函数​  bool empty();//队列判空​  bool full(); //判断是否满队列​  int size(); //获取队列实际长度​  int capacity();//获取队列容量大小​  bool push(T t);//入队​  bool pop(T &t);//出对​  void traverse();};​template
     
      CircularQueue
      
       ::CircularQueue(int capacity) :  m_iCapacity(capacity),   m_iLenth(0),   m_iHead(0){  m_pQueue = new T[m_iCapacity];}​template
       
        CircularQueue
        
         ::~CircularQueue() { delete m_pQueue; m_pQueue = nullptr;}​template
         
          bool CircularQueue
          
           ::empty() { return 0 == m_iLenth; }​template
           
            bool CircularQueue
            
             ::full(){ return m_iLenth == m_iCapacity;}​template
             
              int CircularQueue
              
               ::size() { return m_iLenth; }​template
               
                int CircularQueue
                
                 ::capacity(){ return m_iCapacity; }​template
                 
                  bool CircularQueue
                  
                   ::push(T t){ if (full()) { std::cout << "队列已满，插入失败：" << t << endl; return false; }​ m_pQueue[m_iHead] = t; m_iHead++; m_iHead %= m_iCapacity; m_iLenth++; return true;}​template
                   
                    bool CircularQueue
                    
                     ::pop(T &t){ if (empty()) { std::cout << "队列为空。" << endl; return false; }​ t = m_pQueue[m_iHead]; m_iHead++; m_iHead %= m_iCapacity; m_iLenth--; return true;}template
                     
                      void CircularQueue
                      
                       ::traverse(){ for (int i = m_iHead; i < m_iHead + m_iLenth; i++) std::cout << m_pQueue[i%m_iCapacity] << " ";​ std::cout << std::endl; std::cout <<"m_iHead: " << m_iHead << std::endl;}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

2、普通队列实现，基于链表

#include 
   
    #include "assert.h"using namespace std;​template
    
     class CQueueNode{public:  T data;  CQueueNode *next;public:  CQueueNode(T t) :data(t), next(NULL) {}  ~CQueueNode() { next = NULL; }  CQueueNode(const CQueueNode& node)  {    if (this == &node)    {      return;    }    *this = node;  }  CQueueNode& operator=(const CQueueNode& node)  {    if (this == &node)    {      return *this;    }​    this->data = node.data;    this->next = node.next;    return *this;  }};​//普通队列实现 基于链表template
     
      class CQueue{private:  CQueueNode
      
       * head;  CQueueNode
       
        * tail;  CQueueNode
        
         * node; int m_iSize;public: CQueue() :head(NULL), tail(NULL), node(NULL), m_iSize(0) {}​ ~CQueue() { delete head; delete tail; delete node;​ head = NULL; tail = NULL; node = NULL; }​ int size(); bool empty(); void push(T t); T pop(); T front(); T back(); void traverse();​};​template
         
          int CQueue
          
           ::size(){ return m_iSize;}​template
           
            bool CQueue
            
             ::empty(){ return 0 == m_iSize;}​template
             
              void CQueue
              
               ::push(T t){ node = new CQueueNode
               
                (t); if (head == NULL) { head = tail = node; } else { tail->next = node; tail = node; } m_iSize++;}​template
                
                 T CQueue
                 
                  ::pop(){ if (empty()) { throw "empty queue."; }​ node = head; head = head->next; m_iSize--;​ return node->data;}​template
                  
                   T CQueue
                   
                    ::front(){ if (empty()) { throw "empty queue."; }​ return head->data;}​template
                    
                     T CQueue
                     
                      ::back(){ if (empty()) { throw "empty queue."; }​ return tail->data;}​template
                      
                       void CQueue
                       
                        ::traverse(){ CQueueNode
                        
                          *node = head; while (node != NULL) { cout << node->data << " "; node = node->next; }​ std::cout << endl;}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

main.cpp

int main(int argc, char**argv){  cout << "***环形队列***" << endl;  CircularQueue
   
     cq(5);  cq.push(2);  cq.push(3);  cq.push(5);  cq.push(14);  cq.push(15);  cq.traverse();  cq.push(36);  cq.traverse();  int val = -1;  cq.pop(val);  cout << "出栈元素：" << val << endl;  cq.traverse();  val = 36;  cq.push(val);  cout << "入栈元素：" << val << endl;  cq.traverse();  cout << endl;    cout << "***普通队列***" << endl;  CQueue
    
      queue;  queue.push('I');  queue.push('t');  queue.push(' ');  queue.push('C');  queue.push('o');  queue.push('n');  queue.push('t');  queue.push('a');  queue.push('i');  queue.push('n');  queue.push('e');  queue.push('r');  queue.traverse();  cout << queue.front() << endl;  cout << queue.back() << endl;  char c = queue.pop();  cout << c << endl;  queue.traverse();  system("pause");  return 0;}
    
   

执行结果：

--|END|--

转载地址：http://ieiii.baihongyu.com/