本文共 4103 字，大约阅读时间需要 13 分钟。

用两个队列实现一个栈

1. 算法导论原题

10.1-7

Show how to implement a stack using two queues. Analyze the running time of the stack operations.

译：使用两个队列实现一个栈。分析栈操作的运行时间（这部分本博文不解答）。

2. 如何使用两个队列实现一个栈？

由于队列的方式是后进后出，而栈的方式是后进先出。所以使用队列实现栈的话，需要将队列的最后一个元素之前的所有元素输出到另一个队列，然后该队列只剩下一个元素，将该元素出队列，因此队列达到了最后一个元素先输出的目的，也就是实现了一个栈。

3. 实现（C++代码）

//StackByTwoQueue.h#pragma once#include 
   
    #include "SequeQueue.h"template
    
     class StackByTwoQueue{public:    StackByTwoQueue(unsigned int size);    bool Push(ElemType elem);    bool Pop(ElemType* elem);    bool Empty() const;    bool Visit(ElemType* elem, const unsigned int& pos) const;private:    bool ToOtherSide(SequeQueue
     
      * source, SequeQueue
      
       * destination);    SequeQueue
       
        * m_queueLeft;    SequeQueue
        
         * m_queueRight; unsigned int m_size;};template
         
          bool StackByTwoQueue
          
           ::Visit(ElemType* elem, const unsigned int& pos) const{ if (pos >= m_size) { return m_queueRight->Visit(elem, pos - m_size); } else { return m_queueLeft->Visit(elem, pos); }}template
           
            bool StackByTwoQueue
            
             ::Empty() const{ if (m_queueLeft->Empty() && m_queueRight->Empty()) { return true; } return false;}template
             
              bool StackByTwoQueue
              
               ::ToOtherSide(SequeQueue
               
                * source, SequeQueue
                
                 * destination){ int length = source->GetLength(); for (int i = 0; i < length - 1; i++) { ElemType tempElem; source->DeQueue(&tempElem); destination->EnQueue(tempElem); } return true;}template
                 
                  bool StackByTwoQueue
                  
                   ::Pop(ElemType* elem){ if (Empty()) { assert(false && "Error: StackByTwoQueue is underflow!\n"); return false; } if (m_queueLeft->Empty()) { ToOtherSide(m_queueRight,m_queueLeft); return m_queueRight->DeQueue(elem); } else { ToOtherSide(m_queueLeft,m_queueRight); return m_queueLeft->DeQueue(elem); }}template
                   
                    bool StackByTwoQueue
                    
                     ::Push(ElemType elem){ if (!m_queueLeft->Empty()) { return m_queueLeft->EnQueue(elem); } else { return m_queueRight->EnQueue(elem); }}template
                     
                      StackByTwoQueue
                      
                       ::StackByTwoQueue(unsigned int size) :m_queueLeft(new SequeQueue
                       
                        (size)),m_queueRight(new SequeQueue
                        
                         (size)),m_size(size){}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

//Util.h#pragma oncenamespace Util{    template
   
        void PrintMemory(const T& dateStruct, unsigned int size)    {        cout << "PrintMemory: ";        for (int i = 0; i != size; i++)        {            ElemType tempElem;            dateStruct.Visit(&tempElem,i);            printf("%d ",tempElem);        }        printf("\n");        printf("\n");    }}
   

//main.cpp#include "Util.h"#include "StackByTwoQueue.h"#include 
   
    using namespace std;typedef int ElemType;int main(){    const int QUEUE_SIZE = 5;    StackByTwoQueue
    
      testStackByTwoQueue(QUEUE_SIZE);    cout << "testStackByTwoQueue is " << (testStackByTwoQueue.Empty() ? "Empty." : "Not Empty.") << endl;    Util::PrintMemory(testStackByTwoQueue,2*QUEUE_SIZE);    for (int i = 1; i != 5; i++)    {        testStackByTwoQueue.Push(i);        cout << "Push:" << i << endl;        cout << "testStackByTwoQueue is " << (testStackByTwoQueue.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testStackByTwoQueue,2*QUEUE_SIZE);    }    for (int i = 1; i != 5; i++)    {        ElemType tempElem;        testStackByTwoQueue.Pop(&tempElem);        cout << "Pop:" << tempElem << endl;        cout << "testStackByTwoQueue is " << (testStackByTwoQueue.Empty() ? "Empty." : "Not Empty.") << endl;        Util::PrintMemory(testStackByTwoQueue,2*QUEUE_SIZE);    }    return 0;}
    
   

4. 程序运行结果

testStackByTwoQueue is Empty.

PrintMemory: 0 0 0 0 0 0 0 0 0 0

Push:1

testStackByTwoQueue is Not Empty.

PrintMemory: 0 0 0 0 0 1 0 0 0 0

Push:2

testStackByTwoQueue is Not Empty.

PrintMemory: 0 0 0 0 0 1 2 0 0 0

Push:3

testStackByTwoQueue is Not Empty.

PrintMemory: 0 0 0 0 0 1 2 3 0 0

Push:4

testStackByTwoQueue is Not Empty.

PrintMemory: 0 0 0 0 0 1 2 3 4 0

Pop:4

testStackByTwoQueue is Not Empty.

PrintMemory: 1 2 3 0 0 1 2 3 4 0

Pop:3

testStackByTwoQueue is Not Empty.

PrintMemory: 1 2 3 0 0 2 2 3 4 1

Pop:2

testStackByTwoQueue is Not Empty.

PrintMemory: 1 2 3 1 0 2 2 3 4 1

Pop:1

testStackByTwoQueue is Empty.

PrintMemory: 1 2 3 1 0 2 2 3 4 1

转载地址：http://mnyii.baihongyu.com/