devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构-线性结构：栈（Stack）【底层依托“动态数组”/“链表”】【“栈”的操作是“动态数组”操作的子集；“栈”只能同一端（称为“栈顶”）添加元素、取出元素；“后进先出”】_栈的底层数据结构

作者：盐析白兔 | 2024-05-29 08:15:33

赞

踩

栈的底层数据结构

栈（stack） ：只能允许在一端进行加入数据和输出数据的线性表（可由顺序表(动态数组)或链表通过特定操作来实现栈规定的特性）

栈（stack）：有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

在这里插入图片描述

一、 “栈”的操作

方法作用
Stack()创建一个新的空栈
push(item)添加一个新的元素item到栈顶
pop()弹出栈顶元素
peek()返回栈顶元素
is_empty()判断栈是否为空
size()返回栈的元素个数

在这里插入图片描述

二、 “栈”的应用

  • undo操作-编辑器
  • 系统调用栈-操作系统
  • 括号匹配-编译器（LeetCode20）

三、 “栈”结构的代码实现

栈可以用顺序表(动态数组)（python中的list数据结构是一种顺序表(动态数组)）实现，也可以用链表实现。

基于“动态数组”的栈、基于“链表”的栈整体上时间复杂度基本一致；最多2~3倍的差异；绝不会出现几百倍的差异；

1、基于“动态数组”的栈

java代码：

MyStack.java

public interface MyStack<T> {
    int getCapacity();  // 获取栈的容量

    int getSize();  // 获取栈的大小

    boolean isEmpty();  // 判断栈是否为空

    void push(T element);   // 压栈

    T pop();    // 出栈

    T peek();   // 获取栈顶元素
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

MyArray.java

public class MyArray<T> {
    private T[] data;
    private int size;

    public MyArray(int capacity){
        data = (T[])new Object[capacity];
        size = 0;
    }

    //默认构造方法，初始化最大容量为10
    public MyArray(){
        this(10);
    }

    //获取数组的大小
    public int getSize(){
        return size;
    }

    //获取数组最大容量
    public int getCapacity(){
        return data.length;
    }

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

    //向数组末尾添加元素
    public void add(T element){
        add(size, element);
    }

    //向数组中指定位置添加元素
    public void add(int index, T element){
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
        }
        if (size == data.length){
            resize(data.length * 2);
        }
        for (int i = size - 1; i >= index; i--){
            data[i + 1] = data[i];
        }
        data[index] = element;
        size++;
    }

