『数据结构与算法』—— 栈

  |     |   本文总阅读量:

定义

先入后出,有点类似将书放在抽屉里,先放进去的书,如果想拿到他,必须将他上面书拿完才可以,粗俗的形容可以这么比喻:“吃了吐”叫栈,“吃了拉”叫队列,话粗理不粗。栈是一种“操作受限”的线性表,只允许一段插入和删除数据。

从功能上看,数组或链表确实可代替栈,但是在特定的情况中,数组和链表暴露的接口太多,操作上虽然灵活,但是很多条件不可控,使用上当然容易出现问题。

当某个数据集合只涉及在一段插入和删除数据,并且满足先进后出的特性,我们就应该首选栈这种数据结构。

实现

根据其定义和特点,栈主要包含两个操作,入栈和出栈。数组和链表都可以实现,用数组实现的栈叫做 顺序栈,用链表实现的栈叫做 链式栈。后面会贴上具体的实现代码和测试用例。

栈存储数据只需要一个大小为 n 的数组就足够了,在操作数据的过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1),至于入栈和出栈的时间复杂度也是 O(1)。

练习

数组实现栈(支持动态扩容)

需要注意点:

  1. 当数据不断增加,大小达到阈值,也就是容器满了,此时大小需要扩容到原来的两倍。
  2. 当数据不断减小,大小达到整个大小四分之一时,此时大小需要缩小为原来的 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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
class ArrayStack<T> implements Iterable<T>{
private T[] data;
private int totalCount;
private int count;

ArrayStack(int capacity) {
data = (T[]) new Object[capacity];
totalCount = capacity;
}

private boolean push(T t) {
if (count == totalCount) {
resize(totalCount * 2);
}
data[count] = t;
count++;
System.out.println("push: " + t + " data:\t" + Arrays.toString(data));
return true;
}

private T pop() {
if (count == 0) return null;
T t = data[count - 1];
data[count - 1] = null;
count --;
if (count == totalCount / 4 && totalCount / 2 != 0) {
resize(totalCount / 2);
}
System.out.println("pop: " + t + " data:\t" + Arrays.toString(data));
return t;
}

boolean isEmpty() {
return count == 0;
}

int size() {
return count;
}

T peek() {
if (count == 0) {
return null;
}
T t = data[count - 1];
System.out.println("peek: " + t + " data:\t" + Arrays.toString(data));
return t;
}

private void resize(int newSize) {
T[] newData = (T[]) new Object[newSize];
for (int i = 0; i < count; i++) {
newData[i] = data[i];
}
totalCount = newData.length;
System.out.println("扩容前:" + data.length);
data = newData;
System.out.println("重新调整大小:\t" + data.length + " data:\t" + Arrays.toString(data));
}

public static void main(String[] args) {
ArrayStack<Integer> data = new ArrayStack<Integer>(4);
data.push(1);
data.push(2);
data.push(3);
data.push(4);
data.push(5);
data.push(6);
System.out.println("size:\t" + data.size());
System.out.println("isEmpty:\t" + data.isEmpty());
for (Integer datum : data) {
System.out.print(datum);
}
System.out.println();
data.pop();
data.pop();
data.pop();
data.pop();
data.peek();
data.peek();
data.peek();
}

@Override
public Iterator<T> iterator() {
return new ArrayIterator();
}
class ArrayIterator implements Iterator<T> {
int i = count;
@Override
public boolean hasNext() {
return i > 0;
}

@Override
public T next() {
return data[--i];
}

@Override
public void remove() {

}
}
}

这里如果需要支持加强 for 循环,则需要创建自定义实现 Iterator 类。

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
push: 1  data:	[1, null, null, null]
push: 2 data: [1, 2, null, null]
push: 3 data: [1, 2, 3, null]
push: 4 data: [1, 2, 3, 4]
扩容前:4
重新调整大小: 8 data: [1, 2, 3, 4, null, null, null, null]
push: 5 data: [1, 2, 3, 4, 5, null, null, null]
push: 6 data: [1, 2, 3, 4, 5, 6, null, null]
size: 6
isEmpty: false
654321
pop: 6 data: [1, 2, 3, 4, 5, null, null, null]
pop: 5 data: [1, 2, 3, 4, null, null, null, null]
pop: 4 data: [1, 2, 3, null, null, null, null, null]
扩容前:8
重新调整大小: 4 data: [1, 2, null, null]
pop: 3 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]
peek: 2 data: [1, 2, null, null]

链表实现栈

