【数据结构与算法之线性结构】栈
【数据结构与算法之线性结构】栈
文章目录
- 【数据结构与算法之线性结构】栈
- 1 栈的基本概念
- 2 栈的定义
- 3 栈的基本操作
- 入栈
- 出栈
- 4 案例
- 二/十进制转换器
- 括号匹配问题
1 栈的基本概念
栈Stack 是一个后进先出 LIFO的线性表，它要求只能在表尾执行删除和插入等操作。其实栈就是一个线性表(可以是数组，也可以是链表)，就是操作受到限制。
栈的操作只能在线性表尾进行，表尾 → 栈顶top，表头 → 栈底bottom。
2 栈的定义
使用数组实现栈。
/*** @Projectname: JavaData_StructureAndAlgorithm* @Classname: MyStack* @Author: Ding Jiaxiong* @Data:2023/3/13 9:27*/public class MyStack {int[] stack; // 数组实现栈int top; // 栈顶索引int capacity; // 栈的容量public MyStack(int capacity) {stack = new int[capacity]; // 动态初始化栈，长度为capacitytop = 0; // 栈顶索引为0，说明此时栈空this.capacity = capacity; // 初始化栈的容量}public void push(int elem) {// 元素入栈}public int pop() {// 出栈}public void increaseCapacity() {// 增加栈的容量}}
这里我们并没有定义栈顶位置的值，因为用数组实现栈的话，bottom恒为0就行了，如果使用链表实现栈，则需要定义bottom，它应该是指向栈顶节点的指针变量。
初始化后，top = bottom = 0，说明此时空栈。
3 栈的基本操作
入栈
入栈就是向栈中存入数据。入栈操作在栈顶执行，每当向栈中压入一个数据，栈顶指针top + 1，直到栈满。
public void push(int elem) {// 元素入栈if (top == capacity) {// 扩容increaseCapacity();}stack[top] = elem;top++;}public void increaseCapacity() {// 增加栈的容量// 初始化一个新栈，容量是原栈容量的2倍int[] stackTmp = new int[stack.length * 2];System.arraycopy(stack, 0, stackTmp, 0, stack.length);stack = stackTmp;}
top 始终指向栈顶元素的上一个位置，所以当top 数值上 = capacity时，说明栈满。
出栈
出栈与入栈相反，从栈顶取出元素，top -1 。
public int pop() {// 出栈if (top == 0) {System.out.println("栈中没有数据");return -1; // 返回一个无效值}top--;return stack[top];}
测试
/*** @Projectname: JavaData_StructureAndAlgorithm* @Classname: MyStack* @Author: Ding Jiaxiong* @Data:2023/3/13 9:27*/public class MyStack {int[] stack; // 数组实现栈int top; // 栈顶索引int capacity; // 栈的容量public MyStack(int capacity) {stack = new int[capacity]; // 动态初始化栈，长度为capacitytop = 0; // 栈顶索引为0，说明此时栈空this.capacity = capacity; // 初始化栈的容量}public void push(int elem) {// 元素入栈if (top == capacity) {// 扩容increaseCapacity();}stack[top] = elem;top++;}public void increaseCapacity() {// 增加栈的容量// 初始化一个新栈，容量是原栈容量的2倍int[] stackTmp = new int[stack.length * 2];System.arraycopy(stack, 0, stackTmp, 0, stack.length);stack = stackTmp;}public int pop() {// 出栈if (top == 0) {System.out.println("栈中没有数据");return -1; // 返回一个无效值}top--;return stack[top];}public static void main(String[] args) {MyStack stack = new MyStack(3);stack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());}}
运行结果
如果再弹
没问题。
4 案例
二/十进制转换器
利用栈结构将二进制数转为十进制数。
举个栗子：将二进制数 11001转换为十进制数, → 1x2^0 + 0x2^1 + 0x2^2 + 1x2^3 + 1x2^4 = 25.
由于栈后进先出的特性，首先将二进制数从高位到地位顺序入栈，从栈顶依次取出，第i个元素，就对应的乘上 2 i − 1 2^{i - 1} 2i−1 。
Java代码实现：
/*** @Projectname: JavaData_StructureAndAlgorithm* @Classname: BiToDecTest* @Author: Ding Jiaxiong* @Data:2023/3/13 10:15*/public class BiToDecTest {public static String BiToDec(String binary) {MyStack stack = new MyStack(10);int i;// 将二进制串binary 从高位到地位入栈for (i = 0; i < binary.length(); i++) {if (binary.charAt(i) == '0') {stack.push(0); // 将0整数形式入栈} else {stack.push(1); // 1同理}}i = 0;int e;long sum = 0;// 将栈中元素顺序出栈，并将其转换为十进制数while ((e = stack.pop()) != -1) {// 没到栈底sum += (int) (e * Math.pow(2, i));i++;}return String.valueOf(sum);}public static void main(String[] args) {System.out.println(BiToDec("11001"));}}
运行结果
括号匹配问题
判断表达式中有两种括号， () 和 []，括号必须成对出现，编写一个程序，判断一个括号表达式是否合法。
【经典问题】利用栈来保存输入的括号，并判断输入的括号表达式是否合法。
每输入一个括号都与栈顶的括号进行比较，如果输入括号与栈顶保存的括号匹配，则栈顶出栈，如果不匹配，则输入符号入栈。输入完毕时，栈为空则表示合法，如果栈中还有剩余元素，则表明输入不完全匹配。
Java实现：
稍微进行了修改的自定义栈类：
/*** @Projectname: JavaData_StructureAndAlgorithm* @Classname: MyStack* @Author: Ding Jiaxiong* @Data:2023/3/13 9:27*/public class MyStack {char[] stack; // 数组实现栈int top; // 栈顶索引int capacity; // 栈的容量public MyStack(int capacity) {stack = new char[capacity]; // 动态初始化栈，长度为capacitytop = 0; // 栈顶索引为0，说明此时栈空this.capacity = capacity; // 初始化栈的容量}public void push(char elem) {// 元素入栈if (top == capacity) {// 扩容increaseCapacity();}stack[top] = elem;top++;}public void increaseCapacity() {// 增加栈的容量// 初始化一个新栈，容量是原栈容量的2倍char[] stackTmp = new char[stack.length * 2];System.arraycopy(stack, 0, stackTmp, 0, stack.length);stack = stackTmp;}public char pop() {// 出栈if (top == 0) {// System.out.println("栈中没有数据");return ' '; // 返回一个无效值}top--;return stack[top];}public static void main(String[] args) {MyStack stack = new MyStack(3);stack.push('a');stack.push('b');stack.push('c');stack.push('d');stack.push('e');System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());System.out.println(stack.pop());}}
测试
import java.util.Stack;/*** @Projectname: JavaData_StructureAndAlgorithm* @Classname: MatchBracketTest* @Author: Ding Jiaxiong* @Data:2023/3/13 10:28*/public class MatchBracketTest {private static boolean match(char a, char b) {if ((a == '(' && b == ')') || (a == '[' && b == ']')) {return true;}return false;}public static boolean MatchBracket(String expression) {// 判断括号表达式expression是否合法MyStack stack = new MyStack(10);char c;for (int i = 0; i < expression.length(); i++) {if ((c = stack.pop()) != ' ') {if (!match(c, expression.charAt(i))) {stack.push(c);stack.push(expression.charAt(i));}} else {stack.push(expression.charAt(i));}}if (stack.pop() != ' ') {return false;} else {return true;}}public static void main(String[] args) {String expression = "[([])]";System.out.println(MatchBracket(expression));}}
运行结果【匹配情况】
不匹配情况
秒速五厘米
太过爱你忘了你带给我的痛
你的名字
我就是我
还没有评论，来说两句吧...