【栈】用俩个栈来实现队列（剑指Offer 09）

一、题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，
分别完成在队列尾部插入整数和在队列头部删除整数的功能。
(若队列中没有元素，deleteHead 操作返回 -1 )

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

二、分析

本题要求用栈来实现队列，也就是要让先进队的元素先出，后进队的元素后出队，这恰好和栈的性质相反。因此本题采用2个栈来是实现队列的要求，构建两个函数： appendTail() 和 deleteHead()，其主要步骤如下：

• 对于 appendTail() 函数，要求是向队列中的队尾增加元素，可以直接采用stack1来暂存新的元素。当然，需要满足先进的元素先出，只靠一个栈是不行的，所以后面借助stack2来完成。
• 对于 deleteHead() 函数，要求是删除队首的元素，且遵循先入队先删除的原则。这时候，需要借助辅助栈stack2，将stack1中的元素转存至stack2中，这时候stack1栈底的元素(先入队的)就会在stack2的栈顶上stack2.top()，此时就能很方便地将先入队的元素删除stack2.pop()。
• 需要注意的是：一次转存，将stack1中所有的元素转存至stack2中；但是，一次deleteHead()操作，只删除stack2中的一个元素。所以在进行deleteHead()操作时，会先判断stack2中是否有元素。如果有，则每次按顺序删除1个；如果没有，则将stack1中的元素全部转存至stack2中，然后进行删除操作。如果stack1中也没有元素，说明此时栈都是空的，因此返回-1。

三、题解

C++实现如下：

class CQueue { stack<int> stack1; stack<int> stack2;
public: CQueue() { } //将新增的元素暂存在stack1，待需要删除操作时，再一次性将多有元素转存于stack2中 void appendTail(int value) { stack1.push(value); } int deleteHead() { if(!stack2.empty()){ //情况1：stack2里还有之前转存的元素，则直接按顺序pop int ans = stack2.top(); stack2.pop(); return ans; } else{ //情况2：stack2是空的，进一步判断stack1里是否有元素 if(!stack1.empty()){   //如果stack1非空，需将stack1中的元素转存于stack2中，再按照顺序pop while(!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } int ans = stack2.top(); stack2.pop(); return ans; } else{ //如果stack1是空的，说明没有添加任何元素，队列是空的，返回-1 return -1; } } }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
 

提交结果如下：

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/118572261