目录

堆栈

lienhui68 收录于技术

2020-06-12 约 914 字预计阅读 2 分钟次阅读

目录

介绍

栈的特点

先入后出的有序列表
限制线性表中元素的插入和删除只能在线性表的同一端进行，允许插入和删除的一端称为栈顶，固定的一端称为栈底。

应用场景

子程序的调用：会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
处理递归调用：和子程序调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
表达式的转换(中缀表达式转后缀表达式)与求值。
二叉树的遍历
图形的深度优先搜索法(depth-first search)

代码实现

使用数组实现

首先声明接口

 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


package com.eh.ftd.dsa.ds;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/17 14:10
 */
public interface Stack<E> {

    /**
     * 入栈
     *
     * @param e
     * @return
     */
    boolean push(E e);

    /**
     * 出栈
     *
     * @return
     */
    E pop();

    /**
     * 是否满
     *
     * @return
     */
    boolean isFull();

    /**
     * 是否空
     *
     * @return
     */
    boolean isEmpty();

    /**
     * 返回栈顶元素
     *
     * @return
     */
    E peek();
}

 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


package com.eh.ftd.dsa.ds.impl;

import com.eh.ftd.dsa.ds.Stack;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/17 14:11
 */
public class ArrayStack<E> implements Stack<E> {

    package com.eh.ftd.dsa.ds.impl;

import com.eh.ftd.dsa.ds.Stack;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/17 14:11
 */
public class ArrayStack<E> implements Stack<E> {

    private int capacity;
    private int top;
    private Object[] data;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        top = -1;
        data = new Object[capacity];
    }

    @Override
    public boolean push(E e) {
        if (isFull()) {
            return false;
        }
        data[++top] = e;
        return true;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        return (E) data[top--];
    }

    @Override
    public boolean isFull() {
        return top == capacity - 1;
    }

    @Override
    public boolean isEmpty() {
        return top == -1;
    }

    @Override
    public E peek() {
        return (E) data[top];
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new ArrayStack<>(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(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
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


package com.eh.ftd.dsa.ds.impl;

import com.eh.ftd.dsa.ds.Stack;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/17 14:22
 */
public class LinkedListStack<E> implements Stack<E> {

    private Node head = new Node();

    class Node<E> {

        public Node() {
        }

        public Node(E e) {
            this.e = e;
        }

        E e;
        Node next;

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    '}';
        }
    }

    @Override
    public boolean push(Object o) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(o);
        return true;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            return null;
        }
        Node temp = head;
        while (temp.next.next != null) {
            temp = temp.next;
        }
        Node res = temp.next;
        temp.next = null;
        return (E) res;
    }

    @Override
    public boolean isFull() {
        return false;
    }

    @Override
    public boolean isEmpty() {
        return head.next == null;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        return (E) temp.e;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new LinkedListStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

运行结果