文章目录

• 定义
• 栈的应用
• 栈中的专业名词
• 例题
• 习题巩固

定义

栈：仅在表尾进行插入和删除操作的线性表

与之对应的：当一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

特性：前进后出

可以想象一下沙漠之鹰的手枪，进栈为子弹弹入弹夹，出栈为子弹弹出弹夹

栈的应用

像浏览器的后退功能也是用栈来实现的，

例题

某城市有一个火车站，铁轨铺设如图。有n节车厢从A方向驶入车站，按进站的顺序编 为1～n。你的任务是判断是否能让他们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如，出栈顺序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。 为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每节车厢，一旦从A移入C，就不能返回A了;一旦从C移入B，就不能返回C了。也就是说，在任意时刻，只有两种选择：A到C和C到B。

习题巩固

题目：设计一个有getMin功能的栈

实现一个特殊的栈，在实现栈的基本功能上，再实现返回栈中最小元素的操作

要求：
1.pop，push，getMin操作的时间复杂度为O（1）
设计时候可以使用现成的栈结构

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34801 人正在系统学习中