目录
一.前言🌈
二.有效的括号✨
a.题目
b.题解分析
c.AC代码
三. 用队列实现栈📏
a.题目
b.题解分析(辅助队列法)
c.AC代码(辅助队列法)
d.题解分析(就地存储法)
c.AC代码(就地存储法)
四. 用栈实现队列🍀
a.题目
b.题解分析
c.AC代码
一.前言🌈
各位小友们好久不见,甚是想念!前段时间我们学习了两个重要的数据结构---栈和队列。那么我们的刷题篇也就该提上日程了,本期将带来三道与栈和队列有关的OJ题,它们分别是:
🚀本期的题目有: 有效的括号、 用队列实现栈、 用栈实现队列
注:为了实现方便,本期我们将使用C++来编写代码,利用STL中现有的栈和队列进行实现。
二.有效的括号✨
a.题目
b.题解分析
我们知道,在我们编写的C程序中,会存在着小括号( )、中括号[ ]以及大括号{ },它们总是成对出现且匹配的,满足这个特点的一组括号我们就称它有效。例如{ ( ) [ ] }就是一组匹配的括号,而{ ( [ ) } ] 就不是一组匹配的括号。我们可以发现一个现象,从左往右开始第一个右括号 其前一个括号 必须是与之对应的左括号,否则这组括号就不匹配
而如果本对括号匹配,我们就可以将本对括号移除,进行下一对括号的判断,直到所有括号都成功匹配,说明本组括号是有效的。如果在这个过程中出现一次不匹配,那就说明本组括号无效。
有了以上思路,那究竟要选择什么合适的数据结构来存放我们的括号呢?
我们自然而然的会想到栈,因为无论是判断是否匹配,移除匹配的括号,我们都只是在其中一端进行操作的。
当我们的指针遇到左括号的时候,我们进行入栈操作。当遇到右括号时,我们就和栈顶的左括号进行比较,如果匹配,则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;
}
}
};
三. 用队列实现栈📏
a.题目
b.题解分析(辅助队列法)
本题要求我们用队列来模拟栈。由于队列的特性是先进先出,栈的特性是后进先出,因此我们需要模拟的栈的栈顶实际上是队尾,我们需要在队尾进行一系列操作。特别是出栈,要先将队列前面的元素全部出队后才能执行。
显然前面的元素我们不能直接无视,在它们出队的同时我们要将他们存放起来,以供下次使用。那么我们要怎样存储呢?这里有两个方案:辅助空间存储和就地存储。
我们先来看看辅助空间存储,我们可以再使用一个辅助的队列来存放队尾前面的元素,由于队列先进先出的特性,每个元素的顺序都将保持一致。当我们进行入栈时就入到不为空的队列;进行出栈时将不为空的队列的前n-1个元素移到为空的队列中,然后将剩下的一个元素pop掉。动态演示如下:
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,这样依然可以保证原有顺序不变。动态演示如下:
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();
}
};
四. 用栈实现队列🍀
a.题目
b.题解分析
本题和上一题基本上一样,区别就是我们这次模拟的是队列。由于队列是先进先出,栈是后进先出,因此我们在模拟出队时依旧要将前n个元素先进行出栈。
那么,我们要怎样将移除的前n-1个元素存放起来呢,可以就地存储吗?
答案是不行的。由于栈是先进先出,出栈和入栈是在同一端进行的,出栈的同时入栈相当于啥也没做。因此我们只能再使用一个栈进行辅助。
我们可以设计两个栈,一个栈存储入队的元素(input),另一个栈用于出队(output)。当进行入队操作时,则往input入栈;当进行出队操作时,如果ouput为空,则先将input中的元素压入output中,此时output的栈顶元素恰好就是队头元素,然后出栈即可,如果不为空,则直接出栈。动态演示如下:
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();
}
};
以上,就是本期的全部内容啦🌸文章来源:https://www.toymoban.com/news/detail-433831.html
制作不易,能否点个赞再走呢🙏文章来源地址https://www.toymoban.com/news/detail-433831.html
到了这里,关于【刷题篇】栈和队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!