程序員面試題精選100題(24)-棧的push、pop序列[數據結構]

時間:2019-09-22 編輯:范文亭
題目:輸入兩個整數序列。其中一個序列表示棧的push順序,判斷另一個序列有沒有可能是對應的pop順序。為了簡單起見,我們假設push序列的任意兩個整數都是不相等的。 比如輸入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一個pop系列。因為可以有如下的push和pop序列:push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,這樣得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
分析:這到題除了考查對棧這一基本數據結構的理解,還能考查我們的分析能力。
這道題的一個很直觀的想法就是建立一個輔助棧,每次push的時候就把一個整數push進入這個輔助棧,同樣需要pop的時候就把該棧的棧頂整數pop出來。
我們以前面的序列4、5、3、2、1為例。第一個希望被pop出來的數字是4,因此4需要先push到棧里面。由于push的順序已經由push序列確定了,也就是在把4 push進棧之前,數字1,2,3都需要push到棧里面。此時棧里的包含4個數字,分別是1,2,3,4,其中4位于棧頂。把4 pop出棧后,剩下三個數字1,2,3。接下來希望被pop的是5,由于仍然不是棧頂數字,我們接著在push序列中4以后的數字中尋找。找到數字5后再一次push進棧,這個時候5就是位于棧頂,可以被pop出來。接下來希望被pop的三個數字是3,2,1。每次操作前都位于棧頂,直接pop即可。
再來看序列4、3、5、1、2。pop數字4的情況和前面一樣。把4 pop出來之后,3位于棧頂,直接pop。接下來希望pop的數字是5,由于5不是棧頂數字,我們到push序列中沒有被push進棧的數字中去搜索該數字,幸運的時候能夠找到5,于是把5 push進入棧。此時pop 5之后,棧內包含兩個數字1、2,其中2位于棧頂。這個時候希望pop的數字是1,由于不是棧頂數字,我們需要到push序列中還沒有被push進棧的數字中去搜索該數字。但此時push序列中所有數字都已被push進入棧,因此該序列不可能是一個pop序列。
也就是說,如果我們希望pop的數字正好是棧頂數字,直接pop出棧即可;如果希望pop的數字目前不在棧頂,我們就到push序列中還沒有被push到棧里的數字中去搜索這個數字,并把在它之前的所有數字都push進棧。如果所有的數字都被push進棧仍然沒有找到這個數字,表明該序列不可能是一個pop序列。
基于前面的分析,我們可以寫出如下的參考代碼:
#include <stack>

/////////////////////////////////////////////////////////////////////////////
// Given a push order of a stack, determine whether an array is possible to
// be its corresponding pop order
// Input: pPush   - an array of integers, the push order
//        pPop    - an array of integers, the pop order
//        nLength - the length of pPush and pPop
// Output: If pPop is possible to be the pop order of pPush, return true.
//         Otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)
{
      bool bPossible = false;

      if(pPush && pPop && nLength > 0)
      {
            const int *pNextPush = pPush;
            const int *pNextPop = pPop;

            // ancillary stack
            std::stack<int> stackData;

            // check every integers in pPop
            while(pNextPop - pPop < nLength)
            {
                  // while the top of the ancillary stack is not the integer 
                  // to be poped, try to push some integers into the stack
                  while(stackData.empty() || stackData.top() != *pNextPop)
                  {
                        // pNextPush == NULL means all integers have been 
                        // pushed into the stack, can't push any longer
                        if(!pNextPush)
                              break;

                        stackData.push(*pNextPush);

                        // if there are integers left in pPush, move 
                        // pNextPush forward, otherwise set it to be NULL
                        if(pNextPush - pPush < nLength - 1)
                              pNextPush ++;
                        else
                              pNextPush = NULL;
                  }

                  // After pushing, the top of stack is still not same as 
                  // pPextPop, pPextPop is not in a pop sequence
                  // corresponding to pPush
                  if(stackData.top() != *pNextPop)
                        break;

                  // Check the next integer in pPop
                  stackData.pop();
                  pNextPop ++;
            }

            // if all integers in pPop have been check successfully, 
            // pPop is a pop sequence corresponding to pPush 
            if(stackData.empty() && pNextPop - pPop == nLength)
                  bPossible = true;
      }

      return bPossible;
}
本文已影響
相關文章
大亨pk10计划苹果版