《算法通关指南数据结构和算法篇（3）--- 栈和stack》 - 教程

《不一样的数据结构之— 栈和stack》

---

小龙报：个人主页
作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《C语言》《算法》KelpBar海带Linux智慧屏项目

✨***永远相信美好的事情即将发生***

文章目录

• 《不一样的数据结构之— 栈和stack》
• 前言
• 一、栈的概念
• 二、栈的模拟实现
• • 2.1创建
  • 2.2进栈
  • 2.3出栈
  • 2.4栈顶元素
  • 2.5判空
  • 2.6有效元素个数
  • 2.7 所有测试代码
• 三、stack
• • 3.1 如何创建
  • 3.2容器相关接口
  • • 3.2.1 size / empty
    • 3.2.2 push/pop
    • 3.2.3 top
  • 3.3测试所有接口
• 总结 --- 每日励志时刻

---

前言

本系列讲解算法竞赛的数据结构在算法竞赛中，我们主要关心的其实是时间开销，空间上是基本够用的，因此我们是使用庞大的数组实现的话不多说冲！

一、栈的概念

栈是⼀种***只允许在⼀端进行数据插入和删除操作***的线性表。
（1）进行数据插入或删除的一端称为***栈顶***，另⼀端称为***栈底***。不含元素的栈称为空栈。
（2）进栈就是往栈中放入元素，出栈就是将元素弹出栈顶。

ps: 栈其实是⼀个比较简单的数据结构。学习的重点在于用栈去解决问题，这也是难点。
【注意】
如果定义了⼀个栈结构，那么添加和删除元素只能在栈顶进行。不能随意位置添加和删除元素，这是栈这个数据结构的特性，也是规定。

二、栈的模拟实现

2.1创建

（1）本质还是线性表，因此可以创建⼀个足够大的数组，充当栈结构
（2）再定义⼀个变量n，用来记录栈中元素的个数，同时还可以标记栈顶的位置。

const int N = 1e6 + 10;
int stk[N];
int n;

2.2进栈

这里依旧舍弃下标为0 的位置，有效元素从 1开始记录。
***进栈***操作，那就***把元素放在栈顶位置***即可。
不必

//进栈
void push(int x)
{
stk[++n] = x;
}

时间复杂度：O(1)

2.3出栈

ps：不用真的删除元素，只用将元素个数减1，就相当于删除栈顶元素。

//出栈
void pop()
{
n--;
}

时间复杂度：O(1)

2.4栈顶元素

注意：因为栈特殊的规定，不⽀持遍历整个栈中的元素。因此，需要查找栈中元素的时候，只能查找到栈顶元素。

// 栈顶元素
int top()
{
return stk[n];
}

时间复杂度：O(1)

2.5判空

// 判空
bool empty()
{
return n == 0;
}

时间复杂度：O(1)

2.6有效元素个数

// 栈中元素个数 
int size()
{
return n;
}

时间复杂度：O(1)

2.7 所有测试代码

#include <iostream>using namespace std;const int N = 1e6 + 10;int stk[N];int n;//进栈void push(int x){stk[++n] = x;}//出栈void pop(){n--;}// 栈顶元素int top(){return stk[n];}// 判空bool empty(){return n == 0;}// 栈中元素个数 int size(){return n;}int main(){for (int i = 1; i <= 10; i++)push(i);while (!empty())  // while(size()) {cout << top() << " ";pop();}return 0;}

运行结果：

三、stack

3.1 如何创建

stack<T> st;//T 可以是任意类型的数据。

3.2容器相关接口

3.2.1 size / empty

（1）size ：返回栈里实际元素的个数；
（2）empty ：返回栈是否为空。
时间复杂度：O(1)

3.2.2 push/pop

（1） push ：进栈；
（2） pop：出栈。
时间复杂度：O(1)

3.2.3 top

（1） top：返回栈顶元素，但是不会删除栈顶元素。
时间复杂度： O(1)

3.3测试所有接口

#include <iostream>#include <stack>using namespace std;int main(){stack<int> st;// 先讲1~10进栈for (int i = 1; i <= 10; i++){st.push(i);}while (st.size()) // !st.empty(){cout << st.top() << endl;st.pop();}return 0;}

运行结果：

总结 — 每日励志时刻