数据结构与算法(四):栈

一、什么是栈

栈(stack)是一种先进后出的有序列表,其中的元素只能在线性表的同一端进出

允许元素插入和删除的一端被称为栈顶(top),固定的另一端被称为栈底(button)。

二、数组简单实现栈

由于栈是只在一端进出,也就是说相比队列实际上只需要有一个栈顶指针top即可:

  1. 当栈空时top为-1
  2. 入栈后top+1
  3. 出栈后top-1

根据思路我们可以用数组实现一个简单的栈:

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
/**
* @Author:huang
* @Date:2020-06-23 16:51
* @Description:使用数组模拟栈
*/
public class Stack {

private int maxSize;
private int top = -1;
private Object[] arr;

public Stack(int maxSize) {
this.maxSize = maxSize;
this.arr = new Object[maxSize];
}

/**
* 判断栈满
* @return
*/
public boolean isFull() {
return top == maxSize - 1;
}

/**
* 判断栈空
* @return
*/
public boolean isEmpty() {
return top == -1;
}

/**
* 入栈
* @param item
*/
public void push(Object item) {
//判断栈是否已满
if (isFull()) {
throw new RuntimeException("栈已满");
}
//入栈
top = top + 1;
arr[top] = item;
}

/**
* 出栈
*/
public Object pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空!");
}
Object item = arr[top];
top--;
return item;
}

/**
* 遍历栈
*/
public void show() {
if (isEmpty()) {
throw new RuntimeException("栈为空!");
}
//遍历并打印栈中元素
for (int i = top; i >= 0; i--) {
System.out.println("stack" + i + ":" + arr[i]);
}
}
}

三、链表简单模拟栈

数组可以比较简单的实现一个栈,但是缺点的数组随着元素的增加会需要扩容,如果初始化申请的存储空间太大,会造成空间的浪费,如果申请的存储空间太小,后期会经常需要扩充存储空间,为此我们可以用链表实现的栈来避免这个问题。

假设现有头结点,一号元素A,我们需要往里面插入或弹出B,,由于要实现“先进后出”的效果:

  1. 入栈时,B需要插入头结点和A之间,取代A的位置:
    • B.next = head.next,也就是B指向A
    • head.next = B.next,也就是让头结点指向B
  2. 出栈时,B需要从头结点和A之间移除:
    • head.next = A,也就是让头结点直接指向A即可

按照这个思路,我们先写一个节点类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @Author:huang
* @Date:2020-06-20 10:19
* @Description:节点类
*/
public class Node {

//数据
Object data;

//下一个节点
Node next;

public Node(Object data) {
this.data = data;
}
}

然后简单实现一个链表栈:

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
/**
* @Author:huang
* @Date:2020-06-23 21:30
* @Description:链表栈
*/
public class LinkListStack {

private Node head = new Node("我是头结点");

/**
* 判断是否空栈
* @return
*/
public boolean isEmpty() {
return head.next == null;
}

/**
* 添加节点到链表
* @param item 要插入的元素
*/
public void push(Object item) {
Node node = new Node(item);
Node temp = head;
//如果空栈就直接插入
if (isEmpty()) {
temp.next = node;
return;
}

//不是空栈就插到头结点头面
node.next = temp.next;
temp.next = node;
}

/**
* 将元素出栈
* @return 出栈元素
*/
public Object pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空!");
}
Node node = head.next;
head.next = node.next;
return node.data;
}

/**
* 遍历栈
*/
public void show() {
if (isEmpty()) {
throw new RuntimeException("栈为空!");
}
Node temp = head.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp.data);
temp = temp.next;
}
}
}
0%