【刷题篇】栈和队列

深碍√TFBOYSˉ_ 2024-04-25 20:04 74阅读 0赞

![d56c634f454bf8fa7efe0fe4d023e436.gif][]

**目录**

一.前言?

二.有效的括号✨

a.题目

b.题解分析

c.AC代码

三. 用队列实现栈?

a.题目

b.题解分析（辅助队列法）

c.AC代码（辅助队列法）

d.题解分析（就地存储法）

c.AC代码（就地存储法）

四. 用栈实现队列?

a.题目

b.题解分析

c.AC代码

--------------------

### 一.前言? ###

各位小友们好久不见，甚是想念！前段时间我们学习了两个重要的数据结构---栈和队列。那么我们的刷题篇也就该提上日程了，本期将带来三道与栈和队列有关的OJ题，它们分别是：

> ?本期的题目有： 有效的括号、 用队列实现栈、 用栈实现队列
> 
> --------------------
> 
> 注：为了实现方便，本期我们将使用C++来编写代码，利用STL中现有的栈和队列进行实现。

### 二.[有效的括号][Link 1]✨ ###

#### a.题目 ####

![1e18d0eb461b48c0a71edced1283916e.png][]

#### b.题解分析 ####

我们知道，在我们编写的C程序中，会存在着小括号( )、中括号\[ \]以及大括号\{ \}，它们总是成对出现且匹配的，满足这个特点的一组括号我们就称它有效。例如\{ ( ) \[ \] \}就是一组匹配的括号，而\{ ( \[ ) \} \] 就不是一组匹配的括号。我们可以发现一个现象，从左往右开始第一个右括号 其前一个括号 必须是与之对应的左括号，否则这组括号就不匹配

![d7c57ca1b4c040da948043bd0261632c.png][]

而如果本对括号匹配，我们就可以将本对括号移除，进行下一对括号的判断，直到所有括号都成功匹配，说明本组括号是有效的。如果在这个过程中出现一次不匹配，那就说明本组括号无效。

![edf5c1162bbe45a3b76cc8dcf5834752.gif][]

![3592217535a54d628262778e1657df97.gif][]

> 有了以上思路，那究竟要选择什么合适的数据结构来存放我们的括号呢？ 
> 
> 我们自然而然的会想到栈，因为无论是判断是否匹配，移除匹配的括号，我们都只是在其中一端进行操作的。
> 
> --------------------
> 
> 当我们的指针遇到左括号的时候，我们进行入栈操作。当遇到右括号时，我们就和栈顶的左括号进行比较，如果匹配，则pop出栈，移除匹配的括号；如果不匹配，则直接返回false。依次反复直到遍历完整个字符串。

#### c.AC代码 ####

class Solution {
        //存放括号的栈
        stack<char> sta;
    public:
    	bool isValid(string s)
    	{
            //遍历字符串
    		for (int i = 0; i < s.size(); i++)
    		{
    			char c = s.at(i);
    			switch (c)
    			{
    			case '(':
    			case '[':
    			case '{':
    				sta.push(c);//左括号入栈
    				break;
    			case ')':
                case ']':
                case '}':
                    if(sta.empty()) //括号栈为空,匹配失败
                    {
                        return false;
                    }
    				if ((c==')' && sta.top() != '(')||
                        (c==']' && sta.top() != '[')||
                        (c=='}' && sta.top() != '{'))
    				{
    					return false; //匹配失败
    				}
    				else
    				{
    					sta.pop();//成功，将匹配成功的左括号出栈
    				}
    				break;
    			default:
    				//cout << "输入的字符串有误" << endl;
    				return false;
    				break;
    			}
    		}
            //遍历完毕，判断括号栈中还有没有剩余的括号
    		if (sta.empty())//为空
    		{
    			return true;
    		}
    		else//不为空，说明左括号多了，匹配失败
    		{
    			return false;
    		}
    	}
    
    };

### 三. [用队列实现栈][Link 2]? ###

#### a.题目 ####

![f3548953ea074f89bc06020f419fe66f.png][]

#### b.题解分析（辅助队列法） ####

本题要求我们用队列来模拟栈。由于队列的特性是先进先出，栈的特性是后进先出，因此我们需要模拟的栈的栈顶实际上是队尾，我们需要在队尾进行一系列操作。特别是出栈，要先将队列前面的元素全部出队后才能执行。

![b1e6147ed868418f805b3eab99cb512a.png][]

> 显然前面的元素我们不能直接无视，在它们出队的同时我们要将他们存放起来，以供下次使用。那么我们要怎样存储呢？这里有两个方案：辅助空间存储和就地存储。
> 
> --------------------
> 
> 我们先来看看辅助空间存储，我们可以再使用一个辅助的队列来存放队尾前面的元素，由于队列先进先出的特性，每个元素的顺序都将保持一致。当我们进行入栈时就入到不为空的队列；进行出栈时将不为空的队列的前n-1个元素移到为空的队列中，然后将剩下的一个元素pop掉。动态演示如下：

![dd057e1f27e645798e4c4a0fd9963837.gif][]

#### c.AC代码（辅助队列法） ####

