苏州诗华洛网站建设,中国林业建设协会网站,开发网站有什么用,什么样的网站好优化目录
Day 14#xff1a;栈
一、栈的基本知识
二、栈的方法
1. 顺序表实现栈
2. 入栈
3. 出栈
三、代码及测试
拓展#xff1a;
小结 Day 14#xff1a;栈 Task#xff1a; push 和 pop 均只能在栈顶操作.没有循环, 时间复杂度为 O(1). 一、栈的基本知识 详细的介…目录
Day 14栈
一、栈的基本知识
二、栈的方法
1. 顺序表实现栈
2. 入栈
3. 出栈
三、代码及测试
拓展
小结 Day 14栈 Task push 和 pop 均只能在栈顶操作.没有循环, 时间复杂度为 O(1). 一、栈的基本知识 详细的介绍可以参考这篇学习笔记【数据结构】栈-CSDN博客。本博文中只选取部分知识点讲解。 简单来说我们可以把栈理解成一种 “运算受限” 的线性表即后进先出(Last In First Out简称LIFO)或先进后出(First In Last Out简称FILO)的原则进行的线性表因此栈又称为LIFO表或FILO表。 对于栈这种数据结构的定位我们可以从栈这个字本身出发。 “ 栈 ”是一个用于存储货物的房间就像我们古代用于旅人驻脚歇店的客栈人们不会在这久居不过是中转站罢了。 这个翻译可谓很灵性了计算机中的“ 栈 ”(Stack)也确实也可以理解为暂时存储的容器。比如在函数调用时底层编译器会把我们当前的数据放于这个临时的容器中存储避免在进入函数后当前上下文环境的信息丢失之后待到函数返回后再从Stack中取出。 当然这种数据中转存储的数据类型我们不是说都称之为栈还包括有有队列性质的高速缓存与各种正常的顺序存储的文件系统等只是说栈有些独有方面的特例。
二、栈的方法
1. 顺序表实现栈 同时需要注意的一点根据线性表的分类顺序表和链表 我们可以用这两种方式来实现栈的构建即分为顺序栈和链栈。本博文中通过顺序表来实现栈具体构造原理可以参考学习笔记这里不做展开。 /*** The depth.*/public static final int MAX_DEPTH 10;/*** The actual*/int depth;/*** The data*/char[] data;/************************ Construct an empty char stack.**********************/public CharStack() {depth 0;data new char[MAX_DEPTH];}// Of the first constructor/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString ;for (int i 0; i depth; i) {resultString data[i];} // Of for ireturn resultString;}// Of toString这里的属性与静态顺序表中的内容无差构造函数完成栈深度长度初始化空间开辟遵循静态链表开辟的方法——使用new开辟固定“MAX_DEPTH”大小的空间。 但注意栈是于栈顶一端进行删除与插入的结构而为了顺序表的实现方便我们往往在下标较大处插入因此我们定义栈顶在数组的最右侧。 所以按照从左向右打印的习惯toString()函数完成的就是栈底向栈顶的打印过程。
2. 入栈 本质上就是加入一个元素只不过位置被限定在栈顶。 从顺序表的角度来看其意义就是在顺序表的最后一个元素后面再插入一个元素。 由于位置固定所以我们只需要给末尾元素之后的空位赋值并且让栈深度1即可对于从0开始记录的任何表表长都默认值最后一个元素的下一个位置 /************************ Push an element.* * param paraChar The given char.* return Success or not.**********************/public boolean push(char paraChar) {if (depth MAX_DEPTH) {System.out.println(Stack full.);return false;} // Of ifdata[depth] paraChar;depth;return true;}// Of push对于任何顺序表的插入都不要忘记判断表满的情况因此这里先进行一次判满的判断这是栈的基本健壮性保证。 之后的入栈操作怎么写要根据你的栈顶指针的默认指向来确定。 这里我们用depth来表示栈深度同时自然也用于表示栈顶指针。这种情况的话depth默认指向的位置刚好就是尾元素后面的空位刚好可以直接插入于是可以使用 data[depth] paraChar;depth;我们可以做如下简写 data[depth] paraChar; 当然若栈顶指针假设指向末尾元素本身的话这里我们假设这个变量为top。在插入元素时需要保证栈顶指针要先移动到末尾元素后面的空位才能进行插入于是就要使用 top;data[top] paraChar;当然也可以简写成 data[top] paraChar; 习惯上我们会将入栈操作定义为 Boolean 类型这是因为布尔信息能够明确的告诉我们该操作是否成功。
3. 出栈 同顺序表一样元素删除需要先判断是否为空以保证程序的健壮性。 出栈时使用resultChar先接收栈顶数据之后再进行栈指针的下移操作实现逻辑上元素减少但是实际上这个值还是存放在原指针所指的位置的因为我们确定栈元素的多少仅依靠栈顶指针的具体值而定。 这个操作与入栈的操作是完全相逆的而且也会因为栈顶指针的含义不同而变化即栈顶指针指向栈顶有效元素的上方的一个无数据位一般我们令其值为 -1。由于这里我们采用的是 depth深度所以最小值为0但观察可知实际操作中读取的 depth - 1是等效的。 public char pop() {if (depth 0) {System.out.println(Nothing to pop.);return \0;} // Of ifchar resultChar data[depth - 1];depth--;return resultChar;}// Of pop三、代码及测试
package datastructure.stack;/*** Char stack. I do not use Stack because it is already defined in Java.** author: Changyang Hu joe03foxmail.com* date created: 2025-05-13*/
public class CharStack {/*** The depth.*/public static final int MAX_DEPTH 10;/*** The actual depth.*/int depth;/*** The data*/char[] data;/************************ Construct an empty char stack.**********************/public CharStack() {depth 0;data new char[MAX_DEPTH];}// Of the first constructor/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString ;for (int i 0; i depth; i) {resultString data[i];} // Of for ireturn resultString;}// Of toString/*** ********************** Title: push* Description: Push an element.** param paraChar The given char.* return Success or not.* return boolean **********************/public boolean push(char paraChar) {if (depth MAX_DEPTH) {System.out.println(Stack full.);return false;} // Of ifdata[depth] paraChar;depth;return true;}// Of push/*** ********************** Title: pop* Description: Pop an element.** return The popped char.* return char **********************/public char pop() {if (depth 0) {System.out.println(Nothing to pop.);return \0;} // Of ifchar resultChar data[depth - 1];depth--;return resultChar;}// Of pop/*** ********************** Title: main* Description: The entrance of the program.** param args Not used now.* return void **********************/public static void main(String args[]) {CharStack tempStack new CharStack();for (char ch a; ch m; ch) {tempStack.push(ch);System.out.println(The current stack is: tempStack);} // Of for chchar tempChar;for (int i 0; i 12; i) {tempChar tempStack.pop();System.out.println(Poped: tempChar);System.out.println(The current stack is: tempStack);} // Of for i}// Of main}// Of CharStack拓展 栈【数据结构】栈-CSDN博客 小结 通过顺序表来实现栈操作本身并不复杂只是说一些要点需要我们在使用前就想好
采用 depth指向栈顶的下一个元素还是 top指向栈顶作为下标采用顺序表来实现还是链表链表相关参考学习笔记 栈虽然本身简单但是其在数据传输中的战略地位极高。 栈实现了“ 调用 ”思想的核心。栈的临时存储与栈出数据总是最近一次栈入的数据的特性非常符合嵌套调用与返回的特性。所以如今我们使用的各种函数都用到了栈的思想任何使用函数完成的算法体系都可以使用栈完成模拟。 栈贯穿了计算机的各个邻域栈的概念在硬件中就早有使用因为栈的实现促成了操作系统的中断特性的实现而中断的特性又促成后来批处理操作系统的诞生是当代计算机的奠基石。也许毫不夸张说没有栈就没有我们如今的计算机的基础。
