当前位置：首页 > news >正文

【数据结构】——栈和队列OJ

news 来源：原创 2025/7/7 11:17:09

一、有效的括号

题目链接：

20. 有效的括号 - 力扣（LeetCode）

题目的要求很简单，就是要求我们判断其输入的括号字符串是否是有效的括号，那么我们要如何判断呢？

我们可以这样，我们遍历出传入的字符串，然后我们创建一个栈，然后如果这个字符是组左括号，那么我们就让其入栈，然后如果是右括号，那么我们就取栈顶的元素和这个右括号进行对比，如果匹配那么就出栈，不匹配的话那么就说明这个字符串不是有效的括号，然后继续进行比较，直到字符串遍历完，那么我们字符串遍历完后，是否就表示我们的这个括号是有效的呢？

并不是，我们还有一种情况，就是我们的字符串全是左括号，那么我们可以在最后进行判断栈，如果栈不为空，那么就说明我们的字符串是无效的括号，那么我们要是为全是右括号的情况呢？

那么我们都是右括号的话，那么我们再取栈顶元素这里就会造成越界访问了，所以我们再判断到其字符不是左边括号的时候，那么我们进入要其是右边括号的情况，那么我们要先判断栈内不为空才行。

那么我们可以将我们前面学习的栈的功能的代码复制到oj平台中，然后我们再写题目中的函数。

二、用队列实现栈

题目链接：

225. 用队列实现栈 - 力扣（LeetCode）

上面的题目也很好理解，就是要我们使用两个队列来实现栈的功能，我们经过前面的学习都知道我们的队列是先进先出，栈是先进后出，队列是一端进，另外一端出，然后栈是只能从栈顶入栈和出栈。其他的两个是差不多的。那么我们改如何使用两个队列来实现栈的功能呢？我们主要是要想办法将我们入队列的数据可以反过来出队列，不过我们发现其不要求我们出栈要在一个队列，我们要两个队列进行配合。

例如我们现在要入1，2，3，4。四个数据，那么我们的入队列的顺序为1->2->3->4，我们现在希望其出队列的顺序为4->3->2->1，那么我们改如何实现呢？

我们可以这样，我们每次要出栈都是要出的入队列最晚的数据，那么我们可以这样，我们每次入栈，都将其先入到一个非空的队列中，然后我们要出栈的时候，那么我们就将从出队列那一端的前size-1个数据按照入队列的顺序，将其转移到另外一个空队列，那么我们要出栈就对原来那个队列进行出栈，那么就可以实现我们的先进先出的功能了。

我们这里需要使用很多队列的功能，那么我们将我们前面完成的队列的功能的函数都复制到oj平台上。

首先我们要先创建两个队列，题目中提供了这个结构体，那么我们在这个结构体中创建两个队列成员即可。

然后我们要对我们的两个队列进行初初始化：

下面我们就要对数据进行入栈，我们提到了，我们入栈的话是将数据存储到非空的队列中，那么我们直接进行判断队列是否为空，不为空我们就调用我们的入队的函数即可。

然后就是我们的出栈了，我们出栈，实际上是出的非空队列的队尾的元素，那么我们就先将非空队列的队尾前面的元素移动到空队列中，然后再出队，那么就可以完成出栈了。

然后就到我们的取栈顶元素，其实就是我们当前不为空的队列的队尾的元素：

然后就是我们的判断当前栈是否为空：那么我们就判断两个队列即可，首先我们这个栈要为空的话，那么我们就需要两个队列都为空，那么我们就返回teur，那么就是我们的判队列为空的函数，当队列为空的时候能返回true，然后两个要都为空，所以我们使用一个与逻辑即可。

然后就剩下我们的销毁栈啦，那么我们直接调用我们销毁队列的函数，将两个队列进行销毁，然后再将这个栈结构也销毁即可。

三、用栈实现队列

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

上面我们是使用队列实现栈，现在这个题目就要求我们使用栈实现队列啦，那么我们要如何实现呢?

我们的栈是先进后出，队列是先进先出，那么我们此时就要两个栈进行配合，实现先进先出的功能，那么我们是否可以和上面队列实现栈一样呢？

基本的逻辑是一样，还是两个栈之间进行数据的倒，但是我们此时不是轮流进行倒了，我们是指定一个栈专门用来实现先进先出，那么具体是咋样呢？

我们先将数据入第一个栈，然后我们就保留栈底的元素，然后我们就从栈顶开始出栈到另外一个栈，然后第一个栈就只有栈底的元素了，那么此时再出栈，此时的数据就是这个队列出队的数据，然后我们第二个栈，此时的栈底是原来栈顶的元素，那么我们此时就要将第二个栈倒回去，然后再重新进行上面的操作吗？

其实不用，我们此时就可以直接对第二个栈进行出栈即可，因为此时我们的第二个栈的方向和一开始不同的了。

下面我们举个例子来理解：

比如我们入第一个栈的顺序为1->2->3->4，那么我们执行第一个操作后，我们的第二个栈从栈顶到栈底的顺序为2->3->4，那么我们此时就直接按照顺序进行出栈，那么就是我们的队列啦，那么我们的逻辑就是，我们判断第二个栈是否为空，如果不为空，那么我们就直接出栈，如果为空，那么我们就将专门用来入队的栈，出栈到第二个栈中。

下面我们来实现一下：

首先我们将我们前面学习的栈的代码进行拷贝复制一下，然后我们一步一步实现题目的要求。

我们题目第一个函数，要求实现队列的初始化，我们就在函数中创建一个队列，然后我们队列结构体是由两个栈组成的，然后我们对两个栈初始化即可，那么我们就调用我们的栈初始化函数即可。