575-两个队列实现一个栈

系统管理员 2022-09-11 14:18 82阅读 0赞

## 两个队列实现一个栈 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**队列的特征是**：先进先出，后进后出  
**从1个队列出队，添加到另外1个队列里面，元素的顺序是没有变化的。**

## 1个队列实现1个栈 ##

**实际上，用队列实现1个栈，1个队列就可以完成了！**  
队列只能从队头出，队尾入  
我们现在添加一个元素12  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]  
然后我们再添加1个元素5  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]  
**现在我们要从队头出队，我们知道，队列都有一个size方法**，每次添加1个元素后，队列的size就增加。现在队列的size是2。  
我们现在出2-1个元素。  
也就是说，出1个，把12出队，然后入队，即添加到队尾  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**实际上，这是在维护一个栈的特性。后入栈的在队头。**  
接着，我们再入栈78，![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
现在size是3，出3-1=2个元素。  
然后把出队的元素依次入队队尾。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**现在的队列元素就是栈的顺序了。**  
**出栈就是出队了。**  
**查看栈顶元素，就是查看队头元素了。**  
**栈是不是空，看队列是不是空就可以了。**

## 2个队列实现1个栈 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
**现在两个队列都是空的。**  
**我们现在要添加元素12，放到q1队列里面。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16 1]

我们现在继续添加元素5，把5放到队列q2中。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_16_color_FFFFFF_t_70_g_se_x_16]  
**然后现在我们要把之前不为空的队列(q1)的元素都出队，然后依次入队q2里面。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]  
**然后现在我们要入栈78,78放在为空的队列（q1)里面**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 3]  
**然后把另外1个不为空的队列(q2)里的元素全部出队，依次入队到q1**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 4]  
**现在的队列q1就是栈的特性了。**  
**后入的元素在队头，先入的元素在队尾。**  
现在我们要添加元素9, 9入到空的队列(q2)里面  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 5]  
然后把另外一个不空的队列(q1)的全部元素出队，依次入队到q2中  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]  
**也就是说，逻思路是这样的：**

**每次进行元素添加的时候，先判断哪个队列为空，就添加到哪个队列里，然后把另一个不为空的队列依次出队，入队到刚才添加元素的队列中**

**但是我们现在想要实现这样：q1专门存放新入栈的元素，q2专门存储已经调整好的栈的数据**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**所以，我们定义2个指针，我们把q1当做其中1个指针，永远指向空的队列，存放新的元素，把后入的元素调整到队头，我们把q2当做另1个指针，永远指向存储已经调整好的栈的数据的队列**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]

## 代码实现 ##

#include <iostream>
    #include<queue>
    using namespace std;
    
    class MyStack
    {
        
    public:
    	MyStack()
    	{
        
    		q1 = new queue<int>;
    		q2 = new queue<int>;
    	}
    	~MyStack()
    	{
        
    		delete q1;
    		delete q2;
    		q1 = nullptr;
    		q2 = nullptr;
    	}
    public:
    	void push(int x)
    	{
        
    		q1->push(x);
    		while (!q2->empty())
    		{
        
    			q1->push(q2->front());
    			q2->pop();
    		}
    		queue<int>* tmp = q1;
    		q1 = q2;
    		q2 = tmp;
    	}
    	int pop()
    	{
        
    		int val = q2->front();
    		q2->pop();
    		return val;
    	}
    	int top()
    	{
        
    		return q2->front();
    	}
    	bool empty()
    	{
        
    		return q2->empty();
    	}
    private:
    	queue<int>*q1;
    	queue<int>*q2;
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f005b1d08e0e499e994bdd4699b4cd5f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/0358b3d2f1414a1aaf0b244b3ae0ac13.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/037c8298d10a4523ac3dd3485a37b1d5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c57a8f1d80184d88a40e75529d7388e8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/ca6dba7099c042a59508a658994e9ed9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/72d8a2c1d38942a5853f5e9327f8e116.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/e5099f8a8f4b46b49321e8e16edcb8cd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/cde08f7e4b5b4ef580ddd162b8a303b4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/091e635e77bb4dfc81b208fe04846d68.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9c39671f84694f0995e450d08d933e0c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/b5e94838cf294ab4b70c18ec76260472.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/98f0e3d3e9d64d2b909f6d62bfa29e87.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/be07c0bc3c394628a0e34606fbafc879.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/ccacd9d2c61d4508989fb9afe8442cca.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3e00962516104dd2a6024c3ffb46b85d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/b3a3448263c34faa97f6f7a5627c049a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/128b2ae55f884bb483de57932304fdfc.png