《大话数据结构》笔记(4-1)--栈与队列:栈

栈的Java实现代码:

https://github.com/Lyu0709/data-structure/blob/master/src/com/coding/basic/stack/Stack.java

逆波兰算法实现:

https://github.com/Lyu0709/data-structure/blob/master/src/com/coding/basic/stack/RPN.java

第四章  栈与队列

定义

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。

栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。

栈的插入操作叫做进栈,也称压栈、入栈。

栈的删除操作叫做出栈。

3个整型数字元素1、2、3依次进栈,会有5种出栈次序:

1) 1,2,3进,3,2,1出。出栈次序为321.

2) 1进1出,2进2出,3进3出。出栈次序为123.

3) 1进,2进2出,3进3出,1出。出栈次序为231.

4) 1进,2进,2出,1出,3进3出。出栈次序为213.

5) 1进,1出,2进,3进,3出,2出。出栈次序为132.

栈的抽象数据类型

上一章讨论了线性表的顺序存储和链式存储,对于栈来说,也是同样适用的。

栈的顺序存储结构及实现

栈是线性表的特例,栈的顺序存储其实是线性表顺序存储的简化,简称为顺序栈。

栈的结构定义

栈的顺序存储结构——进栈操作:O(1)

栈的顺序结构——出栈操作:O(1)

两栈共享空间

关键思路:两个具有相同数据类型的栈在数组的两端,向中间靠拢。

top1=-1时,栈1为空;top2=n时,栈2为空。当top1+1=top2时,栈满。

两栈共享空间的结构代码

入栈

出栈

使用这样的数据结构,通常都是当两个栈的空间需求有相反关系时,即一个栈增长时另一个栈在缩短的情况。

栈的链式存储结构及实现

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

入栈:O(1)

出栈:O(1)

如果栈的使用过程中元素变化不可预料,则用链栈;反之,如果元素的变化在可控范围内,则用顺序栈。

栈的引入简化了程序设计的问题,划分了不同的关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题的核心。

栈的应用——递归

把一个直接调用自己或通过一系列的调用语句间接调用自己的函数,称作递归函数

每个递归定义必须至少有一个条件,满足时递归不再进行。

迭代和递归的区别:

1. 迭代使用的是循环结构,递归使用的是选择结构。

2. 递归能使程序的结构更清晰,但大量的递归调用会建立函数的副本,消耗大量的时间和内存;迭代不需要反复调用函数和占用额外的内存。

存储某些数据,并在后面又以存储的逆序恢复这些数据,以提供之后使用的需求,显然很符合栈这样的数据结构。

在递归的前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中;在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

栈的应用——四则运算表达式求值

后缀(逆波兰 Reverse Polish Notation)表示法定义

四则运算中括号成对出现,碰到左括号,就将此左括号进栈,不管表达式有多少重括号都如此,碰到左括号就将此左括号进栈。后面出现右括号时,就让栈顶的左括号出栈,期间让数字运算。这样,最终有括号的表达式从左到右巡查一遍,栈应该是由空到有元素,最终再因全部匹配成功后成为空栈的结果。

后缀表达式:所有的符号都在运算数字的后面出现。

比如:9+(3-1)*3=10/2 化为后缀表达式为:9 3 1 - 3 * + 10 2 / +

后缀表达式计算结果

后缀表达式:9 3 1 - 3 * + 10 2 / +

规则:从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号就将处于栈顶的两个数字出栈,一直到最终获得结果。

中缀表达式转后缀表达式

平时所用的标准四则运算表达式叫做中缀表达式。

规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号则栈顶元素一次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

时间: 04-28

《大话数据结构》笔记(4-1)--栈与队列:栈的相关文章

图的基础算法(大话数据结构笔记)

概述 线性表的每个元素有线性关系,每个数据元素只有一个直接前去和一个直接后继.树的数据元素之间有着明细那的层次关系,并且每层上的数据元素可能和下一层中多个元素相关,但只能和上一层中一个元素相关.这和一对父母可以有很多孩子,但每个孩子却只能有一对父母是一个道理.可现实中,人与人之间关系复杂,不是简单一对一,一对多的关系.这种复杂关系更适合用图来表示.在图结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.如下图所示:无向边:Edge (vi,vj)有向边:也叫弧,Arc. <v

