数据结构（九）——队列

一、队列简介

队列是一种特殊的线性表，仅能在两端进行操作，队头可以进行区数据操作，队尾进行插入数据操作。

队列的特性是先进先出。队列的操作包括创建队列、销毁队列、入队、出队、清空队列、获取队头元素、获取队列的长度。

二、队列的实现

1、队列的抽象类

template 
    
       class Queue:public Object  {  public:    virtual void add(const T& value) = 0;//进队列    virtual void remove() = 0;//出队列    virtual T front()const = 0;//获取队头元素    virtual void clear() = 0;//清空队列    virtual int length()const = 0;//队列长度  };
    

2、队列的顺序存储结构实现

队列可以使用顺序存储结构的内存空间实现，其内存空间分布如下：

根据存储空间的分配方式可以分为使用原生数组实现的静态队列和使用动态分配的堆空间实现的动态队列。静态队列的实现要点如下：A、类模板实现B、使用原生数组作为队列的存储空间C、使用模板参数决定队列的容量大小静态队列的实现如下：

template 
    
       class StaticQueue:public Queue
     
        {  protected:    T m_space[N];//队列存储空间，N为模板参数    int m_front;//队头标识    int m_rear;//队尾标识    int m_length;//队列长度  public:    StaticQueue()    {      m_front = 0;      m_rear = 0;      m_length = 0;    }    int capacity()const    {      return N;    }    void add(const T &value)//入队    {      if(m_length < N)      {          m_space[m_rear] = value;          m_rear = (m_rear + 1) % N;          m_length++;      }      else      {          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");      }    }    void remove()//出队    {      if(m_length > 0)      {          m_front = (m_front + 1) % N;          m_length--;      }      else      {          THROW_EXCEPTION(InvalidOperationException, "No element...");      }    }    T front() const//取队头元素    {      if(m_length > 0)      {          return m_space[m_front];      }      else      {          THROW_EXCEPTION(InvalidOperationException, "No element...");      }    }   void clear()//清空队列   {     m_length = 0;     m_front = 0;     m_rear = 0;   }   int length() const   {     return m_length;   }   bool isEmpty()const   {     return (m_length == 0) && (m_front == m_rear);   }   bool isFull()const   {     return (m_length == N) && (m_front == m_rear);   }  };
     
    

静态队列的缺陷：

当存储的元素类型为类类型时，创建静态队列时会多次调用元素类型的类构造函数，影响效率。

3、队列的链式存储结构实现

队列使用链式存储结构实现的内容空间分布如下：

链式队列的实现要点：A、类模板实现，继承自抽象父类QueueB、内部使用链式结构实现元素的存储C、只在链表的头部和尾部进行操作链式队列的实现：

template 
    
       class LinkedQueue:public Queue
     
        {  protected:    LinkedList
      
        m_list;  public:    LinkedQueue()    {    }    void add(const T& value)//入队    {      m_list.insert(value);    }    void remove()//出队    {      if(m_list.length() > 0)         m_list.remove(0);      else      {          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");      }    }    T front()const//获取队头元素    {      if(m_list.length() > 0)         return m_list.get(0);      else      {          THROW_EXCEPTION(InvalidOperationException, "No elemnet...");      }    }    void clear()//清空队列    {      m_list.clear();    }    int length() const    {      return m_list.length();    }  };
      
     
    

三、栈和队列的相互实现

1、栈实现队列

用栈实现队列，用栈的后进先出的特性实现队列的先进先出的特性。

用栈实现队列需要使用两个栈，解决方案如下：新元素入队时，将元素压入stack_in栈，

template 
    
     class StackToQueue:public Queue
     
      {protected:  mutable LinkedStack
      
        m_stack_in;  mutable LinkedStack
       
         m_stack_out;public:  void add(const T& value)//入队  {    m_stack_in.push(value);  }  void remove()//出队  {    //出栈为空，则将入栈的所有元素压入出栈并弹出入栈的元素    if(m_stack_out.size() == 0)    {        while(m_stack_in.size() > 0)        {            m_stack_out.push(m_stack_in.top());            m_stack_in.pop();//弹出入栈的元素        }    }    //出栈不为空，将出栈栈顶元素弹出    if(m_stack_out.size() > 0)    {        m_stack_out.pop();    }    else    {        THROW_EXCEPTION(InvalidOperationException, "No element...");    }  }  T front() const  {    if(m_stack_out.size() == 0)    {        while(m_stack_in.size() > 0)        {            m_stack_out.push(m_stack_in.top());            m_stack_in.pop();        }    }    //弹出出栈栈顶元素    if(m_stack_out.size() > 0)    {        return m_stack_out.top();    }    else    {        THROW_EXCEPTION(InvalidOperationException, "No element...");    }  }  void clear()  {     m_stack_in.clear();     m_stack_out.clear();  }  int length()const  {     return m_stack_in.size() + m_stack_out.size();  }};
       
      
     
    

2、队列实现栈

用队列实现栈，用队列的先进先出的特性实现栈的后进先出的特性。

用队列实现栈需要使用两个队列，解决方案如下：

template 
    
     class QueueToStack:public Stack
     
      {protected:  LinkedQueue
      
        m_queue1;  LinkedQueue
       
         m_queue2;  LinkedQueue
        
         * m_pIn;//入队列  LinkedQueue
         
          * m_pOut;//出队列 //将入队列前n-1个元素移动到出队列 void move()const { int n = m_pIn->length() - 1; for(int i = 0; i < n; i++) { m_pOut->add(m_pIn->front()); m_pIn->remove();//从入队列出队 } } //交换 void swap() { LinkedQueue
          
           * temp = NULL; temp = m_pIn; m_pIn = m_pOut; m_pOut = temp; }public: QueueToStack() { m_pIn = &m_queue1; m_pOut = &m_queue2; } //压栈 void push(const T& value) { m_pIn->add(value);//将元素入队列 } void pop()//出栈 { if(m_pIn->length() > 0) { move();//移动前n-1个元素 m_pIn->remove();//将入队列的最后一个元素出队 swap();//交换 } else { THROW_EXCEPTION(InvalidOperationException, "No element..."); } } void clear() { m_queue1.clear(); m_queue2.clear(); } T top() const { if(m_pIn->length() > 0) { move();//移动 return m_pIn->front(); } else { THROW_EXCEPTION(InvalidOperationException, "No element..."); } } int size()const { return m_queue1.length() + m_queue2.length(); }};