程序員面試題精選100題(18)-用兩個棧實現隊列[數據結構]

時間:2019-09-22 編輯:范文亭
題目:某隊列的聲明如下:
template<typename T> class CQueue
{
public:
      CQueue() {}
      ~CQueue() {}

      void appendTail(const T& node);  // append a element to tail
      void deleteHead();               // remove a element from head 

private:
     T> m_stack1;
     T> m_stack2;
};
 
分析:從上面的類的聲明中,我們發現在隊列中有兩個棧。因此這道題實質上是要求我們用兩個棧來實現一個隊列。相信大家對棧和隊列的基本性質都非常了解了:棧是一種后入先出的數據容器,因此對隊列進行的插入和刪除操作都是在棧頂上進行;隊列是一種先入先出的數據容器,我們總是把新元素插入到隊列的尾部,而從隊列的頭部刪除元素。
我們通過一個具體的例子來分析往該隊列插入和刪除元素的過程。首先插入一個元素a,不妨把先它插入到m_stack1。這個時候m_stack1中的元素有{a},m_stack2為空。再插入兩個元素b和c,還是插入到m_stack1中,此時m_stack1中的元素有{a,b,c},m_stack2中仍然是空的。
這個時候我們試著從隊列中刪除一個元素。按照隊列先入先出的規則,由于a比b、c先插入到隊列中,這次被刪除的元素應該是a。元素a存儲在m_stack1中,但并不在棧頂上,因此不能直接進行刪除。注意到m_stack2我們還一直沒有使用過,現在是讓m_stack2起作用的時候了。如果我們把m_stack1中的元素逐個pop出來并push進入m_stack2,元素在m_stack2中的順序正好和原來在m_stack1中的順序相反。因此經過兩次pop和push之后,m_stack1為空,而m_stack2中的元素是{c,b,a}。這個時候就可以pop出m_stack2的棧頂a了。pop之后的m_stack1為空,而m_stack2的元素為{c,b},其中b在棧頂。
這個時候如果我們還想繼續刪除應該怎么辦呢?在剩下的兩個元素中b和c,b比c先進入隊列,因此b應該先刪除。而此時b恰好又在棧頂上,因此可以直接pop出去。這次pop之后,m_stack1中仍然為空,而m_stack2為{c}。
從上面的分析我們可以總結出刪除一個元素的步驟:當m_stack2中不為空時,在m_stack2中的棧頂元素是最先進入隊列的元素,可以pop出去。如果m_stack2為空時,我們把m_stack1中的元素逐個pop出來并push進入m_stack2。由于先進入隊列的元素被壓到m_stack1的底端,經過pop和push之后就處于m_stack2的頂端了,又可以直接pop出去。
接下來我們再插入一個元素d。我們是不是還可以把它push進m_stack1?這樣會不會有問題呢?我們說不會有問題。因為在刪除元素的時候,如果m_stack2中不為空,處于m_stack2中的棧頂元素是最先進入隊列的,可以直接pop;如果m_stack2為空,我們把m_stack1中的元素pop出來并push進入m_stack2。由于m_stack2中元素的順序和m_stack1相反,最先進入隊列的元素還是處于m_stack2的棧頂,仍然可以直接pop。不會出現任何矛盾。
我們用一個表來總結一下前面的例子執行的步驟:
操作 m_stack1 m_stack2
append a {a} {}
append b {a,b} {}
append c {a,b,c} {}
delete head {} {b,c}
delete head {} {c}
append d {d} {c}
delete head {d} {}
 
總結完push和pop對應的過程之后,我們可以開始動手寫代碼了。參考代碼如下:
///////////////////////////////////////////////////////////////////////
// Append a element at the tail of the queue
///////////////////////////////////////////////////////////////////////
template<typename T> void CQueue<T>::appendTail(const T& element)
{
      // push the new element into m_stack1
      m_stack1.push(element);

///////////////////////////////////////////////////////////////////////
// Delete the head from the queue
///////////////////////////////////////////////////////////////////////
template<typename T> void CQueue<T>::deleteHead()
{
      // if m_stack2 is empty, and there are some
      // elements in m_stack1, push them in m_stack2
      if(m_stack2.size() <= 0)
      {
            while(m_stack1.size() > 0)
            {
                  T& data = m_stack1.top();
                  m_stack1.pop();
                  m_stack2.push(data);
            }
      }

      // push the element into m_stack2
      assert(m_stack2.size() > 0);
      m_stack2.pop();
}
擴展:這道題是用兩個棧實現一個隊列。反過來能不能用兩個隊列實現一個棧?如果可以,該如何實現?
本文已影響
相關文章
大亨pk10计划苹果版