DomBro Studio

栈及栈的应用

2017/12/21

前言

数据结构是一个程序员的内功,只有内功基础打牢了,才可以决定你是否可以练就上乘的武功。今天来说一说栈结构。

What

啥是栈(stack)结构?关于栈结构听过最多的就是后入先出的结构(LIFO,last in first out)。别说你不知道啊!

  • 栈的特点

1.首先栈你要知道栈是一个表(线性结构),因此任何实现表的方法都能实现栈。
2.栈是限制插入和删除只能在一个位置进行的表,该位置是表的末端,叫做栈顶(top)。
3.对栈的基本操作有push(进栈)和 pop(出栈),前者相当于插入,后者则是删除最后插入的元素。
4.由于第二点和第三点中说的,栈只在栈顶进行操作,所以出栈和入栈都是常数时间的操作。

How

根据栈的特点中的第一条,栈是一个表,任何实现表的方法都能实现栈。那就分别用数组和链表的方式实现一下栈。

栈的数组实现

由于栈只操作栈顶元素,如果用顺序存储的数组实现,又考虑后入先出的原则,很自然就会想到利用数组中最后一个元素的索引(这里叫他topOfStack) !比如push操作,我们可以先让topOfStack++,然后再把push的元素赋值给数组的topOfStack索引。

很好理解吧?因为栈这个结构本身就是一个很基础的结构呀!下面是具体的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class ArrayStack<AnyType> {

//默认规模
private static final int DEFAULT_CAPACITY = 10;
//用数组实现栈
private AnyType[] theArray;
//记录栈的规模
private int theSize;
//记录栈顶元素位置
private int top0fStack;
//通过构造方法完成初始化
public ArrayStack(){
doClear();
}

/**
* 入栈操作
* 1.栈顶元素索引 ++,并指向插入元素
* 2.栈规模 ++
*/
public void push(AnyType item){
//判断栈是否已满
if(theSize == theArray.length){
ensureCapacity(theSize*2+1);
}
top0fStack++;
theArray[top0fStack] = item;
theSize++;
}

public AnyType peek(){
if (size() == 0){
throw new EmptyStackException();
}else {
return theArray[theSize-1];
}

}

public int size() {
return theSize;
}

/**
* 出栈操作
* 1.栈规模 --
* 2.返回当前栈顶元素,栈顶元素索引--
*/
public AnyType pop(){
theSize--;
return theArray[top0fStack--];
}



private void doClear(){
theSize = 0;
top0fStack = -1;
ensureCapacity(DEFAULT_CAPACITY);
}

//扩充栈规模
public void ensureCapacity(int newCapacity){

if (theSize > newCapacity)
return;
//判断theArray有没有被初始化
if (theArray != null){
AnyType[] oldItems = theArray;
theArray = (AnyType[]) new Object[newCapacity];
for (int i = 0; i < theSize; i++){
theArray[i] = oldItems[i];
}
}else{
theArray = (AnyType[]) new Object[newCapacity];
}

}

public boolean isEmpty(){
return theSize == 0;
}

}

有意思的是,你会发现我在pop(出栈)操作时,并没有将栈顶元素删除掉而是利用了 topOfStack(栈顶元素在数组中的索引) 减一,让使用者无法访问刚刚出栈的元素,这是一种逻辑上的删除

栈的链表实现

用链表实现栈的好处是,我们不用担心数组越界,数组是否已满等等,要考虑后入先出,我们就要依赖于 topOfStack 节点的引用(注意,这里是节点!!),首先topOfStack 节点的数据域被初始化为null,当进行push操作时 topOfStack 的后继为新插入的节点,而新插入节点的前驱则为当前 topOfStack ,最后将 topOfStack 引用指向刚刚插入的节点。什么?你蒙了?看图呀!