第三章:1.栈和队列 -- 栈的表示及实现

前言: 栈和队列 是两种重要的线性结构.从数据结构角度来看,栈和队列也是线性表,它的特殊性在于其操作是线性表的子集,是操作受限的线性表,因此可以称作限定性的数据结构. (限定性:如.人为的规定线性表只能从表尾插入和删除结点数据元素,那么这样的线性表就是栈) 目录: 1.栈 2.栈的应用举例 3.栈与递归的实现 4.队列 5.离散事件模型 正文: 栈的定义 栈(stack) 如上所说,就是限定只能在表尾进行插入和删除的线性表.表尾 称为 栈顶(top), 表头 称为 栈底 (bottom),没有数

第4章 栈与队列-----栈

栈 (stack)是限定仅在表尾进行插入和删除操作的线性表.   允许插入和删除的一端称为栈顶(top),另一端为栈底(bottom),不含任何数据元素的栈称为空栈.栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构. 栈的抽象数据类型   实例:StaticSize是5,则栈普通情况.空栈和栈满的情况示意图如图4-4-2所示   栈的顺序存储结构----进栈操作 栈的顺序存储结构---出栈操作  栈的链式存储结构,简称链栈   栈的链式存储结构---进栈操作 栈的

数据结构-王道2017-第3章 栈和队列-栈和队列的应用

1.前中后缀表达式的转换: 举例说明将自然表达式转换成二叉树: a×(b+c)-d ① 根据表达式的优先级顺序,首先计算(b+c),形成二叉树 ②然后是a×(b+c),在写时注意左右的位置关系 ③最后在右边加上 -d 然后最这个构造好的二叉树进行遍历,三种遍历的顺序分别是这样的: ① 前序遍历:根-左-右 ② 中序遍历:左-根-右 ③ 后序遍历:左-右-根 前缀表达式:-*a+bcd 中缀表达式:a*b+c-d 后缀表达式:abc+*d- 2.队列在层次遍历二叉树中起作用,且在计算机系统中应用非

剑指offer-面试题9-用两个栈实现队列-栈和队列

/* 题目: 用两个栈实现一个队列.队列声明如下. */ /* 思路: 将值压入stack1,再从stack1弹出到stack2,则为先进先出. appendTail时直接压入stack1即可,当stack2没有可用于deleteHead的元素时,将stack1的元素全部压入stack2. */ template<typename T> class CQueue{ public: CQueue(void) ~CQueue(void); void appendTail(const T&

剑指offer-用两个栈实现队列-栈和队列-python

题目描述 用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. # -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): # write code here self.stack1.append(node) return self.stack1 def pop(self): # return x

05 1 栈与队列 栈的实现与Stack类

1 /// <summary> 2 /// 自定义栈 3 /// </summary> 4 class CStack { 5 6 /// <summary> 7 /// 存储数据的数组 8 /// </summary> 9 private ArrayList m_arrayList; 10 /// <summary> 11 /// 栈顶索引 12 /// </summary> 13 private int m_top; 14 15 p

第三章:2.栈和队列 -- 栈的应用举例

前言: 本节为栈的应用举例,只包括代码实现部分 目录: 2.栈的应用举例 进制转换: 括号匹配: 正文: 进制转换实现代码: 注意:此函数要和上一节,栈的实现代码放在一起 //进制转换 void conversion(){ SqStack S; InitStack(S); int num; printf("%s","请输入一个十进制数:"); scanf("%d",&num); while(num){ Push(S,num%8); num

数据结构看书笔记(四)--栈与队列

栈与队列 栈是限定尽在表尾进行插入和删除操作的线性表  队列是只允许在一端进行插入操作.而在另一端进行删除操作的线性表栈的定义: 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表 其中允许插入的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈.栈又称为先进后出(Last In First Out)的线性表,简称为LIFO结构. 特殊之处在与限制了这个线性表的插入和删除位置只能是在栈顶.  栈的插入操作,叫做进栈,也称为压栈.入栈. 栈的删除操作,叫做出