数据结构与算法——栈基本概念(学习笔记)
2022/3/19 11:30:00
本文主要是介绍数据结构与算法——栈基本概念(学习笔记),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录
一.栈的介绍
二.栈的应用场景
三.数组模拟栈
一.栈的介绍
1.栈(Stack)是一个先入后出的有序列表。
2.栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶,另一端为固定的一端,称为栈底。
3.根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
4.图解方式说明出栈(pop)和入栈(push)的概念
二.栈的应用场景
1.子程序的调用:在跳往子程序之前,会先将下个指令的地址存到堆栈中,直到子程序执行完成后再将地址取出,以回到原来的程序中。
2.处理递归调用:和子程序的调用类似,只是除了存储下一个指令的地址外,也将参数,区域变量等数据存入堆栈中。
3.表达式的转换[中缀表达式转后缀表达式]与求值。
4.二叉树的便历。
5.图形的深度优先搜索法。
三.数组模拟栈
由于栈是一种 有序列表,可以使用数组的结构来储存栈的数据内容,模拟栈的出栈,入栈等操作。
代码实现:
import java.util.Scanner; public class ArrayStackDemo { public static void main(String[] args) { ArrayStack arrayStack = new ArrayStack(4); String key = ""; boolean loop = true; Scanner scanner = new Scanner(System.in); while (loop) { System.out.println("show: 显示栈"); System.out.println("exit: 退出程序"); System.out.println("push: 添加数据"); System.out.println("pop: 取出数据"); System.out.println("请输入你的选择"); key = scanner.next(); switch (key) { case "show": arrayStack.list(); break; case "push": System.out.println("请输入一个数"); int value = scanner.nextInt(); arrayStack.push(value); break; case "pop": try { int res = arrayStack.pop(); System.out.println(res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case "exit": scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出"); } } class ArrayStack { private int maxSize; private int[] stack; private int 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; } public void push(int value) { if (isFull()) { System.out.println("栈满"); } top++; stack[top] = value; } public int pop() { if (isEmpty()) { throw new RuntimeException("栈空"); } int value = stack[top]; top--; return value; } public void list() { if (isEmpty()) { System.out.println("栈空"); return; } for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } }
这篇关于数据结构与算法——栈基本概念(学习笔记)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南