也就是说topOfStack就是指向栈顶的引用!下面使代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
* 用链表实现的栈
*/
public class LinkedStack<AnyType> {


//栈规模
private int theSize;

//栈顶结点
private Node<AnyType> topOfStack;

/**
*入栈操作:
* 1.将栈顶结点作为插入节点的前驱
* 2.栈顶结点变为新插入节点
* 3.栈规模加一
*/
public void push(AnyType item){
Node<AnyType> newNode = new Node<AnyType>(item,topOfStack);
topOfStack.next = newNode;
topOfStack = topOfStack.next;
theSize++;
}

public AnyType peek(){
return topOfStack.data;
}

/**
* 出栈操作:
* 1.返回当前栈顶结点的数据域
* 2.栈顶结点的前驱作为栈顶结点
* 3.栈规模减一
*
*/
public AnyType pop(){

Node<AnyType> oldTop;
if (theSize <= 0){
throw new IllegalStateException();
}
oldTop = topOfStack;
topOfStack = topOfStack.prev;
theSize--;
return oldTop.data;
}

public LinkedStack(){
doClear();
}

/**
* 对栈进行初始化
*/
private void doClear(){
topOfStack = new Node<AnyType>(null,null);
theSize = 0;
}



private static class Node<AntType>{

public AntType data ;
public Node<AntType> next;
public Node<AntType> prev;

public Node(AntType data,Node<AntType> prev){
this.data = data;
this.prev = prev;
}

}

public boolean isEmpty(){
return theSize <= 0;
}

}

总的来说无论用数组实现还使用链表实现都是各有优缺点的,比如用数组实现你就要考虑数组长度问题,而用链表如果你指针(引用)知识学的很屎,则容易出现大的bug !但是一般来说使用数组方式实现是更流行的。

When

是英雄总要有用武之地,栈是一个在计算机科学中很常用也很实用的数据结构。下面来介绍几个简单的应用。

符号平衡

