栈和队列相关面试题

创新互联专注于石拐网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供石拐营销型网站建设，石拐网站制作、石拐网页设计、石拐网站官网定制、微信小程序服务，打造石拐网络公司原创品牌,更为您提供石拐网站排名全网营销落地服务。

// 1、实现一个栈，要求实现Push（出栈）、 Pop（入栈）、Min（返回最小值的操作） 的时间复杂度为O(1)

// 【剑指offer 面试题21】

template

class StackWithMin

{

public:

    void push(const T& value);

    void pop();

    const T& min() const;

protected:

    stack _min; //  记录每次出栈压栈 最小值

    stack _data; //  存数据

};

template

void StackWithMin::push(const T& value)

{

    _data.push(value);

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

    {

        _min.push(value);

    }

    else

    {

        _min.push(_min.top());

    }

}

template

 void StackWithMin::pop()

 {

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

     _data.pop();

     _min.pop();

 }

 template

const T& StackWithMin::min() const

 {

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

     return _min.top();

 }

 void test_StackWithMin()

 {

     StackWithMin 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();

 }

//   2、使用两个栈实现一个队列

 // 【剑指offer 面试题7】

 template

 class CQueue

 {

 public:

     void appendTail(const T& node);

     T deleteHead();

 protected:

     stack _stack1;

     stack _stack2;

 };

 template

 void CQueue::appendTail(const T& node)

 {

     _stack1.push(node);

 }

 template

 T CQueue::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 q;

     q.appendTail(1);

     q.appendTail(2);

     q.appendTail(3);

     q.deleteHead();

     q.deleteHead();

     q.deleteHead();

     try

     {

         q.deleteHead();

     }

     catch (const exception& e)

     {

         cout<

     }

 }

////3、使用两个队列实现一个栈

 // 【剑指offer 面试题 7 扩展】

 //题目：用两个队列实现一个栈。队列的声明如下，请实现它的pop和push函数。

//思路：入栈动作时，如果内部两个队列都为空的话，将数据压入其中一个队列(代码中为m_queue1)。如果其中一个队列已经有数据了，则将数据压入已经有数据的那个队列。出栈动作时，先将有数据的那个队列，除了最后一个入队的数据之外的所有数据输出到另外一个空的队列，然后最后那个数据也出队。

#include 

 template

 class CStack

 {

 public:

     void push(const T& node);

     T pop();

 private:

     queue _queue1;

     queue _queue2;

 };

 template 

 void CStack::push(const T& node)

 {

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

     {

         _queue1.push(node);

     }

     else

     {

         _queue2.push(node);

     }

 }

 template

 T CStack::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 有数据 _queue1 空

     {

         while (_queue2.size() > 1)

         {

             node = _queue2.front();

             _queue2.pop();

             _queue1.push(node);

         }

         node = _queue2.front();

         _queue2.pop();

     }

     return node;

 }

 void test_CStack()

 {

     CStack 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) ;  

 }

// 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 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、一个数组实现两个栈

 //  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指定哪个栈

     void push(int index, int data);

     int pop(int index);

 private:

     int _top1;

     int _top2;  // 两个栈顶坐标

     int _len ;  //  数组长度

     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");

     }

     // 对栈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<

     }

     S.pop(0);

     S.pop(1);

     S.pop(1);

     bool em = S.isEmpty(1);

 }