关键词：
栈
定义
栈是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端有其特殊含义，称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈顶实现元素的进出，栈的修改遵循后进先出的原则。因此，栈又称为后进先出（last in first out）的线性表（简称LIFO结构）。
表示及实现
栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：
- 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
- 链栈：采用链式存储结构实现栈结构；
顺序栈
顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
先为栈分配一个基本容量，然后在应用的过程中，当栈的空间不够使用时za再逐段扩大。为此可设定两个常量：STACK_INIT_SIZE（存储空间初始分配量）和STACKINCREMENT(存储空间分配增量)，并以下述类型说明作为顺序栈的定义。
typedef struct
int *base;//类型要看元素是什么类型
int *top;
int stacksize; // 当前栈可使用的最大容量。
Sqstack;
top=base可作为栈空的标记。每当插入新元素时，指针top+1；删除时，指针top-1；因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
链栈
栈的操作即在单链表操作基础上，push则是在头结点前添加元素，pop则是删除头结点。
应用举例
数制转换
def number_base_conversion(input_number: int, base=8):
stack = LinkedStack()
while input_number:
input_number, r = divmod(input_number, base)
stack.push(r)
out_put_lis = []
data = stack.pop()
while data is not None:
out_put_lis.append(str(data))
data = stack.pop()
return ‘‘.join(out_put_lis)
括号匹配的校验
def brackets_matching_check(input_brackets: str):
"""核心: 期待的紧迫程度，利用栈"""
def pair_brackets(a: str, b: str):
return True if a + b in [‘()‘, ‘[]‘] else False
left_bracket_lis = [‘(‘, ‘[‘]
right_bracket_lis = [‘)‘, ‘]‘]
stack = LinkedStack()
for bracket in input_brackets:
if bracket not in left_bracket_lis + right_bracket_lis:
return "invalid input"
if bracket in left_bracket_lis:
stack.push(bracket)
elif bracket in right_bracket_lis:
bracket_to_pair = stack.pop()
if not pair_brackets(bracket_to_pair, bracket):
return False
if stack.pop():
return False
else:
return True
行编辑程序
def line_editor():
"""
这个输入缓冲区为一个stack，每当从终端接受一个字符之后，
判断：
如果它既不是退格符(#)也不是退行符(@),则将该字符压入栈顶；
如果它是一个退格符(#)stack出栈一个字符；
如果它是一个退行符(@)清空stack；
:return:
"""
codes = []
s = input()
stack = LinkedStack()
while s:
if s == ‘EOF‘:
return ‘
‘.join(codes)
for char in s:
if char in [‘#‘, ‘@‘]:
if char == ‘#‘:
stack.pop()
else:
while not stack.is_empty():
stack.pop()
else:
stack.push(char)
line_code = []
while not stack.is_empty():
line_code.insert(0, stack.pop())
codes.append(‘‘.join(line_code))
s = input()
return ‘
‘.join(codes)
迷宫求解
"""
do
if 当前位置可通:
则
将当前位置插入栈顶；
若该位置是出口位置，则结束；
否则切换当前位置的东邻方块为新的当前位置；
else:
if 栈不空且栈顶位置尚有其他方向未经探索；
则 设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若 栈不空但栈顶位置的四周均不通
则
删去栈顶位置；
若栈不为空，则重新测试新的栈顶位置，直到找到一个可通的相邻块或出栈至空
while (栈不空)
"""
表达式求值
栈与递归的实现
递归函数
一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数
在高级语言编制的程序中，调用函数与被调用函数之间的链接及信息交换需通过栈来进行。
通常在一个函数运行期间调用另一个函数时，在运行被调用函数之前，系统需完成三件事：
- 将所有的实在参数，返回地址等信息传递给被调用函数保存。
- 为被调用函数的局部变量分配储存区。
- 将控制转移到被调函数入口
从被调函数返回调用函数之前，系统完成三件工作：
- 保存被调函数计算结果
- 释放被调用函数的数据区
- 依照被调用函数保存的返回地址将控制转移到调用函数。
递归函数运行过程类似多个函数的嵌套调用，只是调用与被调用函数为同一个，因此，和每次调用相关的一个重要概念是递归函数运行的层次。
从0层开始调用则进入1层，从i层调用进入i+1层，返回则是返回上一层，即层级递减。为了保证递归函数的正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有局部变量以及上一层的返回地址。每进入一层，则产生一个新的记录压入栈顶。没退出一层，则弹出一个。当前执行层的工作记录必须是递归栈顶的工作记录，称这个记录为“活动的记录”。
队列
定义
队列(queue)是一种先进先出(first in first out, FIFO)的线性表，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一端叫做队尾(rear/tail), 允许删除的一端则称队头(front)
链队列
用链表表示的队列，称为链队列
一个链队列显然需要两个分别指示队头和队尾的指针才能唯一确定。为了操作方便，我们也给队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件是头指针和尾指针均指向头结点
相关实现代码见queues.py
循环队列
与顺序栈类似，在队列的顺序结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分贝指示队列头元素及队列尾元素的位置。
用此方法表示循环队列，就无法用Q.front=Q.rear来判断队列空间是空还是满。可有两种处理方法：
- 另设一个标志位以区别队列是空还是满
- 少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置上”作为队列呈满状态的标志
相关实现代码见queues.py
数据结构与算法--栈和队列(代码片段)
栈定义栈是限定仅在表尾进行插入或删除操作的线性表。因此对栈来说，表尾端有其特殊含义，称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈顶实现元素的进出，栈的修改遵循后进先出的原则。因此，栈又称为后进... 查看详情
《数据结构与算法》-3-栈和队列(代码片段)
...构4.3矩阵的压缩存储?该系列博客的目的是为了学习一遍数据结构中常用的概念以及常用的算法，为笔试准备；主要学习过程参考王道的《2018年-数据结构-考研复习指导》；已总结章节：《数据结构与算法》-1-绪论《数据结构与... 查看详情
考研数据结构与算法栈和队列(代码片段)
文章目录一、栈1.1顺序栈1.1.1顺序栈代码实现1.1.1.1初始化1.1.1.2判栈空1.1.1.3进栈1.1.1.4出栈1.1.1.5读栈顶元素1.2链栈1.2.1链栈的代码实现1.2.1.1初始化1.2.1.2判栈空1.2.1.3进栈1.2.1.4出栈1.2.1.5读取栈顶元素1.3共享栈1.4实际应用1.4.1进制转... 查看详情
博客作业03--栈和队列(代码片段)
...学习中比较重要的知识点关键词。重要的知识点关键词：数据结构、复杂度、抽象数据类型、线性表、栈和队列、串、算法、逻辑结构、存储结构、基本运算等；1.2使用思维导图将这些关键词组织起来。2.PTA实验作业2.1题目名称... 查看详情
数据结构(c语言版)栈和队列算法设计demo7(代码片段)
假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法... 查看详情
数据结构——栈和队列相关算法实现(代码片段)
数据结构栈和队列的基本算法实现限定性线性表——栈栈的定义栈作为一种限定性的线性表，是将线性表的插入和删除操作限制为仅在表的一端进行。基本算法演示/*栈的常见操作：1.初始化栈2.元素进栈3.元素出栈4.栈的遍历5.判... 查看详情
clanguage栈和队列-顺序队列(代码片段)
...建结构体structSqQueue intdata[MaxSize]; intfornt,rear;;-初始化队列算法：//初始化voidinitQueue(SqQueue*&s) 查看详情
数据结构与算法系列研究二——栈和队列
...关问题分析一、栈和队列定义 栈和队列是两种重要的数据结构。从结构特性角度看，栈和队列也是线性表，其特殊性在于它们的基本操作是线性表的子集，是操作受限的线性表，可称为限定性的数据结构；从数据类型角度看... 查看详情
[数据结构]栈和队列的内容分析与讲解(代码片段)
[数据结构]栈和队列的内容分析与讲解一、前言二、栈三、栈的常见接口3.1栈的定义3.2栈的初始化3.3栈的销毁3.4栈的插入元素3.5栈的删除元素3.6栈的长度3.7栈的判空3.8栈的栈顶元素获取四、队列五、常见接口5.1队列的定义5.2队列... 查看详情
栈和队列----算法(代码片段)
一、题目：生成窗口最大值数组(要求时间复杂度为O(N))有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。思路：来自https://blog.csdn.net/qq_32583189/article/details/53055618?utm_source=copy滑动窗... 查看详情
java集合与数据结构栈和队列(代码片段)
Java集合与数据结构栈和队列栈(Stack)基本方法栈的习题出栈顺序不可能中缀表达式转后缀表达式（逆波兰式）手动实现栈队列(Queue)基本方法链表实现队列循环队列用队列实现栈用栈实现队列括号匹配问题实现一个最小栈... 查看详情
java集合与数据结构栈和队列(代码片段)
Java集合与数据结构栈和队列栈(Stack)基本方法栈的习题出栈顺序不可能中缀表达式转后缀表达式（逆波兰式）手动实现栈队列(Queue)基本方法链表实现队列循环队列用队列实现栈用栈实现队列括号匹配问题实现一个最小栈... 查看详情
算法和数据结构解析-8:栈和队列相关问题(代码片段)
1.栈和队列数据结构1.1栈（Stack）栈（Stack）又名堆栈，它是一种重要的数据结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，... 查看详情
clanguage栈和队列-链队列(代码片段)
...next;Qnode;typedefstruct Qnode*front; Qnode*rear;LinkQuNode;初始化队列算法：//初始化队列voi 查看详情
数据结构与算法栈与队列c语言版(代码片段)
目录3.1栈和队列的定义和特点3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的... 查看详情
数据结构10：栈和队列(代码片段)
数据结构栈(Stack)和队列(Queue)详解本章讲解了两种特殊的线性表结构——栈和队列。读者要重点理解栈的“先进后出”原则和队列的“先进先出”原则，体会两种特殊的线性表结构的应用场景。本章内容：1.栈(S... 查看详情
数据结构(c语言版)栈和队列算法设计demo8(代码片段)
如果允许在循环队列的两端都可以进行插入和删除操作。要求：①写出循环队列的类型定义；②写出“从队尾删除”和“从队头插入”的算法。[题目分析]用一维数组v[0…M-1]实现循环队列，其中M是队列长度。设队头... 查看详情
数据结构与算法-栈和队列
一、简介众所周知，线性表是数据结构的基础，通常有两种实现方式：数组和链表。栈和队列是最常用的数据结构，它们基于线性表实现。 二、栈定义：栈是限定仅在表尾进行插入和删除操作的线性表，即FILO。栈被经常类... 查看详情