08_栈

一、问题引入

请输入一个表达式

计算式：[7x2x2-5+1-5+3-3]，点击计算（如图所示） 请问：计算机底层是如何运算得到结果的?注意不是简单的把算式列出运算,因为我们看这个算式7x2x2-5+1-5+3-3，但是计算机怎么理解这个算式的(对计算机而

言，它接收到的就是一个字符串)，我们讨论的就是这个问题 --> 栈

二、栈的介绍

​ 1）栈的英文为(stack)；

​ 2）栈是一个先入后出(FILO-First In Last Out)的有序列表；

​ 3）栈(stack)是限制线性表中元素的插入和删除，只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)；

​ 4）根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

​ 5）图解出栈与入栈的概念：

三、栈的应用场景

​ 1）子程序的调用:在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

​ 2）处理递归调用:和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

​ 3）表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。

​ 4）二叉树的遍历。

​ 5）图形的深度优先(depth-first)搜索法。

四、数组模拟栈

4.1 思路分析

​ 1）使用数组来模拟栈

​ 2）定义一个top来表示栈顶，初始化为-1

​ 3）入栈的操作，当有数据加入到栈时，top++;stack[top]=data;

​ 4）出栈的操作，int value = stack[top];top–;return value;

数组模拟栈思路分析图

4.2 代码实现

public class ArrayStackDemo { public static void main(String[] args) { //验证数组模拟栈的正确性 //先创建一个ArrayStack对象 ArrayStack arrayStack = new ArrayStack(5); arrayStack.list(); arrayStack.push(10); arrayStack.push(20); arrayStack.push(30); arrayStack.push(40); arrayStack.push(50); arrayStack.push(60); arrayStack.list(); int value = arrayStack.pop(); System.out.println(value); arrayStack.list(); } } //定义一个ArrayStack类表示栈结构 class ArrayStack{ private int maxSize; //栈的大小 private int[] stack; //数组，数组模拟栈，数据就放在该数组中 private int top = -1; //top表示栈顶，初始化为-1 //构造器 public ArrayStack(int maxSize){ this.maxSize = maxSize; stack = new int[this.maxSize]; } //判断栈满 public boolean isFull(){ return top == maxSize - 1; } //判断栈空 public boolean isEmpty(){ return top == -1; } //入栈-push public void push(int value){ //判断栈是否已满 boolean flag = isFull(); if (flag){ System.out.println("该栈已满，无法插入数据！"); }else{ System.out.println("该栈未满，可以插入数据！"); top++; stack[top] = value; } } //出栈-pop public int pop(){ //判断栈是否为空栈 boolean flag = isEmpty(); if (flag){ throw new RuntimeException("该栈已空，无法弹出数据！"); }else { System.out.println("该栈未空，可以弹出数据！"); int value = stack[top]; top--; return value; } } //显示栈的所有元素--遍历栈（遍历时需要从栈顶开始显示数据） public void list(){ //判断栈是否为空 if (isEmpty()){ System.out.println("该栈已空，无法弹出数据！"); System.out.println("-------------------"); return; } for (int i = top; i >= 0; i--) { System.out.println("stack["+ i + "] = " + stack[i] + " "); } System.out.println("-------------------"); } }

五、链表模拟栈

5.1 代码实现

public class LinkedListStackDemo { public static void main(String[] args) { //验证单链表模拟栈的正确性 //先创建一个LinkedListStack对象 LinkedListStack linkedListStack = new LinkedListStack(new SingleLinkedList()); linkedListStack.showStack(); linkedListStack.push(10); linkedListStack.push(20); linkedListStack.push(30); linkedListStack.showStack(); int value = linkedListStack.pop(); System.out.println(value); linkedListStack.showStack(); } } //定义一个LinkedListStack类表示栈结构 class LinkedListStack{ private SingleLinkedList list; public LinkedListStack(SingleLinkedList list) { this.list = list; } //判断栈空 public boolean isEmpty(){ return list.getLength() == 0; } //入栈-push public void push(int value){ Node node = new Node(value,null); list.add(node); } //出栈-pop public int pop(){ //判断栈是否为空栈 boolean flag = isEmpty(); if (flag){ throw new RuntimeException("该栈已空，无法弹出数据！"); }else { System.out.println("该栈未空，可以弹出数据！"); return list.delete(); } } //显示栈的所有元素--遍历栈（遍历时需要从栈顶开始显示数据） public void showStack(){ //判断栈是否为空 if (isEmpty()){ System.out.println("该栈为空栈！"); System.out.println("-------------------"); return; } list.reversePrint(list.getHead()); } } //定义SingleLinkedList来管理节点 class SingleLinkedList{ //先初始化一个头结点（一般不存放具体数据） private Node head = new Node(null,null); public Node getHead() { return head; } public SingleLinkedList() { } public SingleLinkedList(Node head) { this.head = head; } /* 添加节点到单链表 当不考虑编号顺序时 1.找到当前链表的最后节点 2.将尾结点的next指向新节点 */ public void add(Node node){ //因为head节点不能动，所以创建一个辅助遍历的节点temp Node temp = head; //遍历链表，寻找尾结点 while (true){ //该节点已经是尾结点及跳出循环 if (temp.next == null){ break; } //若仍不是尾结点则继续遍历 temp = temp.next; } //退出while循环时，temp就指向了链表的尾结点 //将尾结点的next指向要插入的新节点 temp.next = node; } //删除尾节点思路：当temp.next.next == null时，删除该节点 public int delete(){ Node temp = head; while (true){ if (temp.next.next == null){ //已经到链表的最后 break; } temp = temp.next; } int value = temp.next.value; //删除尾节点 temp.next = null; return value; } //显示链表（遍历） public void showList(){ //判断链表是否为空 if (head.next == null){ System.out.println("该链表为空链表！"); return; } //因为头节点不能动，所以使用一个辅助节点进行遍历 Node temp = head.next; while (true){ if (temp.next == null){ System.out.println(temp); break; } System.out.println(temp); temp = temp.next; } } //显示链表长度(遍历) public int getLength(){ int length = 0; //判断链表是否为空 if (head.next == null){ return length; } //因为头节点不能动，所以使用一个辅助节点进行遍历 Node temp = head.next; while (true){ if (temp.next == null){ break; } length++; temp = temp.next; } return length; } //可以使用栈将各个节点压入到栈中，然后利用栈的先进后出的特点，实现逆序打印 public void reversePrint(Node head){ //创建一个栈stack，将各个节点压入栈 Stack<Node> stack = new Stack<>(); Node cur = head.next; while (cur != null){ stack.push(cur); cur = cur.next; } //将栈中的节点pop出栈并打印 while (stack.size() > 0){ System.out.println(stack.pop()); } } } //定义一个Node类，每个Node对象就是栈中的一个节点 class Node{ public Integer value; public Node next; //指向下一个节点 //构造方法 public Node(Integer value, Node next) { this.value = value; this.next = next; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } }