數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列

數(shù)據(jù)結(jié)構(gòu)（九）——隊(duì)列

一、隊(duì)列簡(jiǎn)介

隊(duì)列是一種特殊的線性表，僅能在兩端進(jìn)行操作，隊(duì)頭可以進(jìn)行區(qū)數(shù)據(jù)操作，隊(duì)尾進(jìn)行插入數(shù)據(jù)操作。
隊(duì)列的特性是先進(jìn)先出。

隊(duì)列的操作包括創(chuàng)建隊(duì)列、銷毀隊(duì)列、入隊(duì)、出隊(duì)、清空隊(duì)列、獲取隊(duì)頭元素、獲取隊(duì)列的長(zhǎng)度。

二、隊(duì)列的實(shí)現(xiàn)

1、隊(duì)列的抽象類

 template <typename T>
  class Queue:public Object
  {
  public:
    virtual void add(const T& value) = 0;//進(jìn)隊(duì)列
    virtual void remove() = 0;//出隊(duì)列
    virtual T front()const = 0;//獲取隊(duì)頭元素
    virtual void clear() = 0;//清空隊(duì)列
    virtual int length()const = 0;//隊(duì)列長(zhǎng)度
  };

2、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)

隊(duì)列可以使用順序存儲(chǔ)結(jié)構(gòu)的內(nèi)存空間實(shí)現(xiàn)，其內(nèi)存空間分布如下：

根據(jù)存儲(chǔ)空間的分配方式可以分為使用原生數(shù)組實(shí)現(xiàn)的靜態(tài)隊(duì)列和使用動(dòng)態(tài)分配的堆空間實(shí)現(xiàn)的動(dòng)態(tài)隊(duì)列。
靜態(tài)隊(duì)列的實(shí)現(xiàn)要點(diǎn)如下：
A、類模板實(shí)現(xiàn)
B、使用原生數(shù)組作為隊(duì)列的存儲(chǔ)空間
C、使用模板參數(shù)決定隊(duì)列的容量大小
靜態(tài)隊(duì)列的實(shí)現(xiàn)如下：

template <typename T, int N>
  class StaticQueue:public Queue<T>
  {
  protected:
    T m_space[N];//隊(duì)列存儲(chǔ)空間，N為模板參數(shù)
    int m_front;//隊(duì)頭標(biāo)識(shí)
    int m_rear;//隊(duì)尾標(biāo)識(shí)
    int m_length;//隊(duì)列長(zhǎng)度
  public:
    StaticQueue()
    {
      m_front = 0;
      m_rear = 0;
      m_length = 0;
    }

    int capacity()const
    {
      return N;
    }

    void add(const T &value)//入隊(duì)
    {
      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()//出隊(duì)
    {
      if(m_length > 0)
      {
          m_front = (m_front + 1) % N;
          m_length--;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }

    T front() const//取隊(duì)頭元素
    {
      if(m_length > 0)
      {
          return m_space[m_front];
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No element...");
      }
    }
   void clear()//清空隊(duì)列
   {
     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);
   }
  };

靜態(tài)隊(duì)列的缺陷：
當(dāng)存儲(chǔ)的元素類型為類類型時(shí)，創(chuàng)建靜態(tài)隊(duì)列時(shí)會(huì)多次調(diào)用元素類型的類構(gòu)造函數(shù)，影響效率。

3、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)

隊(duì)列使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的內(nèi)容空間分布如下：

鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)要點(diǎn)：
A、類模板實(shí)現(xiàn)，繼承自抽象父類Queue
B、內(nèi)部使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)元素的存儲(chǔ)
C、只在鏈表的頭部和尾部進(jìn)行操作
鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)：

 template <typename T>
  class LinkedQueue:public Queue<T>
  {
  protected:
    LinkedList<T> m_list;
  public:
    LinkedQueue()
    {
    }
    void add(const T& value)//入隊(duì)
    {
      m_list.insert(value);
    }

    void remove()//出隊(duì)
    {
      if(m_list.length() > 0)
         m_list.remove(0);
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No enough memory...");
      }
    }
    T front()const//獲取隊(duì)頭元素
    {
      if(m_list.length() > 0)
         return m_list.get(0);
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No elemnet...");
      }
    }

    void clear()//清空隊(duì)列
    {
      m_list.clear();
    }

    int length() const
    {
      return m_list.length();
    }
  };

三、棧和隊(duì)列的相互實(shí)現(xiàn)

1、棧實(shí)現(xiàn)隊(duì)列

用棧實(shí)現(xiàn)隊(duì)列，用棧的后進(jìn)先出的特性實(shí)現(xiàn)隊(duì)列的先進(jìn)先出的特性。
用棧實(shí)現(xiàn)隊(duì)列需要使用兩個(gè)棧，解決方案如下：

新元素入隊(duì)時(shí)，將元素壓入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)//入隊(duì)
  {
    m_stack_in.push(value);
  }
  void remove()//出隊(duì)
  {
    //出棧為空，則將入棧的所有元素壓入出棧并彈出入棧的元素
    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、隊(duì)列實(shí)現(xiàn)棧

用隊(duì)列實(shí)現(xiàn)棧，用隊(duì)列的先進(jìn)先出的特性實(shí)現(xiàn)棧的后進(jìn)先出的特性。
用隊(duì)列實(shí)現(xiàn)棧需要使用兩個(gè)隊(duì)列，解決方案如下：

template <typename T>
class QueueToStack:public Stack<T>
{
protected:
  LinkedQueue<T> m_queue1;
  LinkedQueue<T> m_queue2;
  LinkedQueue<T>* m_pIn;//入隊(duì)列
  LinkedQueue<T>* m_pOut;//出隊(duì)列
  //將入隊(duì)列前n-1個(gè)元素移動(dòng)到出隊(duì)列
  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();//從入隊(duì)列出隊(duì)
    }
  }
  //交換
  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);//將元素入隊(duì)列
  }
  void pop()//出棧
  {
    if(m_pIn->length() > 0)
    {
        move();//移動(dòng)前n-1個(gè)元素
        m_pIn->remove();//將入隊(duì)列的最后一個(gè)元素出隊(duì)
        swap();//交換
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  void clear()
  {
    m_queue1.clear();
    m_queue2.clear();
  }

  T top() const
  {
    if(m_pIn->length() > 0)
    {
        move();//移動(dòng)
        return m_pIn->front();
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "No element...");
    }
  }

  int size()const
  {
    return m_queue1.length() + m_queue2.length();
  }
};