class MyStack {
        queue<int> q1;
        queue<int> q2;
    public:
        MyStack() {
    
        }
        //入栈
        void push(int x) 
        {
            //从不为空的队列放入数据
            if (!q1.empty())
            {
                q1.push(x);
            }
            else
            {
                q2.push(x);
            }
    
        }
        //出栈
        int pop() 
        {
            if (q1.empty())
            {
                swap(q1, q2);
            }
            //将前几个元素转移到为空的队列中
            while (q1.size() > 1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            int ret = q1.front();
            q1.pop(); //移除栈顶元素
            return ret;
        }
        //求栈顶元素
        int top() 
        {
            //栈顶所在位置即为队尾，直接访问即可
            if(!q1.empty())
            {
                return q1.back();
            }
            else
            {
                return q2.back();
            }
        }
        //判空
        bool empty() 
        {
            //两个队列都为空说明栈为空
            return q1.empty() && q2.empty();
        }
    };

--------------------

#### **d.题解分析（就地存储法）** ####

上面我们采用了一个辅助队列来进行解题，实际上我们也可以只使用一个队列。出栈的时候只需将前n-1个元素同时出队并再次入队，此时队头元素即为我们的栈顶元素，我们再将其pop，这样依然可以保证原有顺序不变。动态演示如下：

![7872aada319d408095b5a5ed7624e945.gif][]

#### c.AC代码（就地存储法） ####

class MyStack {
        queue<int> q1;
    public:
        MyStack() {
    
        }
        //入栈
        void push(int x) 
        {
            //放入数据,入队
            q1.push(x);
        }
        //出栈
        int pop() 
        {
            //记录当前共有几个元素
            int count=q1.size();
            //将前面count-1个元素出队并入队
            while(count > 1)
            {
                int val=q1.front();
                q1.pop();
                q1.push(val);
                count--;
            }
    
            //将此时的队头，即栈顶元素出队
            int ret=q1.front();
            q1.pop();
            return ret;
        }
        //求栈顶元素
        int top() 
        {
            //栈顶元素就是队尾元素
            return q1.back();
        }
        //判空
        bool empty() 
        {
            //队列为空说明栈为空
            return q1.empty();
        }
    };

### 四. [用栈实现队列][Link 3]? ###

#### a.题目 ####

![c7848d2002d64bffbf62180227b84289.png][]

#### b.题解分析 ####

本题和上一题基本上一样，区别就是我们这次模拟的是队列。由于队列是先进先出，栈是后进先出，因此我们在模拟出队时依旧要将前n个元素先进行出栈。

![1c389550c6bf486991000dad32ad913c.png][]

>  那么，我们要怎样将移除的前n-1个元素存放起来呢，可以就地存储吗？
> 
> --------------------
> 
> 答案是不行的。由于栈是先进先出，出栈和入栈是在同一端进行的，出栈的同时入栈相当于啥也没做。因此我们只能再使用一个栈进行辅助。

![67047687e66d4d9681fd17327cc6aeae.gif][]

> 我们可以设计两个栈，一个栈存储入队的元素(input)，另一个栈用于出队(output)。当进行入队操作时，则往input入栈；当进行出队操作时，如果ouput为空，则先将input中的元素压入output中，此时output的栈顶元素恰好就是队头元素，然后出栈即可，如果不为空，则直接出栈。动态演示如下：

#### ![8e853ac548fb4675934347fc9c5a1668.gif][] ####

#### c.AC代码 ####

class MyQueue {
        stack<int> input;
        stack<int> output;
    public:
        MyQueue() {
    
        }
        //入队
        void push(int x)
        {
            //往input入栈
            input.push(x);
        }
        //出队
        int pop()
        {
            //output为空，先将input数据移入
            if (output.empty())
            {
                while (!input.empty())
                {
                    int val = input.top();
                    input.pop();
                    output.push(val);
                }
            }
            //此时output栈顶元素即为队头元素，出栈
            int ret = output.top();
            output.pop();
            return ret;
        }
        //求队头元素
        int peek()
        {
            //output为空，先将input数据移入
            if (output.empty())
            {
                while (!input.empty())
                {
                    int val = input.top();
                    input.pop();
                    output.push(val);
                }
            }
            //栈顶元素即为队头元素
            int ret = output.top();
            return ret;
        }
        //判空
        bool empty()
        {
            //两个栈都为空说明队列为空
            return input.empty() && output.empty();
        }
    };

--------------------

***以上，就是本期的全部内容啦*****?**

***制作不易，能否点个赞再走呢*****?**

[d56c634f454bf8fa7efe0fe4d023e436.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/00f6cd8307c346fcb59f542c5477fb19.gif
[Link 1]: https://leetcode.cn/problems/valid-parentheses/
[1e18d0eb461b48c0a71edced1283916e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/110b60524c4d423cbdcbea3dd01e51d4.png
[d7c57ca1b4c040da948043bd0261632c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/970f2a731990444c8975c802e7e6162f.png
[edf5c1162bbe45a3b76cc8dcf5834752.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/6319516e462e419f8e87174d2fd41040.gif
[3592217535a54d628262778e1657df97.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/9a03afebfa3f427f8d37a6e5be5d7adf.gif
[Link 2]: https://leetcode.cn/problems/implement-stack-using-queues/
[f3548953ea074f89bc06020f419fe66f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/7befea4e8ae14858b79fe66b27dc9004.png
[b1e6147ed868418f805b3eab99cb512a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/60d0aecfd5b943248c218d846279d433.png
[dd057e1f27e645798e4c4a0fd9963837.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/9f9f22313a694c6f97dddcbde2ebdb74.gif
[7872aada319d408095b5a5ed7624e945.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/6a67a90aed9c4b07a49469b405782614.gif
[Link 3]: https://leetcode.cn/problems/implement-queue-using-stacks/
[c7848d2002d64bffbf62180227b84289.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/ddda44e6a2bc4d21b5b6ec97fb76c65a.png
[1c389550c6bf486991000dad32ad913c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/ff084cf0036f4e3497ec7ca4b57c6fb4.png
[67047687e66d4d9681fd17327cc6aeae.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/f347412d2a314b22b1321a79e353a36a.gif
[8e853ac548fb4675934347fc9c5a1668.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/8fd17b3fd5514868a98028f66bc4f398.gif