    //获取指定位置的元素
    public T get(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get faild. Index is illegal.");
        }
        return data[index];
    }

    //修改指定位置的元素
    public void set(int index, T element){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Set faild. Index is illegal.");
        }
        data[index] = element;
    }

    //查找数组中是否包含该元素
    public boolean contains(T element){
        for (int i = 0; i < size; i++){
            if (data[i].equals(element)){
                return true;
            }
        }
        return false;
    }

    //查找该元素的下标
    public int indexOf(T element){
        for (int i = 0; i < size; i++){
            if (data[i].equals(element)){
                return i;
            }
        }
        return -1;
    }

    //删除数组末尾的元素
    public T remove(){
        return remove(size - 1);
    }

    //删除数组中指定位置的元素
    public T remove(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Remove faild. Index is illegal.");
        }

        T element = data[index];
        for (int i = index + 1; i < size; i++){
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;

        if (size == data.length / 4 && data.length / 2 != 0){
            resize(data.length / 2);
        }
        return element;
    }

    //删除数组中指定的元素
    public boolean remove(T element){
        int index = indexOf(element);
        if (index != -1){
            remove(index);
            return true;
        }
        return false;
    }

    //对数组进行扩容或缩容
    private void resize(int capacity){
        T[] newData = (T[])new Object[capacity];
        for (int i = 0; i < size; i++){
            newData[i] = data[i];
        }
        data = newData;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("[");
        for (int i = 0; i < size; i++){
            string.append(data[i]);
            if (i != size - 1){
                string.append(", ");
            }
        }
        string.append("]");
        return string.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
  • 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
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141

MyArrayStack.java

//基于动态数组的栈
public class MyArrayStack<T> implements MyStack<T> {

    MyArray<T> array;

    public MyArrayStack(int capacity) {
        array = new MyArray<>(capacity);
    }

    public MyArrayStack() {
        array = new MyArray<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }


    @Override
    public void push(T element) {
        array.add(element);
    }

    @Override
    public T pop() {
        return array.remove();
    }

    @Override
    public T peek() {
        return array.get(array.getSize() - 1);
    }

    @Override
    public int getCapacity() {
        return array.getCapacity();
    }


    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("Stack: ");
        string.append("bottom [");
        for (int i = 0; i < array.getSize(); i++){
            string.append(array.get(i));
            if (i != array.getSize() - 1){
                string.append(", ");
            }
        }
        string.append("] top");
        return string.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

Main.java

public class Main {
    public static void main(String[] args){
        MyStack<String> stack = new MyArrayStack<>();
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");

        stack.push("a");
        stack.push("b");
        stack.push("c");
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");

        System.out.println("返回栈顶元素：stack.peek() = " + stack.peek());
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");

        System.out.println("弹出栈顶元素：stack.pop() = " + stack.pop());
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");
        
        MyArrayStack stack02 = new MyArrayStack();
        for(int i = 0; i< 5; i++){
            stack02.push(i);
            System.out.println(stack02);
        }
        System.out.println("========================================================================================");
        stack02.pop();
        System.out.println(stack02);
        System.out.println("========================================================================================");
    }
}

  • 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

输出结果：

stack.getCapacity() = 10
stack.getSize() = 0
stack.isEmpty() = true
stack = Stack: bottom [] top
========================================================================================
stack.getCapacity() = 10
stack.getSize() = 3
stack.isEmpty() = false
stack = Stack: bottom [a, b, c] top
========================================================================================
返回栈顶元素：stack.peek() = c
stack.getCapacity() = 10
stack.getSize() = 3
stack.isEmpty() = false
stack = Stack: bottom [a, b, c] top
========================================================================================
弹出栈顶元素：stack.pop() = c
stack.getCapacity() = 5
stack.getSize() = 2
stack.isEmpty() = false
stack = Stack: bottom [a, b] top
========================================================================================
Stack: bottom [0] top
Stack: bottom [0, 1] top
Stack: bottom [0, 1, 2] top
Stack: bottom [0, 1, 2, 3] top
Stack: bottom [0, 1, 2, 3, 4] top
========================================================================================
Stack: bottom [0, 1, 2, 3] top
========================================================================================

Process finished with exit code 0

  • 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

2、基于“链表”的栈

MyStack.java

public interface MyStack<T> {
    int getCapacity();  // 获取栈的容量

    int getSize();  // 获取栈的大小

    boolean isEmpty();  // 判断栈是否为空

    void push(T element);   // 压栈

    T pop();    // 出栈

    T peek();   // 获取栈顶元素
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

MyLinkedList.java

/**
 * Title: 带虚拟头结点的链表
 * Description:
 * 链表结构包含两个要素： 头结点head + 链表大小size，
 * 操作包括：
 * 链表的增删
 * 链表是否为空
 * 链表的大小
 * 链表的打印输出
 * 删除链表重复节点
 * 链表倒数第K个元素
 * 链表的反转
 * 链表的倒序输出
 * 链表的中间节点
 * 链表是否有环
 * 链表节点的删除(不知道头结点的情况下)
 * 链表是否相交
 * 链表的交点
 */
public class MyLinkedList<E> {
    // 节点
    private class Node {
        private E elem;
        private Node next;

        private Node(E elem, Node next) {
            this.elem = elem;
            this.next = next;
        }

        private Node(E elem) {
            this(elem, null);
        }

        private Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return elem.toString();
        }
    }

    private Node dummyHead; // 链表虚拟头节点
    private int size; // 链表大小

    // 初始化链表
    public MyLinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    // 获取链表的头结点
    public Node getHead() {
        return dummyHead;
    }

    // 获取链表中的元素个数
    public int getSize() {
        return size;
    }

    // 链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }


    // 在链表的index(0-based)位置添加新的元素elem【此操作在链表中不是一个常用的操作，仅仅练习使用】
    public void add(int index, E elem) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("超出范围...");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {   // 查找插入处(index处)的前一个节点
            prev = prev.next;   // 最后一个 prev.next 表示 index节点
        }
/*            Node node = new Node(elem); // 将新元素链入链表
            node.next = prev.next;
            prev.next = node;*/
        prev.next = new Node(elem, prev.next);  // 新建一个Node节点，让该节点的next指针指向head，然后让head指向该节点【完成插入头结点的操作，和上面三行代码结果相同】
        size++;
    }

    // 重载添加方法，如果不写添加元素的下标，则默认添加头节点
    public void add(E elem) {
        addFirst(elem);
    }

    // 链表头添加新的元素elem
    public void addFirst(E elem) {
        add(0, elem);
    }

    // 在链表末尾添加新的元素elem
    public void addLast(E elem) throws Exception {
        add(size, elem);
    }

    // 获得链表的第index(0-based)个位置的元素【此操作在链表中不是一个常用操作，仅仅练习使用】
    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("超出范围...");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.elem;
    }

    // 获得链表的第一个元素
    public E getFirst() {
        return get(0);
    }

    // 获得链表的最后一个元素
    public E getLast() {
        return get(size - 1);
    }

    // 修改链表的第index(0-based)个位置的元素为elem【此操作在链表中不是一个常用操作，仅仅练习使用】
    public void set(int index, E elem) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("超出范围...");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.elem = elem;
    }

    // 查找链表中是否有元素elem
    public boolean contains(E elem) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.elem.equals(elem)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 从链表汇总删除第index(0-based)个位置的元素【此操作在链表中不是一个常用操作，仅仅练习使用】
    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("超出范围...");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node retNode = prev.next;   // retNode代表待删除节点
        prev.next = retNode.next;   // 将待删除节点的前一个节点的next指向待删除节点的下一个节点
        retNode.next = null;   // 将待删除节点的next指向null
        size--;

        return retNode.elem;
    }

    // 删除链表中该元素的节点
    public void remove(E elem) {
        if (elem == null) {
            return;
        }
        Node prev = dummyHead;
        Node node = dummyHead.next;
        while (node != null) {
            if (elem.equals(node.elem)) {
                prev.next = node.next;
                node.next = null;
                size--;
                break;
            }
            prev = prev.next;
            node = node.next;
        }
    }

    // 从链表中删除第一个元素，返回删除的元素
    public E removeFirst() {
        return remove(0);
    }

    // 从链表中删除最后一个元素，返回删除的元素
    public E removeLast() {
        return remove(size - 1);
    }


    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
