人生处万类,知识最为贤。这篇文章主要讲述『数据结构与算法』栈:原理与实现相关的知识,希望能为你提供帮助。
1. 栈(Stack)
栈又叫堆栈,是一种运算受限制的线性表,限定只能在一端进行插入和删除操作,该端称为栈顶(Top),相对的另一端叫栈底(Bottom)。
根据栈的定义可知,最先进入栈的元素在栈底,最后进入栈的元素在栈顶。而删除元素刚好相反,即删除顺序从栈顶到栈底
对栈的操作只有两种:
- 入栈(push):又叫进栈或压栈,即向栈插入一条新的元素,该元素为新的栈顶元素。
- 出栈(pop):又叫退栈,即从栈顶删除(取出)最后入栈的元素,而其相邻元素成为新的栈顶元素。
文章图片
栈是一个先进后出(FILO - First In Last Out)的有序列表。在上图中描述了栈的模型,我们对栈的操作只有
push
和pop
,栈顶元素是该栈唯一可见的元素。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树
- 散列表(哈希表)
文章图片
推荐阅读
- 动态路由
- 零基础领跑教科书式博文(DAY2---Linux文件管理)
- # 聊一聊悟空编辑器 #H3C交换机密码设置
- JavaScript中 querySelector 与 getElementById 方法的区别
- WordPress-functions.php导致WordPress错误
- 设置静态首页后,WordPress首页(主页)无法重定向
- WordPress页脚的汇总
- WordPress(在我的索引页(主页)中修复了太多链接的.CSS文件)
- WordPress-在插件中首先检查page.php