『数据结构与算法』栈(原理与实现)

人生处万类,知识最为贤。这篇文章主要讲述『数据结构与算法』栈:原理与实现相关的知识,希望能为你提供帮助。
1. 栈(Stack)
栈又叫堆栈,是一种运算受限制的线性表,限定只能在一端进行插入和删除操作,该端称为栈顶(Top),相对的另一端叫栈底(Bottom)。
根据栈的定义可知,最先进入栈的元素在栈底,最后进入栈的元素在栈顶。而删除元素刚好相反,即删除顺序从栈顶到栈底
对栈的操作只有两种:

  • 入栈(push):又叫进栈或压栈,即向栈插入一条新的元素,该元素为新的栈顶元素。
  • 出栈(pop):又叫退栈,即从栈顶删除(取出)最后入栈的元素,而其相邻元素成为新的栈顶元素。
『数据结构与算法』栈(原理与实现)

文章图片

栈是一个先进后出(FILO - First In Last Out)的有序列表。在上图中描述了栈的模型,我们对栈的操作只有pushpop,栈顶元素是该栈唯一可见的元素。
2. 代码实现
由于栈是一个表,因此任何实现表的方法都能实现栈。显然我们之前用到的《 数组 》和《 链表 》都可以实现栈。下面代码是使用数组实现的一个栈。
size表示栈内元素的大小,栈顶元素为 elementData[size - 1],栈底元素为 elementData[0]。入栈时执行 size++,出站时执行 size--
public class StackDemo {public static void main(String[] args) {System.out.println("-------------------入站"); Stack< String> stack = new Stack< > (10); stack.push("a"); stack.push("b"); stack.push("c"); stack.push("d"); stack.push("e"); stack.print(); System.out.println("元素大小: " + stack.size()); System.out.println("栈容量: " + stack.capacity()); System.out.println("-------------------出站"); System.out.println("出站元素: " + stack.pop()); System.out.println("出站元素: " + stack.pop()); stack.print(); System.out.println("元素大小: " + stack.size()); System.out.println("栈容量: " + stack.capacity()); }private static class Stack< E> { private int size; // 元素大小 private final int capacity; // 栈的容量 transient Object[] elementData; // 元素数据public Stack(int capacity) { if (capacity < = 0) { throw new IllegalArgumentException("Illegal Capacity: " + capacity); } else { this.capacity = capacity; elementData = https://www.songbingjia.com/android/new Object[capacity]; } }/** * 获取栈的元素大小 * * @return */ public int size() { return size; }/** * 获取栈的容量 * * @return */ public int capacity() { return capacity; }/** * 入栈 * * @param e * @return */ public boolean push(E e) { if (size > = capacity) { return false; } elementData[size++] = e; return true; }/** * 出栈 * * @return */ public E pop() { if (size < = 0) { return null; } return (E) elementData[--size]; }/** * 打印元素数据 */ public void print() { System.out.print("站内元素: "); for (int i = 0; i < size; i++) { System.out.printf("%s\\t", elementData[i]); } System.out.println(); } } }

输出结果:
-------------------入站 站内元素: a bcde 元素大小: 5 栈容量: 10 -------------------出站 出站元素: e 出站元素: d 站内元素: a bc 元素大小: 3 栈容量: 10

3. 栈的应用 - 平衡符号
编译器检查程序的语法错误时,常常会因为缺少一个符号(如遗漏一个花括号等)引起编译器上列出上百行的诊断,而真正的错误并没有找出。在这种情况下,如果能有一个工具能够检测括号必须成对出现那就好了,这便可以使用栈进行解决。
下面代码使用了java自带的Stack类进行实现。字符串[ ( ) ]是合法的,而[ ( ] )是错误的。
代码实现:
public class StackDemoBalancedChar {public static void main(String[] args) {BalancedChar balancedChar = new BalancedChar(); String str = "[()][{}][][((()))]"; boolean ok = balancedChar.isOk(str); System.out.printf("字符串:%s\\t----> %s", str, ok); }private static class BalancedChar { private final char[] openArray = {\'(\', \'[\', \'{\'}; // 左括号 private final char[] closeArray = {\')\', \']\', \'}\'}; // 右括号/** * 判断字符串是否正确 * * @param str * @return */ public boolean isOk(String str) { // 使用 Java 自带的 Stack 类 Stack< Character> stack = new Stack< > (); boolean ok = true; // 判断字符串是否正确for (char c : str.toCharArray()) {// 若不是平衡符则忽略 if (!isBalancedChar(c)) { continue; }// 如果是左括号,则入栈 if (isOpen(c)) { stack.push(c); continue; }// 如果是右括号,而栈为空则报错 if (stack.empty()) { ok = false; break; } // 如果是右括号,从栈中取出一个元素,并与当前元素判断是否是一对,若不是一对则报错 Character open = stack.pop(); if (!isTwain(open, c)) { ok = false; } }return ok & & stack.empty(); }/** * 是否为左括号 * * @param c * @return */ public boolean isOpen(char c) { return inArray(openArray, c); }/** * 是否为右括号 * * @param c * @return */ public boolean isClose(char c) { return inArray(closeArray, c); }/** * 是否是平衡符 */ public boolean isBalancedChar(char c) { return isOpen(c) || isClose(c); }/** * 是否在数组中 * * @param charArray * @param c * @return */ public boolean inArray(char[] charArray, char c) { for (char c1 : charArray) { if (c1 == c) { return true; } } return false; }/** * 是否一对平衡符 * * @param open * @param close * @return */ public boolean isTwain(char open, char close) { switch (open) { case \'(\': if (close == \')\') { return true; } case \'[\': if (close == \']\') { return true; } case \'{\': if (close == \'}\') { return true; } default: return false; } }} }

输出结果:
字符串:[()][{}][][((()))]----> true

推荐阅读
  • 数组
  • 稀疏数组
  • 链表(单链表、双链表、环形链表)
  • 队列
  • 二叉树
  • 二叉查找树(BST)
  • AVL树(平衡二叉树)
  • B树
  • 散列表(哈希表)
【『数据结构与算法』栈(原理与实现)】
『数据结构与算法』栈(原理与实现)

文章图片


    推荐阅读