棧和隊(duì)列相關(guān)面試題-創(chuàng)新互聯(lián)

棧和隊(duì)列 相關(guān) 面試題

在白銀區(qū)等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需網(wǎng)站設(shè)計(jì),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計(jì),全網(wǎng)整合營(yíng)銷推廣,外貿(mào)網(wǎng)站建設(shè),白銀區(qū)網(wǎng)站建設(shè)費(fèi)用合理。

// 1、實(shí)現(xiàn)一個(gè)棧，要求實(shí)現(xiàn)Push（出棧）、 Pop（入棧）、Min（返回最小值的操作） 的時(shí)間復(fù)雜度為O(1)

// 【劍指offer 面試題21】

template<class T>

class StackWithMin

{

public:

    void push(const T& value);

    void pop();

    const T& min() const;

protected:

    stack<T> _min; //  記錄每次出棧壓棧 最小值

    stack<T> _data; //  存數(shù)據(jù)

};

template<class T>

void StackWithMin<T>::push(const T& value)

{

    _data.push(value);

    if (_min.size() == 0 || value < _min.top())

    {

        _min.push(value);

    }

    else

    {

        _min.push(_min.top());

    }

}

template<class T>

 void StackWithMin<T>::pop()

 {

     assert(_data.size() > 0 && _min.size() > 0);

     _data.pop();

     _min.pop();

 }

 template<class T>

const T& StackWithMin<T>::min() const

 {

     assert(_data.size() > 0 && _min.size() > 0);

     return _min.top();

 }

 void test_StackWithMin()

 {

     StackWithMin<int> st;

     st.push(8);

     st.push(5);

     st.push(3);

     st.push(2);

     st.push(2);

     int min = st.min();

     st.pop();

     st.pop();

     st.pop();

     min = st.min();

 }

棧和隊(duì)列 相關(guān) 面試題

//   2、使用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

 // 【劍指offer 面試題7】

 template<class T>

 class CQueue

 {

 public:

     void appendTail(const T& node);

     T deleteHead();

 protected:

     stack<T> _stack1;

     stack<T> _stack2;

 };

 template<class T>

 void CQueue<T>::appendTail(const T& node)

 {

     _stack1.push(node);

 }

 template<class T>

 T CQueue<T>::deleteHead()

 {

     if (_stack2.size() <= 0)

     {

         while (_stack1.size() > 0)

         {

             T& data = _stack1.top();

             _stack2.push(data);

             _stack1.pop();

         }

     }

     if (_stack2.size() == 0)

     {

         throw exception("queue is empty");

     }

     T head = _stack2.top();

     _stack2.pop();

     return head;

 }

 void test_CQueue()

 {

     CQueue<int> q;

     q.appendTail(1);

     q.appendTail(2);

     q.appendTail(3);

     q.deleteHead();

     q.deleteHead();

     q.deleteHead();

     try

     {

         q.deleteHead();

     }

     catch (const exception& e)

     {

         cout<<e.what();

     }

 }

////3、使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

 // 【劍指offer 面試題 7 擴(kuò)展】

 //題目：用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的pop和push函數(shù)。

//思路：入棧動(dòng)作時(shí)，如果內(nèi)部?jī)蓚€(gè)隊(duì)列都為空的話，將數(shù)據(jù)壓入其中一個(gè)隊(duì)列(代碼中為m_queue1)。如果其中一個(gè)隊(duì)列已經(jīng)有數(shù)據(jù)了，則將數(shù)據(jù)壓入已經(jīng)有數(shù)據(jù)的那個(gè)隊(duì)列。出棧動(dòng)作時(shí)，先將有數(shù)據(jù)的那個(gè)隊(duì)列，除了最后一個(gè)入隊(duì)的數(shù)據(jù)之外的所有數(shù)據(jù)輸出到另外一個(gè)空的隊(duì)列，然后最后那個(gè)數(shù)據(jù)也出隊(duì)。

#include <queue>

 template<class T>

 class CStack

 {

 public:

     void push(const T& node);

     T pop();

 private:

     queue<T> _queue1;

     queue<T> _queue2;

 };

 template <class T>

 void CStack<T>::push(const T& node)

 {

     if ((_queue1.empty() && _queue2.empty()) || _queue1.size())

     {

         _queue1.push(node);

     }

     else

     {

         _queue2.push(node);

     }

 }

 template<class T>

 T CStack<T>::pop()

 {

     assert(!(_queue1.empty() && _queue2.empty()));

     T node;

     if (_queue1.size())

     {

         while (_queue1.size() > 1)

         {

             node = _queue1.front();

             _queue1.pop();

             _queue2.push(node);

         }

         node = _queue1.front();

         _queue1.pop();

     }

     else // _queue2 有數(shù)據(jù) _queue1 空

     {

         while (_queue2.size() > 1)

         {

             node = _queue2.front();

             _queue2.pop();

             _queue1.push(node);

         }

         node = _queue2.front();

         _queue2.pop();

     }

     return node;

 }

 void test_CStack()

 {

     CStack<char> testStack ;

    testStack.push('a')  ;

    testStack.push('b') ;

    testStack.push('c') ;

    char ch = testStack.pop() ;

    printf("%c\n",ch) ;

    ch = testStack.pop() ;

    printf("%c\n",ch) ;

    testStack.push('d') ;

    ch = testStack.pop() ;

    printf("%c\n",ch) ;

 }

