数据结构===栈

栈的定义

栈是一种先进后出的数据结构。它的操作受限。

栈，是一种先进后出，或者后进先出的数据结构。跟数组和链表相比，有一定的限制性。毕竟，它也有自己的适用场景，比如：函数调用，表达式求值等等。栈有2个操作，入栈，出栈。时间复杂度都是O(1)。

实现一个栈

实现一个栈：怎么实现呢，有2种方式，用数组实现或者用链表实现。用数组实现的叫做顺序栈，用链表实现的叫做链式栈。

用数组实现栈

先用数组实现，不考虑扩容的情况，代码如下：

class Stack:
    def __init__(self):
        self.stack = []

    # 入栈操作
    def push(self, item):
        self.stack.append(item)

    # 出栈操作
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            return None

    # 查看栈顶元素
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            return None

    # 判断栈是否为空
    def is_empty(self):
        return len(self.stack) == 0

    # 获取栈的大小
    def size(self):
        return len(self.stack)
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

这是python的实现方式。可以再看下java的实现方式，如下图：

public class Stack {
    private int[] elements;
    private int top;
    private int capacity;

    // 初始化栈，设置初始容量
    public Stack(int capacity) {
        this.capacity = capacity;
        elements = new int[capacity];
        top = -1; // 初始时栈顶为-1，表示栈为空
    }

    // 入栈操作
    public void push(int item) {
        if (!isFull()) {
            top++;
            elements[top] = item;
        } else {
            System.out.println("栈已满，无法添加元素");
        }
    }

    // 出栈操作
    public int pop() {
        if (!isEmpty()) {
            return elements[top--];
        } else {
            System.out.println("栈为空，无法删除元素");
            return -1; // 或者可以抛出一个异常
        }
    }

    // 查看栈顶元素
    public int peek() {
        if (!isEmpty()) {
            return elements[top];
        } else {
            System.out.println("栈为空，没有元素可查看");
            return -1; // 或者可以抛出一个异常
        }
    }

    // 检查栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 检查栈是否已满
    private boolean isFull() {
        return top == capacity - 1;
    }

    // 获取栈的大小
    public int size() {
        return top + 1;
    }

    // 展示栈的内容（可选）
    public void displayStack() {
        if (isEmpty()) {
            System.out.println("栈为空");
        } else {
            for (int i = top; i >= 0; i--) {
                System.out.print(elements[i] + " ");
            }
            System.out.println();
        }
    }

    // 主函数，用于测试栈的实现
    public static void main(String[] args) {
        Stack stack = new Stack(5); // 创建一个容量为5的栈

        stack.push(1);
        stack.push(2);
        stack.push(3);

        stack.displayStack(); // 显示栈的内容

        System.out.println("栈顶元素: " + stack.peek());

        stack.pop();
        stack.pop();

        stack.displayStack(); // 再次显示栈的内容

        System.out.println("栈的大小: " + stack.size());
        System.out.println("栈是否为空: " + stack.isEmpty());
    }
}
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

用链表实现栈

用数组实现完了，再用链表实现，如下图：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    # 入栈操作
    def push(self, data):
        if self.top is None:
            self.top = Node(data)
        else:
            new_node = Node(data)
            new_node.next = self.top
            self.top = new_node

    # 出栈操作
    def pop(self):
        if self.top is None:
            return None
        else:
            popped = self.top.data
            self.top = self.top.next
            return popped

    # 查看栈顶元素
    def peek(self):
        return self.top.data if self.top else None

    # 判断栈是否为空
    def is_empty(self):
        return self.top is None

# 测试代码
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())  # 输出：3
print(s.peek())  # 输出：2
print(s.is_empty())  # 输出：False
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

java的实现方式，如下图：

public class Node<T> {
    private T data;
    private Node<T> next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

public class LinkedListStack<T> {
    private Node<T> top;

    public LinkedListStack() {
        this.top = null;
    }

    // 入栈操作
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.setNext(top);
        top = newNode;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        T data = top.getData();
        top = top.getNext();
        return data;
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.getData();
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == null;
    }

    // 获取栈的大小
    public int size() {
        int size = 0;
        Node<T> current = top;
        while (current != null) {
            size++;
            current = current.getNext();
        }
        return size;
    }

    // 测试代码
    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        stack.push(200);
        stack.push(300);
        stack.push(600);
        System.out.println(stack.pop());  
        System.out.println(stack.peek());  
        System.out.println(stack.isEmpty()); 
        System.out.println(stack.size());  
    }
}
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

好了，实现方式就是这样的。再来看看动态扩容的栈是怎么实现的。

支持动态扩容的栈

这个跟普通的栈有一个不同的地方，在入栈的时候栈满了会进行扩容，然后复制之前的数据，再进行入栈操作。用java实现，如下图：

public class DynamicArrayStack<T> {
    private static final int DEFAULT_CAPACITY = 10;
    private static final int RESIZE_FACTOR = 2;
    private Object[] elements;
    private int top;

    public DynamicArrayStack() {
        elements = new Object[DEFAULT_CAPACITY];
        top = -1;
    }

    // 入栈操作
    public void push(T item) {
        ensureCapacity();
        elements[++top] = item;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elements[top--];
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elements[top];
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 获取栈的大小
    public int size() {
        return top + 1;
    }

    // 确保数组有足够的容量
    private void ensureCapacity() {
        if (top == elements.length - 1) {
            resize();
        }
    }

    // 调整数组大小
    private void resize() {
        int newSize = elements.length * RESIZE_FACTOR;
        elements = Arrays.copyOf(elements, newSize);
    }

    // 测试代码
    public static void main(String[] args) {
        DynamicArrayStack<Integer> stack = new DynamicArrayStack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop());  // 输出：3
        System.out.println(stack.peek());  // 输出：2
        System.out.println(stack.size());  // 输出：2
        System.out.println(stack.isEmpty());  // 输出：false
    }
}
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

栈的应用

栈应用非常多，比如，在浏览器里有个向前，向后的箭头，就可以用2个栈来存储；函数的调用，也是可以用栈的。例子就不多举了。

小结

这篇文章讲述了栈的数据结构。

主要是讲解了栈的数据结构，以及实现，目的是了解底层的数据结构及应用，还有动态扩容的栈，栈的时间复杂度，空间复杂度都是O(1)。基本上就这么多。至于实现，用什么语言不重要，原理懂了，写一个，应该都不是什么难事。