//        for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
//            string.append(cur + "->");
//        }
        Node cur = dummyHead.next;
        while (cur != null) {
            string.append(cur + "->");
            cur = cur.next;
        }
        string.append("NULL");

        return string.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
  • 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
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211

MyLinkedListStack.java

/**
 * @name MyLinkedListStack
 * @description 基于链表的栈
 */
public class MyLinkedListStack<T> implements MyStack<T> {

    private MyLinkedList<T> list;

    public MyLinkedListStack(){
        list = new MyLinkedList<>();
    }

    @Override
    public int getCapacity() {
        return 0;
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public void push(T element) {
        list.addFirst(element);
    }

    @Override
    public T pop() {
        return list.removeFirst();
    }

    @Override
    public T peek() {
        return list.getFirst();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("Stack: top ");
        string.append(list);
        return string.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

Main.java

public class Main {
    public static void main(String[] args){
        MyStack<String> stack = new MyLinkedListStack<>();
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");

        stack.push("a");
        stack.push("b");
        stack.push("c");
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");

        System.out.println("返回栈顶元素：stack.peek() = " + stack.peek());
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");

        System.out.println("弹出栈顶元素：stack.pop() = " + stack.pop());
        System.out.println("stack.getCapacity() = " + stack.getCapacity());
        System.out.println("stack.getSize() = " + stack.getSize());
        System.out.println("stack.isEmpty() = " + stack.isEmpty());
        System.out.println("stack = " + stack);
        System.out.println("========================================================================================");

        MyLinkedListStack stack02 = new MyLinkedListStack();
        for(int i = 0; i< 5; i++){
            stack02.push(i);
            System.out.println(stack02);
        }
        System.out.println("========================================================================================");
        stack02.pop();
        System.out.println(stack02);
        System.out.println("========================================================================================");
    }
}

  • 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

输出结果：

stack.getCapacity() = 0
stack.getSize() = 0
stack.isEmpty() = true
stack = Stack: top null
========================================================================================
stack.getCapacity() = 0
stack.getSize() = 3
stack.isEmpty() = false
stack = Stack: top c->b->a->null
========================================================================================
返回栈顶元素：stack.peek() = c
stack.getCapacity() = 0
stack.getSize() = 3
stack.isEmpty() = false
stack = Stack: top c->b->a->null
========================================================================================
弹出栈顶元素：stack.pop() = c
stack.getCapacity() = 0
stack.getSize() = 2
stack.isEmpty() = false
stack = Stack: top b->a->null
========================================================================================
Stack: top 0->null
Stack: top 1->0->null
Stack: top 2->1->0->null
Stack: top 3->2->1->0->null
Stack: top 4->3->2->1->0->null
========================================================================================
Stack: top 3->2->1->0->null
========================================================================================

Process finished with exit code 0

  • 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

python代码：

class Stack(object):
    """栈"""

    def __init__(self):
        self.__items = []

    def is_empty(self):
        """判断栈是否为空"""
        return self.__items == []

    def push(self, item):
        """加入一个新的元素item到栈顶"""
        # self.__items .insert(0,item)  # 往items这个list的头部添加新元素（时间复杂度为O(n)）
        self.__items.append(item)  # 往items这个list的尾部添加新元素（时间复杂度为O(1)）

    def pop(self):
        """弹出栈顶元素"""
        return self.__items.pop()  # 从items这个list的尾部取出一个元素（时间复杂度为O(1)）

    def peek(self):
        """返回栈顶元素"""
        if self.__items:
            return self.__items[- 1]  # 展示items这个list的尾部元素
        else:
            return None

    def size(self):
        """返回栈的大小"""
        return len(self.__items)  # 展示items这个list的长度


if __name__ == "__main__":
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print('栈的大小', stack.size())
    print('返回栈顶元素', stack.peek())
    print('弹出栈顶元素', stack.pop())
    print('弹出栈顶元素', stack.pop())
    print('弹出栈顶元素', stack.pop())

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/641300
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号