如果你是一个 Java 或 C++ 等程序员(不包括Python),如果不用 IDEA 或 Eclipse 等IDE 让你在记事本上(或者是 vim 等编辑器,无所谓啦)写程序,你可能很不习惯,因为这些家伙都不能自动为你补齐 { < ( [ 括号的 右半部分,而且也不会提示你没有输入右半部分的括号。那你有没有好奇那些编辑器是咋做到的,其实很简单!就是利用咱们的栈结构!因为在编程语言中右括号一定会匹配离该右括号最近的左括号,而最近的左括号一定是最后输入的。
遵循以下几点:
1.给定一段字符串,当遇到 左括号 { < ( [ 时入栈。
2.当遇到右括号 ] ) > } 时出栈,判断出栈符号与右括号是否匹配。
3.当字符串读取完毕,但是栈中还有左括号时,说明存在未输入的右括号。

下面是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* 栈的平衡符号应用
* 1.若遇到 [,{,(,< 入栈
* 2.若遇到 ].},),> 出栈
*/
public static void bracketCheck(String input){
ArrayStack<Character> stack = new ArrayStack();

for (int i = 0;i < input.length();i++){
char inChar = input.charAt(i);
switch (inChar){
case '[':
case '{':
case '(':
case '<':
stack.push(inChar);
break;

case ']':
case '}':
case ')':
case '>':
if (! stack.isEmpty()){
char popChar = stack.pop();
if ((popChar == '[' && inChar != ']') || (popChar == '{' && inChar != '}') || (popChar == '(' && inChar != ')')|| (popChar == '<' && inChar != '>')){
throw new RuntimeException("请确保有与"+inChar+"对应字符");
}
}else {
throw new RuntimeException("你并没输入左侧符号");
}
break;

default:
break;
}
}
if (!stack.isEmpty()){
throw new RuntimeException("你并没输入右侧符号");
}
}

后缀表达式求值

我们的计算机是很笨的,他只会从左往右去读,比如让他计算 1*3+4+2 它会算出结果是 9 但是 1+3+4*2 他一定给你算一个 16 。怎么办呢?聪明的计算机设计人员设计了一种后缀表达式 1+3+4*2 就变成 13+42*+ 。啥?你看不懂?后缀表达式就是把原本在两个数字中间的运算符号放置在要计算的两个数字后面计算后缀表达式最简单的做法就是使用栈,并且不需要知道任何优先规则

遵循以下几点:
1.当遇到一个数字进栈;
2.遇到第一个操作符时,该运算符就作用于栈中弹出的两个数上,再将所得结果压入栈中。

下面是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* 后缀表达式求值
* 1.将数字依次压入栈中
* 2.当遇到操作符时将栈中两个数字出栈,将两数字与操作符的结果再次压入栈中
* 3.后缀表达式的好处是不用知道任何优先规则
* 4.按照规定位与位之间用 " " 相隔
*/
public static int postFix(String input){
ArrayStack<Integer> stack = new ArrayStack();
String[] postFix = input.split(" ");
for (int i = 0;i < postFix.length; i++){
String card = postFix[i];
int topOfStack ;
int nextOfStack;
int result;
if (card.matches("[0-9]+")){
int number = Integer.parseInt(card);
stack.push(number);
}else{
switch (card){
case "+":
topOfStack = stack.pop();
nextOfStack = stack.pop();
result = topOfStack + nextOfStack;
stack.push(result);
break;
case "-":
topOfStack = stack.pop();
nextOfStack = stack.pop();
result = nextOfStack - topOfStack ;
stack.push(result);
break;
case "*":
topOfStack = stack.pop();
nextOfStack = stack.pop();
result = nextOfStack * topOfStack ;
stack.push(result);
break;
case "/":
topOfStack = stack.pop();
nextOfStack = stack.pop();
result = nextOfStack / topOfStack ;
stack.push(result);
break;
}
}
}
return stack.pop();
}

中缀表达式转后缀表达式

上面介绍了后缀表达式求值,可是要怎样将正常的中缀表达式转为后缀表达式呢?仅考虑中缀表达式中的符号有 + - * / () 。还要考虑这几个符号的运算优先级,咋办?用栈!
遵循以下几点:
1.当遇到数字直接输出。
2.遇到 ( 入栈。
3.遇到 +或- :判断栈顶是否为*或/ ,若是则将 * 或 /出栈并输出,并将 +或 -入栈
4.遇到*或/ :直接入栈。
5.遇到 ) : 将栈中一直到 ( 的字符出栈并输出,( 出栈并不输出。
6.读取字符串之后,将栈中字符出栈并输出。

下面是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
* 通过中缀表达式得到后缀表达式
* 1.使用栈放入操作符
* 2.操作符仅允许使用 + - * / ()
* 3.优先级 () 大于 * / 大于 + -
* 4.当 遇到优先级 更高的操作符时,当遇到数字便全部出栈
* 5.当 栈中有 ( 时,除非遇到 ) 否则 ( 不出栈
* 6.按照规定位与位之间用 " " 相隔
*/
public static String getPostFix(String input){
ArrayStack<String> opStack = new ArrayStack<>();

String[] preFixArray = input.split(" ");
String suffix = "";
for (int i = 0; i < preFixArray.length; i++){
String current = preFixArray[i];
String temp ;
switch (current){
//遇到 ( 则入栈
case "(":
opStack.push(current);
break;
case "+":
case "-":
while (!opStack.isEmpty()){
temp = opStack.pop();
//如果是栈顶是 ( 则直接将当前字符串入栈,不进行操作
if (temp.equals("(")){
opStack.push("(");
break;
}else {
suffix += " "+temp;
}

}
opStack.push(current);
suffix += " ";
break;
case "*":
case "/":
while (!opStack.isEmpty()){
temp = opStack.pop();
if (temp.equals("(") || temp.equals("+") || temp.equals("-")){
opStack.push(temp);
break;
}else {
suffix += " " + temp;
}
}
opStack.push(current);
suffix += " ";
break;
case ")":
while (!opStack.isEmpty()){
temp = opStack.pop();
if (temp.equals("(")){
break;
}else {
suffix += " "+temp ;

}
}
break;
default :
suffix += current;
break;
}
}

while (!opStack.isEmpty()){
suffix += " "+ opStack.pop();
}
System.out.println();

return suffix;
}

这就是栈的几个应用,你说他简单但是他却很重要。你会发现栈的应用一般都是用在要保存某种状态时的场景,比如网页浏览记录、回退等等。

CATALOG
  1. 1. 前言
  2. 2. What
  3. 3. How
    1. 3.1. 栈的数组实现
    2. 3.2. 栈的链表实现
  4. 4. When
    1. 4.1. 符号平衡
    2. 4.2. 后缀表达式求值
    3. 4.3. 中缀表达式转后缀表达式