秒懂百科，C++如此简单丨第二十一天：栈和队列

阅读本书更多章节>>>>

目录

前言

Everyday English

栈（Stack）

图文解释

实现添加删除元素

实现查看清空栈

完整代码

运行示例

栈的选择题

队列（Queue）

图文解释

队列的基本用法

完整代码 

运行结果 

队列的好处 

结尾 

---

前言

今天我们将学习两个新的数据结构——栈和队列。

Everyday English

A friend in need is a friend indeed.
患难见真情。

栈（Stack）

图文解释

栈最直白的想象就是羽毛球筒了（假设从一个口取）。

比如说我想按照红-橙-黄的顺序放进去，并取出橙色羽毛去，得进行以下操作：

1.放入红-橙-黄色羽毛球。

2.取出顶部的黄色羽毛球。

3.取出顶部的橙色羽毛球。

下面请欣赏我的纯手绘图片：

现在请你把注意力放在黄色羽毛球上，它在放进筒时是最后一个放进去的，而被取出来时是第一个被取出来的；而红色羽毛球却是最后一个被取出来的。所以栈有一个很重要的性质：

先进后出，后进先出（LIFO：Last in first out）

实现添加删除元素

添加：将元素入栈并使指针右移一位。

void add(int n)//添加元素至栈顶{    tmp++;    a[tmp]=n;}

 删除：将元素出栈并使指针左移一位。

void pop()//删除栈顶元素{    a[tmp]=0;//这一步可要可不要    tmp--;}

实现查看清空栈

查看：把数组从1-tmp输出一下即可。

void look(int n[]){    for(int i=1;i<=tmp;i++)    {        cout<<n[i]<<" ";    }}

清空：把数组归零，并把指针赋值为1。 

void empty(int n[]){    for(int i=1;i<=tmp;i++)    {        n[i]=0;    }    tmp=0;}

完整代码

#include<bits/stdc++.h>using namespace std;string op="";int a[1005],tmp=0,n;char b[1005],m;void add(int n)//添加元素至栈顶{tmp++;    a[tmp]=n;}void pop()//删除栈顶元素{a[tmp]=0;//这一步可要可不要tmp--;}void look(int n[]){cout<<"The stack is:";     for(int i=1;i<=tmp;i++)    {        cout<<n[i]<<" ";    }}void empty(int n[]){    for(int i=1;i<=tmp;i++)    {        n[i]=0;    }    tmp=0;    cout<<"The stack is empty now."<<endl;}int main(){memset(a,0,sizeof(a));while(1){cin>>op;if(op[0]=='s') return 0;else {if(op[0]=='a') cin>>n,add(n);if(op[0]=='p') pop();if(op[0]=='l') look(a);if(op[0]=='e') empty(a);}}} 

运行示例

add 1add 2add 3add 4poppoplookThe stack is:1 2add 5emptyThe stack is empty now.add 6lookThe stack is:6

栈的选择题

栈虽然编程中用的不是特别多，但是在CSP的第一轮考试中经常出现，我们来看一看。 

1.有6个元素，按照6、5、4、3、2、1的顺序入栈S，请问下列哪个出栈顺序是非法的？

A.5  4  3  6  1  2

B.4  5  3  1  2  6

C.3  4  6  5  2  1

D.2  3  4  1  5  6

题目来源：2022 CSP-J 选择第二题

解析：因为6比5先入栈，所以出栈时6应该在5后面，故选C。当然你也可以模拟一下。

2.对于入栈顺序为a，b，c，d，e的序列，下列（ ）不是合法的出栈序列。

A.a，b，c，d，e

B.e，d，c，b，a

C.b，a，c，d，e

D.c，d，a，e，b

题目来源：2021 CSP-J 选择题第五题

解析：因为a比b先入栈，所以出栈时a应该在b后面，故选D。当然你也可以模拟一下。

A.进栈一个，出栈一个

B.全部进栈，全部出栈

C.a进栈，b进栈，b出栈，a出栈，剩下的进栈一个，出栈一个。

D.无法完成

3.下图中所使用的数据结构是？

A、栈

B、队列

C、二叉树

D、哈希表

栈的性质是：后进先出，故选A。

队列（Queue）

图文解释

队列顾名思义就是排队买票，先买票的人总是先出来，最后买票的人最后出来。

如上图，1号游客最先排队，所以他第一个买票也是第一个出来的，这就是队列的重要性质：

先进先出，后进后出（FIFO：First in first out）

队列的基本用法

在C++中，已经有为我们写好的队列了，我们只需直接使用即可。

首先需要定义一个队列：

queue<变量类型> q; 

这个变量类型可以是int,double,long long,struct...... 

下面是队列的几个基本用法：

q.pop() //弹出队首元素q.push(item) //把元素item插入到队尾q.empty() //如果队列为空返回True,否则返回Falseq.full() //如果队列已满返回True,否则返回Falseq.front() //调用队首元素q.size() //返回队列中元素的数量

完整代码 

#include<bits/stdc++.h>using namespace std;int main(){    queue<int> q;    q.push(1);    q.push(2);    q.push(3);    q.pop();    cout<<q.front()<<endl;    q.pop();    cout<<q.size()<<endl;    q.pop();    if(q.empty()) cout<<"The queue is empty."<<endl;    return 0;}

运行结果 

21The queue is empty.

队列的好处 

等我们后面学到BFS时，会用到很多有关于队列的知识。

结尾 

本篇文章我们学习了栈和队列，图片为纯手绘无参考，制作不易，还请各位大佬三连支持一下！

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/zhengce/2024-03-26/148925.html，文章来源：网络cs，作者：利杜鹃，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！