【栈】化栈为队（实现push、pop、peak、empty等操作）

一、题目

实现一个MyQueue类，该类用两个栈来实现一个队列。

  

 

  
1
 

二、分析

本题是 两栈实现队列 的加强版，在原来只实现push和pop的基础上，新增了实现peak()和empty()的要求。思路还是一样，可以先参考之前的题解，在来看这一题就简单多了。

需要注意的是：本题没有说明当队列中没有元素时，如果执行pop()，应该返回什么。考虑到代码的完整性，这里我默认返回的是-1。

三、题解

C++实现如下：

class MyQueue {
public: /** Initialize your data structure here. */ stack<int> stack1; stack<int> stack2; MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { if(!stack2.empty()){ int ans = stack2.top(); stack2.pop(); return ans; } else{ if(!stack1.empty()){ while(!stack1.empty()){ stack2.push(stack1.top()); stack1.pop();; } int ans = stack2.top(); stack2.pop(); return ans; } else{ return -1;  //当队列是空的时候，返回-1 } } } /** Get the front element. */ int peek() { if(!stack2.empty()){ return stack2.top(); } else{ if(!stack1.empty()){ while(!stack1.empty()){ stack2.push(stack1.top()); stack1.pop(); } return stack2.top(); } else{ return -1; //当队列是空的时候，返回-1 } } } /** Returns whether the queue is empty. */ bool empty() { return stack1.empty() && stack2.empty(); }
};


  

 

  
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
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
 

提交结果如下：

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

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