【数据结构】什么是栈?

简介: 【数据结构】什么是栈?

人生,需要有进栈出栈精神的体现.在哪里跌倒,就应该在哪里爬起来.无论陷入何等困境,只要抬头能仰望蓝天,就有希望,不断进取,你就可以让出头之日重现.困难不会永远存在,强者才能勇往直前.                                             ——封清扬

📌栈的定义

栈和队列是两种重要的线性结构.从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表操作的子集,它们是操作受限的线性表,因此,可称为限定性的数据结构.但从数据类型角度看,它们是和线性表大不相同的两类重要的抽象数据类型.

栈(stack)是限定仅在表尾进行插入和删除操作的线性表.

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈.栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构.

要理解栈这个概念,我们需要注意,首先栈是一个线性表,也就是说,栈具有线性关系,即前驱后继关系.只不过它是一种特殊的线性表而已.定义中说栈在线性表的尾部进行插入和删除操作,这里的表尾指的是栈顶,而不是栈底.

栈的插入操作,叫做进栈,也称压栈,入栈.类似于子弹入弹夹,如下图:

栈的删除操作,叫作出栈,也有的叫作弹栈.如同弹夹中的子弹出弹夹,如下图:

生活中类似于栈"先进后出"概念的东西很多,如我们平常用的抽纸,装羽毛球的球筒,装子弹的弹夹等.


📌元素进栈出栈的顺序

虽然栈的定义中规定了栈中元素必须符合先进后出的规则,但并没有对元素进出栈的时间做限制,因此最先进栈的元素,不一定就最后出栈,例如:

现在有三个整型元素1,2,3依次进栈,会有以下5种不同的出栈顺序:

第一种:1进,2进,3进.3出,2出,1出.

出栈顺序:321.

第二种:1进,1出,2进,2出,3进,3出.

出栈顺序:123

第三种:1进,2进,2出,1出,3进,3出.

出栈顺序:213

第四种:1进,1出,2进,3进,3出,2出.

出栈顺序:132

第五种:1进,2进,2出,3进,3出,1出,

出栈顺序:231


你可能会好奇,按照排列组合应该还有一个312的出栈顺序啊,为什么没写呢?别急,这是我们要重点分析的一种情况,我们把它拉出来单独分析:


首先,要出3的话,那么3肯定进栈了.按照1,2,3的进栈顺序,3进栈了,那么1,2肯定已经进栈了,所以3出栈时栈内的情况应该是这样的:

3出栈后,栈内元素情况是这样的:

可以看到,当前栈中栈顶元素为2,但我们想要出栈的元素是1,这是不可能做到的,因为按照栈的先进后出原则,我们此时只能先出2,再出1.

因此312的出栈顺序是不可能的.

根据上述对312出栈顺序的分析,我们可以得出一个结论:

即当按照由1~x的元素顺序入栈时,假设当前栈顶元素为x,则该栈不可能实现按照x,x-2,x-1顺序出栈.如下图:


📌栈的抽象数据类型

对于栈来讲,因为它的特殊性,因此在操作上相对于线性表有些变化,特别是插入和删除操作,只需要保留进栈出栈两部分.

栈的抽象数据类型如下:

ADT 栈(stack)
Data
  栈的数据对象集合为 {a1, a2, ..., an},每个元素的类型均为STDataType.
  其中, 除第一个元素a1外, 每一个元素有且只有一个直接前驱元素.
  除了最后一个元素an外, 每一个元素有且只有一个直接后继元素.
  数据元素之间的关系是一对一的关系.
Operation
  InitStack(*s);      初始化操作, 建立一个空的栈s.
    DestroyStack(*s)        若栈存在,则销毁它.
  StackEmpty(s);      若栈为空,返回true,否则返回false.
  ClearStack(*s);     将栈清空.
  GetTop(s, *e);        若栈存在且非空,用e返回s的栈顶元素.
    Push(*s,e);             若栈s存在,插入新元素e到栈s中并成为栈顶元素.
  Pop(*s,*e);             删除栈s中栈顶元素,并用e返回其值.
  StackLength(s);     返回栈s的元素个数.
endADT

📌栈的顺序存储结构

顺序栈和顺序表一样,都是使用数组来实现的,对于这种只能一头插入和删除的线性表来说,使用下标为0的一端做为栈底比较好.因为顺序表尾插和尾删的时间复杂度都是O(1),而头插和头删因为要挪动元素,所以时间复杂度为O(n).对比来看,显然是用下标为0的一端做头,然后在数组尾部进栈出栈是较优的选择.

在顺序栈中需要包含三个要素:存储数据的数组arr,顺序栈的当前存储容量capacity,顺序栈栈顶元素的位置top.

随着数据的进栈和出栈,top位置在变化的,但无论如何top也不能够比数组容量capacity还要大.因此top必须小于capacity.当栈中存在一个元素时,top=0,因此同常把空栈的判定条件设为top=-1.

若现在有一个顺序栈,capacity是5,则栈普通情况,空栈满栈的情况示意图如下:

顺序栈中,进栈和出栈的逻辑完全和顺序表的尾插尾删逻辑一样,后续我们会一起实现一个顺序栈的程序,因此在这里就不多赘述了.


📌栈的链式存储结构

栈的链式存储结构,简称为链栈.

因为栈只在栈顶插入或删除的特性,我们在设计链栈时应当把栈顶放在单链表的头部,并且对链表来说,头指针是必须的,而对链栈来说,栈顶指针同样是必须的,因此我们不如将他们合二为一.

链栈示意图:

对于链栈来说,基本不存在栈满的情况.而对空栈来说,链栈的判断条件应该是top=NULL.

链栈的进栈操作

对于链栈的进栈push操作,假设元素新结点是e,top为栈顶指针,则进栈示意图如下:

链栈的出栈操作

对于链栈的出栈pop操作,假设top为栈顶指针,则出栈示意图如下:


📌栈的应用(待补)

🎏递归

🎏括号匹配问题

🎏四则运算表达式求值


结语

当我们了解了栈的定义后,接下来我们将一起实现一个顺序栈程序,由于篇幅有限,我会在下篇博客中为大家详细介绍一下顺序栈的实现,感兴趣的话可以点击下面链接查看:

http://t.csdnimg.cn/ksbBH

希望这篇有关数据结构栈的介绍文章能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!



数据结构栈和队列篇思维导图


相关文章
|
15天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
6天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
15 1
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
14天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
41 4
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
30 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
18天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
初步认识栈和队列
初步认识栈和队列
58 10
|
1月前
数据结构(栈与列队)
数据结构(栈与列队)
17 1
|
1月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
44 3

热门文章

最新文章