剑指 Offer 09. 用两个栈实现队列

一、题目描述

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

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

二、解题思路

从题目可以看出，题意是要用两个“先进后出”的栈实现一个“先进先出”的队列。

image-20211125211538040

具体实列：

①、定义两个栈:stack1、stack2;在stack1中依次插入值；

②、然后将stack1中的值依次弹入stack2中；

③、如：在stack1中依次插入1、2、3、4;那么这时stack1的栈顶值为4；然后依次插入stack2中；这时stack2的栈顶值就为：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
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include  <stack>
using namespace std;


class CQueue
{
public:
	//无参构造函数，保证stack1和stack2为空
	CQueue()
	{
		while (!stack1.empty())
		{
			stack1.pop();
		}

		while (!stack2.empty())
		{
			stack2.pop();
		}
	}


	//入栈
	void appendTail(int value)
	{
		stack1.push(value);
	}

	//出栈 实现先进先出
	int deletHead()
	{
		int temp;
		//判断stack2是否为空
		if (stack2.empty())
		{
			if (stack1.empty()) //确保stack1不为空
			{
				return -1;
			}
			else
			{
				while (!stack1.empty())//只要stack1不为空 则将stack1的值弹入stack2中
				{
					temp = stack1.top();//stack1的栈顶保存在temp中
					stack2.push(temp);//将stack1栈顶插入stack2中
					stack1.pop();//把stack1栈顶删除
				}
			}
		}
		else//如果stack2不为空，则弹出stack2的栈顶
		{
			temp = stack2.top();
			stack2.pop();
			return temp;
		}

	}

private:
	stack<int> stack1;
	stack<int> stack2;
};


int main()
{
	CQueue cqueue1;

	//依次插入值：1、2、3、4
	cqueue1.appendTail(1);
	cqueue1.appendTail(2);
	cqueue1.appendTail(3);

	cout << "队列先进先出的数字为：" << cqueue1.deletHead() << endl;

	return 0;

}
1
队列先进先出的数字为：1