| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> (王道408考研数据结构)第三章栈和队列-第一节:栈基本概念、顺序栈和链栈基本操作 -> 正文阅读 |
|
[数据结构与算法](王道408考研数据结构)第三章栈和队列-第一节:栈基本概念、顺序栈和链栈基本操作 |
文章目录一:栈基本概念(1)栈的定义栈(stack):是一种将插入和删除操作限制在一端进行的线性表。我们把允许插入和删除的一端称之为栈顶(top),另一端则称之为栈顶(bottom),不含任何数据元素的栈称之为空栈。栈中元素遵循后进先出原则
(2)压栈和出栈压栈:是栈的插入操作,也叫做进栈、入栈 出栈:是栈的删除操作,也叫做弹栈
(3)进栈出栈变化形式值得注意的是,栈对线性表的插入和删除是在位置上进行了限制,但是并没有对进出时机进行限制,也就说,在不是所有元素都进栈的情况下,事先进去的元素也可以出栈,只要保证位置是栈顶即可 比如现在有3个整型数字元素 1 1 1、 2 2 2、 3 3 3依次进栈,会有哪些出栈次序呢?
但是像 312 312 312这种情况是绝对不可能出现的。因为 3 3 3先出栈,就意味着 3 3 3曾经进栈,既然 3 3 3都进栈了,那么也就意味着 1 1 1和 2 2 2已经进栈了,此时 2 2 2一定是在 1 1 1的上面,出栈只能是 321 321 321 其实,
n
n
n个不同元素进栈,出栈元素不同排列的个数可由卡特兰(
C
a
t
a
l
a
n
Catalan
Catalan)数确定:
(4)栈的操作一个栈的基本操作如下
其它常用操作
二:栈的顺序存储结构及其操作实现(1)顺序栈的定义顺序栈:顺序栈自然而然使用数组来实现。采用下标为0的一端作为栈顶,这样的话数组尾部作为栈顶以进行插入和删除 由于尾部元素作为栈顶,也就是最后一个元素是栈顶元素,所以需要使用一个 变量
因此顺序栈结构定义如下
假定
(2)进栈进栈:进栈时,先栈顶指针+1,后进行元素赋值(若 代码如下,注意栈满判断
(3)出栈出栈:处栈时,先保存元素,后栈顶指针-1(若
代码如下,注意栈空判断
(4)读取栈顶元素代码如下
(5)共享栈顺序栈其缺点就在于事先要确定空间大小,万一不够用需要进行扩容,很是麻烦。另一种解决方法就是利用共享栈 共享栈:有两个相同类型的栈,如果一个栈空间满了,就可以借助另一个栈的空间。具体来说,可以让一个栈的栈底为“栈”始端,即数组下标0处,另一个栈为“栈”末端,即数组下标n-1处,增加元素时,就是两端点向中间延伸 不难想象,其判空和判满条件如下 判空: 判满:普通情况下, 共享栈结构定义如下
共享栈压栈代码如下,注意需要一个变量StackNumber用于标识是哪个栈进栈
共享栈出栈代码如下
三:栈的链式存储结构及其操作实现(1)链栈的定义链栈:这是栈的链式存储结构。对于单链表来说它本身就具有头指针,所以可以让头指针和栈顶指针合二为一。同时,栈顶元素就在头部,因此头结点失去意义,所以对于链栈来说是不需要头结点的 因此链栈结构定义如下
(2)进栈进栈:链栈进栈相当于单链表的插入操作
(3)出栈出栈:链栈进栈相当于单链表的删除操作
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 | -2025/1/9 1:08:26- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |