数据结构--栈

文章目录

栈
- 1、栈的基本概念
- 2、栈的常见基本操作
- 3、栈的实现
- - 1.栈的顺序存储（顺序栈）
  - 2.栈的链式存储（链栈）
  - 3.链栈与顺序栈的区别
- 4.栈的应用
- - 1.斐波那契数列
  - 2.四则运算表达式求值
  - 3.汉诺塔问题
  - 4.其他

栈

为什么要有栈？

使用寄存器来对数据进行临时存储，在小程序中固然可行，但若程序稍大些、复杂些，剩余的寄存器也不够我们使用的，所以引出使用内存空间来对数据进行暂存。但是这种方式会造成困扰，要记得每个临时性数据在什么地方存储不是容易的事情，也不便于维护，这样很不方便使用。最后引出栈的使用，开辟一个内存空间用做栈段，通过push和pop操作便捷地对临时性数据进行暂存，解放了程序猿要记忆和寻找数据内存地址的痛苦过程。

1、栈的基本概念

栈（Stack）：是只允许在一端进行插入或删除的线性表

常见的栈实现方式有数组和链表两种，其中数组实现的栈又称为顺序栈，链表实现的栈称为链式栈。

在这里插入图片描述

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构

2、栈的常见基本操作

push（入栈）：将元素压入栈顶
pop（出栈）：弹出栈顶元素，并删除
isEmpty（判断栈是否为空）：返回布尔值
peek（查看栈顶元素）：查看栈顶元素，不删除
search（查找）：从栈顶开始搜索元素在栈中的位置，如果找到则返回其距离栈顶的位置（栈顶为1），如果未找到则返回-1
clear(清空)：对当前栈进行清空

import java.util.Stack;public class StackExample {public static void main(String[] args) {//创建一个整型的栈Stack<Integer> stack = new Stack<>();//入栈：压入元素到栈中stack.push(10);stack.push(20);stack.push(30);System.out.println("栈内元素为：" +stack);// 弹出栈顶元素，并删除int poppedElement = stack.pop();System.out.println("栈顶元素为：" + poppedElement);System.out.println("此时栈内元素为："+stack);// 查看栈顶元素，但不删除int peekedElement = stack.peek();System.out.println("栈顶元素为：" + peekedElement);System.out.println("此时栈内元素为："+stack);// 判断栈是否为空boolean empty = stack.isEmpty();System.out.println("栈是否为空： " + empty);// 搜索元素在栈中的位置int position1 = stack.search(20);int position2 = stack.search(10);int position3 = stack.search(30);System.out.println("20在栈中的位置: " + position1);System.out.println("10在栈中的位置: " + position2);System.out.println("30在栈中的位置: " + position3);}}

运行结果：

栈内元素为：[10, 20, 30]
栈顶元素为：30
此时栈内元素为：[10, 20]
栈顶元素为：20
此时栈内元素为：[10, 20]
栈是否为空： false
20在栈中的位置: 1
10在栈中的位置: 2
30在栈中的位置: -1

3、栈的实现

1.栈的顺序存储（顺序栈）

它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。

当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位 top = -1

若现在有一个栈，StackSize是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：

在这里插入图片描述

package Stack;public class SortStack {public Object[] data;   // 数组表示栈内元素public int maxSize;     // 栈空间大小public int top;         // 栈顶指针(指向栈顶元素)/*** 初始化栈的长度* @param initialSize*/public SortStack(int initialSize){if(initialSize>=0){this.data=new Object[initialSize];this.maxSize=initialSize;this.top=-1;}else{System.out.println("栈初始化失败!");}}/*** 判断栈是否为空* @return*/public boolean isEmpty(){return top == -1 ? true : false;}/*** 判断是否栈满* @return*/public boolean isFull(){return top == maxSize-1 ? true : false;}/*** 入栈操作* 先判断是否栈满* @param value*/public void push(Object value){if(!isFull()){System.out.print(value+"入栈   ");data[++top]=value;}else{System.out.println("满栈，无法进行入栈操作!");}}/*** 出栈操作* 先判断是否为空栈* @return*/public Object pop(){Object num=null;if(!isEmpty()){num = data[top--];return num;}else{return "空栈，无法进行出栈操作!";}}/*** 获取栈顶元素* @return*/public Object getPeek(){if(top>=0){return data[top];}else{return "栈顶指针为空，无栈顶元素!";}}/*** 打印栈内元素*/public void displayStack(){// 栈顶指针不为—1，栈内有元素，进行打印if(top>=0){for(int i=top;i>=0;i--){System.out.print(data[i] + " ");}System.out.println();}else{System.out.println("栈内元素为空！");}}/*** 获取栈顶指针为n的栈内元素* @param n* @return*/public Object getPeekN(int n){if(n<=top){return data[n];}else{return "error";}}public static void main(String[] args) {SortStack stack=new SortStack(3);System.out.println("栈顶元素为："+stack.getPeek());System.out.println("栈是否为空："+stack.isEmpty());System.out.println("是否为满栈："+stack.isFull());System.out.println("*********入栈*********");stack.push(1);stack.push('A');stack.push(5);stack.push("hello");System.out.println("*********判断栈内情况*********");System.out.println("栈是否为空："+stack.isEmpty());System.out.println("是否为满栈："+stack.isFull());System.out.println("栈顶指针为："+stack.top);System.out.println("********出栈**********");System.out.println("出栈前的栈顶元素为："+stack.pop());System.out.println("出栈后的栈顶元素为："+stack.getPeek());System.out.println("栈顶指针为："+stack.top);System.out.println("********此时栈内情况**********");System.out.println("栈顶元素为："+stack.getPeek());System.out.println("栈顶指针为1的栈内元素:"+stack.getPeekN(1));System.out.println("栈顶指针为2的栈内元素:"+stack.getPeekN(2));System.out.println("栈是否为空："+stack.isEmpty());System.out.println("是否为满栈："+stack.isFull());System.out.println("*******打印栈内元素***********");System.out.print("栈内元素为：");stack.displayStack();System.out.println("栈顶指针为："+stack.top);}}

运行结果：

栈顶元素为：栈顶指针为空，无栈顶元素!
栈是否为空：true
是否为满栈：false
*********入栈*********
1入栈   A入栈   5入栈   满栈，无法进行入栈操作!
*********判断栈内情况*********
栈是否为空：false
是否为满栈：true
栈顶指针为：2
********出栈**********
出栈前的栈顶元素为：5
出栈后的栈顶元素为：A
栈顶指针为：1
********此时栈内情况**********
栈顶元素为：A
栈顶指针为1的栈内元素:A
栈顶指针为2的栈内元素:error
栈是否为空：false
是否为满栈：false
*******打印栈内元素***********
栈内元素为：A 1 
栈顶指针为：1

2.栈的链式存储（链栈）

链栈的空间可以是不连续分配，规定链表中的插入和删除运算只能在**链表开头（首结点）**进行

链栈的实现使用单链表来实现，链表的存储单元包含有两部分，一个是数据域用以存储数据，一个是指针域用以指向下一个结点

在这里插入图片描述

一个标准的链栈具有如下的基本操作：

1、初始化链栈

2、销毁链栈

3、清空链栈

4、检测链栈是否为空

5、返回链栈中的元素个数

6、返回链栈的栈顶元素，不修改栈指针

7、向链栈顶压入元素

8、从链栈顶弹出元素

9、从栈底到栈顶遍历链栈

class Stack{/*定义两个指针目的是分别指向栈底和栈顶*/private Element base ;private Element top ;/*栈中的数据模型*/class Element{public Object data ;                     //栈中元素Element next ;                           //下一个元素}/*初始化*/public void init(){Element elem = new Element() ;           //开辟一个元素的空间作为栈底base = elem ;                            //top指针和base指针初始化top =  elem ;base.data = null ;System.out.println("栈已初始化");}/*压栈操作*/public void push(Object obj){Element elem = new Element() ;           // 入栈元素分配空间elem.data = obj ;                        // 将元素放入elem.next = top ;                        // 元素指针指向当前top所指元素top = elem ;                             // 修改top指针System.out.println(top.data+" 压栈成功");}/*退栈操作*/public Object pop(){if(this.isEmpty()){System.out.println("退栈失败，栈为空！");return null ;}Object obj = top.data ;                   //取出对象的值top = top.next ;                          //修改top指针System.out.println(obj+" 退栈成功");return obj ;                              //返回元素}/*判断栈是否为空*/public boolean isEmpty(){if(base == top)                           //若栈顶栈底指针相同，则为空否则非空return true ;elsereturn false ;}/*清空栈*/public void clear(){while(!this.isEmpty()){this.pop() ;}System.out.println("栈已清空");}/*获取栈的大小*/public int size(){int n = 0 ;Element flag = top ;while(flag!=base){flag = flag.next ;n++ ;}return n ;}/*获取栈顶元素*/public void getTop(){System.out.println("栈顶元素为："+top.data);}/*遍历栈，输出栈的元素*/public void print(){if(this.isEmpty()){                        //若栈空System.out.println("输出失败，栈为空！");}else{Element flag = top ;System.out.print("栈中元素为：");while(flag != base){System.out.print(flag.data+" ");flag = flag.next ;}}}
}

测试：

public static void main(String[] args) {Stack stack = new Stack();// 不断地入栈System.out.println("*********入栈***********");stack.push("aaaa");stack.push("bbbb");stack.push("cccc");stack.push("dddd");System.out.println("*********栈内元素***********");stack.print();System.out.println("\n栈的大小为："+stack.size());System.out.println("*********访问栈顶元素***********");// 访问栈顶元素stack.getTop();// 弹出一个元素System.out.println("*********出栈***********");System.out.print("第一次弹出栈顶元素：");stack.pop();System.out.print("此时");stack.print();// 再次弹出一个元素System.out.print("\n第二次弹出栈顶元素：" );stack.pop();System.out.print("此时");stack.print();System.out.println("\n*********两次pop之后的栈***********");stack.print();System.out.println("\n栈的大小为："+stack.size());System.out.println("*********清空栈***********");stack.clear();System.out.println("栈是否为空："+stack.isEmpty());System.out.println("此时栈的大小为："+stack.size());}

运行结果：

*********入栈***********
aaaa 压栈成功
bbbb 压栈成功
cccc 压栈成功
dddd 压栈成功
*********栈内元素***********
栈中元素为：dddd cccc bbbb aaaa 
栈的大小为：4
*********访问栈顶元素***********
栈顶元素为：dddd
*********出栈***********
第一次弹出栈顶元素：dddd 退栈成功
此时栈中元素为：cccc bbbb aaaa 
第二次弹出栈顶元素：cccc 退栈成功
此时栈中元素为：bbbb aaaa 
*********两次pop之后的栈***********
栈中元素为：bbbb aaaa 
栈的大小为：2
*********清空栈***********
bbbb 退栈成功
aaaa 退栈成功
栈已清空
栈是否为空：true
此时栈的大小为：0

3.链栈与顺序栈的区别

顺序栈底层是数组，最大空间容量受到限制，因此必须初始化一个数组的容量，也就是栈的容量，链栈则无需此操作
顺序栈的入栈操作是直接根据头指针将数据加入到数组指定的下标位置，链栈的入栈则是直接在首结点插入
链栈在入栈前不需要判断栈是否满,在出栈后需要释放出栈元素的栈顶空间
顺序栈是通过头指针直接拿到下标为头指针的数组元素，链栈则是直接将链表的头部删除返回
对比链栈和顺序栈的实现，可以发现入栈和出战方法的时间复杂度都是O(1)，效率上没有区别，但是顺序栈占用的空间会相对更多

一些，顺序栈是通过指针指向假设的栈顶，其他元素其实依然存在，但链栈的栈顶之前的元素会被垃圾回收，因此链栈的实现综合时间和空间来看，更优秀一些。

4.栈的应用

1.斐波那契数列

斐波那契数列数列有一个明显的特点，即：前面两项之和，构成了后一项。

在这里插入图片描述

package Stack;public class FibonacciSequence {public static void main(String[] args) {for(int i=0;i<20;i++){System.out.print(recursive(i)+"\t");}
//        cycle();}//递归实现public static int recursive(int i) {if (i <= 1) {return i == 0 ? 0 : 1;}else{return recursive(i-1)+recursive(i-2);}}//数组迭代实现public static void cycle() {int i;int[] arr = new int[20];arr[0] = 0;System.out.println(arr[0]);arr[1] = 1;System.out.println(arr[1]);for (i = 2; i < 20; i++) {arr[i] = arr[i - 1] + arr[i - 2];System.out.print(arr[i]+"\t");}}
}

运行结果：

0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

2.四则运算表达式求值

中缀表达式转后缀表达式

后缀表达式计算结果

3.汉诺塔问题

package Stack;
import java.util.Stack;public class HanoiTower {public static void main(String[] args) {int n = 3; // 汉诺塔的盘子数hanoi(n, 'A', 'B', 'C');}public static void hanoi(int n, char from, char temp, char to) {Stack<HanoiStep> stack = new Stack<>(); // 用栈来模拟汉诺塔的移动步骤// 先将初始问题压入栈中stack.push(new HanoiStep(n, from, temp, to));while (!stack.isEmpty()) {HanoiStep step = stack.pop();if (step.n == 1) {// 将盘子直接从起始柱子移动到目标柱子System.out.println("Move disk 1 from " + step.from + " to " + step.to); } else {// 将大问题分解为三个子问题，并依次压入栈中// 将n-1个盘子从temp柱子移动到to柱子stack.push(new HanoiStep(step.n - 1, step.temp, step.from, step.to)); // 将最后一个盘子从起始柱子移动到目标柱子stack.push(new HanoiStep(1, step.from, step.temp, step.to)); // 将n-1个盘子从from柱子移动到temp柱子stack.push(new HanoiStep(step.n - 1, step.from, step.to, step.temp)); }}}static class HanoiStep {int n; // 当前盘子数char from, temp, to; // 起始柱子、中转柱子、目标柱子public HanoiStep(int n, char from, char temp, char to) {this.n = n;this.from = from;this.temp = temp;this.to = to;}}
}

运行结果：

Move disk 1 from A to C
Move disk 1 from A to B
Move disk 1 from C to B
Move disk 1 from A to C
Move disk 1 from B to A
Move disk 1 from B to C
Move disk 1 from A to C