概述
- 栈就是一种 只允许在表尾进行插入和删除操作 的 线性表
- 栈的特点
- 先进后出 ，在表尾进行插入和删除操作
数组实现栈
- crown
- crown：使用crown来确定栈顶所在数组的下标，默认为 -1
- 空栈
- 当空栈时 ，crown = -1
- 栈是否为空
- 当 crown = -1 时 ，栈为空 ，不能 遍历 ，出栈 ， 获取栈顶元素
- 栈是否已满
- 当 crown = 数组.length – 1 时 ，栈已满 ， 不能 入栈
- 入栈
- 栈未满，才能入栈
- 先将 crown上移 ，再给数组下标为crown的元素赋值
- 栈满 ，不能入栈
- 出栈
- 栈不为空 ，才能出栈
- 将 crown往下移即可
- 栈为空 ，不能出栈
- 获取栈顶元素
- 栈不为空 ，才能获取栈顶元素
- 获得数组下标为crown的元素
- 栈为空 ，不能出栈
- 重置栈
- 让crown = -1 即可
- 打印栈
- 遍历数组下标范围为 [ 0 , crown ] ，即可
public class ArrayStack { private int[] satck; private int size; private int crown = -1; // 栈顶 public ArrayStack(int size){ this.size = size; satck = new int[size]; } //入栈操作 public void push(int value){ if (!isFull()){ satck[++crown] = value; } } //出栈 public void pop(){ if (!isEmpty()){ crown--; } } //判断是否为空 public boolean isEmpty(){ return crown == -1; } //判断栈是否已满 public boolean isFull(){ return crown == size-1; } //获取栈顶元素 public int getTop(){ if (!isEmpty()){ return satck[crown]; } return -1; } //重置栈 public void reset(){ crown = -1; } //打印栈 , 从栈顶开始打印 public void print(){ int j = 0; for (int i = crown; i >= 0; i--) { System.out.println("第"+(++j)+"个元素为：" + satck[i]); } }}/** * @author 发着呆看星 * @create 2023/4/18 **/public class ArrayStackTest { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); ArrayStack arrayStack = new ArrayStack(5); boolean p = true; while (p){ System.out.println("==================栈的功能检测==================="); System.out.println("1) 入栈"); System.out.println("2) 出栈"); System.out.println("3) 重置栈"); System.out.println("4) 打印栈"); System.out.println("5) 取出栈顶元素"); System.out.println("6) 退出程序"); System.out.print("请选择你需要的功能(1~~6)："); int i = scanner.nextInt(); int j; switch (i){ case 1: System.out.print("请选择你要入栈的数字："); j = scanner.nextInt(); arrayStack.push(j); break; case 2: arrayStack.pop(); break; case 3: arrayStack.reset(); break; case 4: arrayStack.print(); break; case 5: int top = arrayStack.getTop(); System.out.println("栈顶元素为："+top); break; case 6: p = false; break; } } }}链表实现栈
- 实现思路
- 入栈：将每一个入栈的元素添加为链表的首节点
- 出栈：出栈则将链表的首节点进行删除
- 由于链表可以无限长，所以不用担心栈满的问题
- crown：代表栈顶元素的上一个元素 ，val属性默认为 -1 ，next 属性即为 栈顶元素
- 当 next == null 时 ，代表空栈
- 判断栈是否为空
- 当crown.next == null 时 ，栈为空
- 重置栈
- 即将 crown的next属性置为null
- 获取栈顶元素
- 即获取链表首节点(获取crown的next属性所代表的节点)
- 打印栈
- 即遍历链表
/** * @author 发着呆看星 * @create 2023/4/18 **/public class LinkedListStack { private ListNode crown = new ListNode(-1,null); // 判断是否为空 public boolean isEmpty(){ return crown.next == null; } // 入栈操作 public void push(int value){ ListNode temp = crown.next; crown.next = new ListNode(value, temp); } // 出栈操作 public void pop(){ if (!isEmpty()){ crown.next = crown.next.next; } } // 取出栈顶元素 public ListNode getTop(){ return crown.next; } // 重置栈 public void reset(){ crown.next = null; } // 打印栈 ，从栈顶开始 public void print(){ ListNode temp = crown; int i = 0; while (temp.next != null){ System.out.println("第"+(++i)+"个元素为："+temp.next.val); temp = temp.next; } }}/** * @author 发着呆看星 * @create 2023/4/18 **/public class LinkedListStackTest { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); LinkedListStack stack = new LinkedListStack(); boolean p = true; while (p){ System.out.println("==================栈的功能检测==================="); System.out.println("1) 入栈"); System.out.println("2) 出栈"); System.out.println("3) 重置栈"); System.out.println("4) 打印栈"); System.out.println("5) 取出栈顶元素"); System.out.println("6) 退出程序"); System.out.print("请选择你需要的功能(1~~6)："); int i = scanner.nextInt(); int j; switch (i){ case 1: System.out.print("请选择你要入栈的数字："); j = scanner.nextInt(); stack.push(j); break; case 2: stack.pop(); break; case 3: stack.reset(); break; case 4: stack.print(); break; case 5: ListNode top = stack.getTop(); System.out.println("栈顶元素为："+top); break; case 6: p = false; break; } } }}春去秋来，岁岁平安