面试题7：用两个栈实现队列-白红宇

面试题7：用两个栈实现队列

阅读量：5328 次

发布时间：2019-06-14

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

stack1负责如队列，stack2负责出队列，当stack2为空时，要将stack1的元素及时放入stack2

两个队列也可以实现一个栈，P61

写程序的时候出了两个问题：

if (stack2.empty())    {        while (!stack1.empty())        {            stack2.push(stack1.top());            stack1.pop();        }    }

不要写成while(!stack1.empty() && !stack2.empty())，这样的话只会放入stack1中的一个元素

另外模板函数前不要忘记加类型

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

template <typename T> T CQueue<T>::deleteHead()

完整程序：

1 #include 
     
       2 using namespace std; 3 #include 
      
        4  5 template 
       
         class CQueue 6 { 7 public: 8     CQueue(void); 9     ~CQueue(void);10 11     // 在队列末尾添加一个结点12     void appendTail(const T& node);13 14     // 删除队列的头结点15     T deleteHead();16 17 private:18     stack
        
          stack1;19     stack
         
           stack2;20 };21 22 template 
          
            CQueue
           
            ::CQueue(void)23 {24 }25 26 template 
            
              CQueue
             
              ::~CQueue(void)27 {28 }29 30 template 
              
                void CQueue
               
                ::appendTail(const T& node)31 {32 stack1.push(node);33 }34 35 template 
                
                  T CQueue
                 
                  ::deleteHead()36 {37 if (stack2.empty())38 {39 while (!stack1.empty())40 {41 stack2.push(stack1.top());42 stack1.pop();43 }44 }45 46 if (stack2.size() == 0)47 throw new exception("queue is empty");48 49 T head = stack2.top();50 stack2.pop();51 52 return head;53 54 }55 56 void Test(char actual, char expected)57 {58 if (actual == expected)59 printf("Test passed.\n");60 else61 printf("Test failed.\n");62 }63 64 int main()65 {66 CQueue
                  
                    queue;67 68 queue.appendTail('a');69 queue.appendTail('b');70 queue.appendTail('c');71 72 char head = queue.deleteHead();73 Test(head, 'a');74 75 head = queue.deleteHead();76 Test(head, 'b');77 78 queue.appendTail('d');79 head = queue.deleteHead();80 Test(head, 'c');81 82 queue.appendTail('e');83 head = queue.deleteHead();84 Test(head, 'd');85 86 head = queue.deleteHead();87 Test(head, 'e');88 89 system("pause");90 return 0;91 }