棧和隊(duì)列 相關(guān) 面試題

// 4、元素出棧、入棧順序的合法性。如入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,2,1）

 //  【劍指offer 面試題22】

 bool IsPopOrder(const int* pPush, const int* pPop, int nLength)

 {

     bool bPossible = false;

     if (pPush != NULL && pPop != NULL && nLength > 0)

     {

         const int* pNextPush = pPush;

         const int* pNextPop = pPop;

         stack<int> stackData;

         while (pNextPop - pPop < nLength)

         {

             while (stackData.empty() || stackData.top() != *pNextPop)

             {

                 if (pNextPush - pPush == nLength)

                 {

                     break;

                 }

                 stackData.push(*pNextPush);

                 pNextPush++;

             }

             if (stackData.top() != *pNextPop)  //  if (pNextPush - pPush == nLength) 跳出的

             {

                 break; //  不匹配

             }

             stackData.pop();

             pNextPop++;

         }

         if (stackData.empty() && pNextPop - pPop == nLength)

         {

             bPossible = true;

         }

     }

     return bPossible;

 }

 void test_IsPopOrder()

 {

     int PushArry[] = {1,2,3,4,5};

     int PopArray1[] = {3,2,5,4,1};

     int PopArray2[] = {3,2,5,1,4};

     int PopArray3[] = {3,2,5,1,1};

     bool ret1 = IsPopOrder(PushArry, PopArray1,5);

     bool ret2 = IsPopOrder(PushArry, PopArray2,5);

     bool ret3 = IsPopOrder(PushArry, PopArray3,5);

 }

//    5、一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧

 //  https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter10/Exercise10_1_2.cpp

 class arrayWithTwoStack

 {

 public:

     arrayWithTwoStack(int size)

         :_top1(0)

         ,_top2(size - 1)

         ,_len(size)

     {

        _s = new int[size];

     }

     bool isEmpty(int index);// index指定哪個(gè)棧

     void push(int index, int data);

     int pop(int index);

 private:

     int _top1;

     int _top2;  // 兩個(gè)棧頂坐標(biāo)

     int _len ;  //  數(shù)組長(zhǎng)度

     int* _s;    //

 };

 bool arrayWithTwoStack::isEmpty(int index)

 {

     if (index == 0 && _top1 == 0)

     {

         return true;

     }

     if (index == 1 && _top2 == _len - 1)

     {

         return true;

     }

     return false;

 }

 void arrayWithTwoStack::push(int index, int data)

 {

     // 已滿

     if (_top1 >= _top2)

     {

         throw exception("error: overflow");

     }

     // 對(duì)棧1操作

     if (index == 0)

     {

         _s[_top1] =data;

         _top1++;

     }

     else if (index == 1)

     {

         _s[_top2] = data;

                  _top2--;

     }

 }

 //出棧

 int arrayWithTwoStack::pop(int index)

 {

     int ret;

     if (index == 0)

     {

         //棧1空

         if (_top1 == 0)

         {

             throw exception("error: stack 0 is empty");

         }

         else

         {

             ret = _s[--_top1];

         }

     }

     else if (index == 1)

     {

         //棧 2 空

         if (_top2 == _len - 1)

         {

             throw exception("error: stack 1 is empty");

         }

         else

         {

             ret = _s[++_top2];

         }

     }

     return ret;

 }

 void test_arrayWithTwoStack()

 {

     arrayWithTwoStack S(6);

     // s0 123  54 s1

     S.push(0,1);

     S.push(0,2);

     S.push(0,3);

     try{

     S.push(1,4);

     S.push(1,5);

     }

     catch(exception e)

     {

         cout<<e.what()<<endl;

     }

     S.pop(0);

     S.pop(1);

     S.pop(1);

     bool em = S.isEmpty(1);

 }

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站標(biāo)題：棧和隊(duì)列相關(guān)面試題-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article8/dhooip.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、自適應(yīng)網(wǎng)站、網(wǎng)站制作、動(dòng)態(tài)網(wǎng)站、搜索引擎優(yōu)化、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

搜索引擎優(yōu)化