1.栈的理解

栈是一种只允许从一端插入或者删除数据的结构,就比如你向弹匣装子弹,只能在头部装,在打枪的时候,也是在头部的子弹先发射出去,简单地说就是后进先出。

栈的插入操作叫做进栈,也称压栈、入栈。
栈的删除操作叫做出栈,也叫弹栈。

2.栈的应用

我们在浏览网页的时候,都会有个后退的按钮,这个就是用栈来实现的,还有就是大部分软件的可撤销操作,也都是用栈实现的。

3.栈的结构需要实现的方法

结构:
需要声明栈的容量以及当前栈的长度(就是下一个元素插入的位置或者当前栈顶的元素位置)

方法:

  1. InitStack(*s): 初始化操作,建立一个空栈。
  2. DestoryStack(*s): 若栈存在,就销毁栈
  3. ClearStaack(*s): 清空栈
  4. StackEmpty(*s): 判断栈是否为空,若为空,返回true
  5. GetTop(*s, e): 若栈顶存在,就用 e 来返回栈定元素
  6. Push(*s, e): 向栈顶插入元素,并用 e 返回栈顶元素
  7. Pop(*s, e): 若站栈顶存在,就删除栈顶元素并赋值给 e 返回
  8. StackLength(): 获取栈的长度

4.用 c 语言实现栈

有空补上

5. 用 Java 语言实现栈

顺序存储结构实现栈
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
public class ArrayStack implements Stack {
int length;
int[] arr;

public ArrayStack(int capacity){
arr = new int[capacity];
length = 0;
}
// 默认创建长度为10的数组
public ArrayStack(){
this(10);
}

@Override
public boolean isEmpty() {
return length == 0;
}

@Override
public int length() {
return length;
}

@Override
public int peek() {
if(length == 0)
throw new IllegalArgumentException("不存在栈顶元素");

return arr[length - 1];
}

@Override
public int pop() {
if(length == 0)
throw new IllegalArgumentException("出栈失败,栈顶为空");

int e = arr[length - 1];
length --;
// 当栈长度小于当前容量的4倍时就进行数据搬移,防止占用大量空间
// 这个时候也要判断 arr.length / 2 != 0,因为不能创建长度为0的数组
// 4倍才进行缩小是因为防止时间复杂度进行了震荡
if(length == arr.length / 4 && arr.length / 2 != 0)
resize(arr.length / 2);
return e;
}

@Override
public void push(int e) {
if(length >= arr.length)
resize(length * 2); // 扩容为当前两倍

arr[length] = e;
length ++;
}

// 动态扩容栈
public void resize(int capacity){
int [] newArr = new int[capacity];
for(int i = 0; i < length; i ++){
newArr[i] = arr[i];
}

arr = newArr;
}

@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("capacoty:%d, length:%d\n", arr.length, length));
res.append("ArrayStack: tail [");
for(int i = 0; i < length; i++){
res.append(arr[i]);
if(i != length - 1)
res.append(", ");
}
res.append("] top");
return res.toString();
}
栈的链式存储结构
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
public class LinkedListStack implements Stack {

class Node{
int data;
Node next;

public Node(int data, Node next){
this.data = data;
this.next = next;
}

public Node(int data){
this(data, null);
}
}

int length;
Node head;

public LinkedListStack(){
length = 0;
// 虚拟头节点
head = new Node(0);
}


@Override
public int length() {
return length;
}

@Override
public boolean isEmpty() {
return length == 0;
}

@Override
public void push(int e) {
// 直接插入链表的头部
Node node = new Node(e);
node.next = head.next;
head.next = node;
length++;
}

@Override
public int pop() {
if(length == 0)
throw new IllegalArgumentException("出栈失败,当前栈为空");

Node node = head.next;
head.next = node.next;
length --;
return node.data;
}

@Override
public int peek() {
if(length == 0)
throw new IllegalArgumentException("出栈失败,当前栈为空");

return head.next.data;
}

@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node node = head.next;
res.append(String.format("length: %d\n", length));
res.append("LinkedList: ");
for(int i = 0; i < length; i++){
res.append(node.data);
res.append(" --> ");
node = node.next;
}
res.append("NULL");

return res.toString();
}