需要注意的是临界值的判断。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class LinkedStack<T> implements Iterable<T> {
Node<T> head = null;
int count = 0;

void push(T t) {
Node<T> node = createNode(t);
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
count++;
System.out.println("push:\t" + t + " data:\t" + head.toString());
}

T pop() {
if (head == null) {
return null;
}
T t = head.value;
head = head.next;
if (head != null) {
System.out.println("pop:\t" + t + " data:\t" + head.toString());
} else {
System.out.println("pop:\t" + t + " data:\tnull");
}
count--;
return t;
}

boolean isEmpty() {
return count == 0;
}

int size() {
return count;
}

T peek() {
if (head == null) {
return null;
}
T t = head.value;
System.out.println("peek:\t" + t + " data:\t" + head.toString());
return t;
}

Node<T> createNode(T t) {
return new Node<T>(t, null);
}

public static void main(String[] args) {
LinkedStack<Integer> stack = new LinkedStack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println("size:\t" + stack.size());
System.out.println("isEmpty:\t" + stack.isEmpty());
for (Integer integer : stack) {
System.out.println(integer);
}
stack.peek();
stack.peek();
stack.peek();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (T t : this) {
sb.append(t).append(" ");
}
sb.append("\n");
return sb.toString();
}

void clear() {
head = null;
count = 0;
}

@Override
public Iterator<T> iterator() {
return new LinkedIterator();
}

class LinkedIterator implements Iterator<T> {
Node<T> first = head;
int n = count;

@Override
public boolean hasNext() {
return n > 0;
}

@Override
public T next() {
T t = first.value;
first = first.next;
n--;
return t;
}

@Override
public void remove() {

}
}
}

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
push:	1  data:	1 
push: 2 data: 2 1
push: 3 data: 3 2 1
push: 4 data: 4 3 2 1
size: 4
isEmpty: false
4321
peek: 4 data: 4 3 2 1
peek: 4 data: 4 3 2 1
peek: 4 data: 4 3 2 1
pop: 4 data: 3 2 1
pop: 3 data: 2 1
pop: 2 data: 1
pop: 1 data: null

栈在括号匹配中的应用

括号一般都是一一对应的,那可以用栈保存未匹配的左括号,从左到又进行扫描。

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
class StackTest1 {
public static void main(String[] args) {
LinkedStack<String> stack = new LinkedStack<String>();
stack.push("[");
stack.push("{");
stack.push("『");
stack.push("「");
stack.push("」");
stack.push("』");
stack.push("}");
stack.push("]");
System.out.println(stack.toString());
System.out.println("is correct:\t" + isCorrect(stack));
}

private static boolean isCorrect(LinkedStack<String> stack) {
boolean isCorrect = true;
LinkedStack<String> stack1 = new LinkedStack<String>();
for (String s : stack) {
stack1.push(s);
}
Iterator<String> iterator = stack.iterator();
Iterator<String> iterator1 = stack1.iterator();
while (iterator.hasNext() && iterator1.hasNext()) {
if (!equals(iterator.next(), iterator1.next())) {
return false;
}
}
return isCorrect;
}

private static boolean equals(String one, String two) {
return ("[".equals(one) && "]".equals(two)) || ("[".equals(two) && "]".equals(one)) ||
("{".equals(one) && "}".equals(two)) || ("{".equals(two) && "}".equals(one)) ||
("「".equals(one) && "」".equals(two)) || ("「".equals(two) && "」".equals(one)) ||
("『".equals(one) && "』".equals(two)) || ("『".equals(two) && "』".equals(one));
}
}

浏览器在栈的应用

一般浏览器支持回退和前进功能,其实可以通过栈来实现这个功能。

  1. 使用两个栈,一个存储后退的数据,一个存储前进的数据
  2. 每次打开新的网址,后退栈压入,前进栈清空
  3. 每次回退网站,后退栈出栈,前进栈压入
  4. 在已经后退基础上前进,后退栈压入,前进栈出栈
  5. 每次前进和后退都需要判断各自栈是否可以进行数据操作
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
class StackTest2 {
String currentPage = "";
LinkedStack<String> backStack;
LinkedStack<String> forwardStack;

StackTest2() {
backStack = new LinkedStack<String>();
forwardStack = new LinkedStack<String>();
}

void open(String url) {
if (currentPage != null) {
backStack.push(url);
forwardStack.clear();
}
showPage(url, "open");
}

boolean canGoBack() {
return !backStack.isEmpty();
}

boolean canGoForward() {
return !forwardStack.isEmpty();
}

void goBack() {
if (canGoBack()) {
String back = backStack.pop();
forwardStack.push(currentPage);
showPage(back, "go back");
}
}

void goForward() {
if (canGoForward()) {
String forward = forwardStack.pop();
backStack.push(currentPage);
showPage(forward, "go forward");
}
}

void showCurrentPage() {
System.out.println("current page url:\t" + currentPage);
}


void showPage(String url, String desc) {
this.currentPage = url;
System.out.println("current page url:\t" + this.currentPage + " desc:\t" + desc);
}

public static void main(String[] args) {
StackTest2 stack = new StackTest2();
stack.open("http://www.baidu.com");
stack.open("http://news.baidu.com/");
stack.open("http://news.baidu.com/ent");
stack.goBack();
stack.goBack();
stack.goForward();
stack.open("http://www.qq.com");
stack.goForward();
stack.goBack();
stack.goForward();
stack.goBack();
stack.goBack();
stack.goBack();
stack.goBack();
stack.showCurrentPage();
}
}

参考自极客时间


赏我 e(=2.72) 元咖啡钱吧,您的支持将鼓励我继续创作!



文章目录
  1. 1. 定义
  2. 2. 实现
  3. 3. 练习
    1. 3.1. 数组实现栈(支持动态扩容)
    2. 3.2. 链表实现栈
    3. 3.3. 栈在括号匹配中的应用
    4. 3.4. 浏览器在栈的应用
您是第 位小伙伴 | 本站总访问量 | 已经写了 97.8k 字啦

载入天数...载入时分秒...