數據結構（九）——隊列

數據結構（九）——隊列

一、隊列簡介

隊列是一種特殊的線性表，僅能在兩端進行操作，隊頭可以進行區數據操作，隊尾進行插入數據操作。
隊列的特性是先進先出。

隊列的操作包括創建隊列、銷毀隊列、入隊、出隊、清空隊列、獲取隊頭元素、獲取隊列的長度。

二、隊列的實現

1、隊列的抽象類

 template <typename T>
  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 <typename T, int N>
  class StaticQueue:public Queue<T>
  {
  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、類模板實現，繼承自抽象父類Queue
B、內部使用鏈式結構實現元素的存儲
C、只在鏈表的頭部和尾部進行操作
鏈式隊列的實現：

 template <typename T>
  class LinkedQueue:public Queue<T>
  {
  protected:
    LinkedList<T> 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 <typename T>
class StackToQueue:public Queue<T>
{
protected:
  mutable LinkedStack<T> m_stack_in;
  mutable LinkedStack<T> 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 <typename T>
class QueueToStack:public Stack<T>
{
protected:
  LinkedQueue<T> m_queue1;
  LinkedQueue<T> m_queue2;
  LinkedQueue<T>* m_pIn;//入隊列
  LinkedQueue<T>* 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<T>* 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();
  }
};