数据结构第二篇, Stack&Queue

何为栈&队列结构

  • Stack 堆结构 常用于系统层面进程管理 有着先进后出的原则 例如Android程序View的展示 总是展示栈顶页面 按back键关闭的是栈顶页面
  • Queue 队列结构 常用于系统间通信 保证先发先到 有先进先出的原则 例如消息中间件MQ

实现原理分析

栈结构和堆结构，底层也是一个泛型的数组，只不过我们定了一些规则，保证其符合先进后出与先进后出的原则即可，并额外提供一些便捷方法。

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
//栈结构
public final class EStack<E> implements TStack<E> {

    private Array<E> stack;

    public EStack(int capacity) {
        stack = new Array<>(capacity, 0.4f);
    }

    public EStack() {
        stack = new Array<>();
    }

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

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

    /**
     * O(1) 均摊复杂度
     * @param e
     */
    @Override
    public void push(E e) {
        stack.put(e);
    }

    /**
     * O(1)
     * @return
     */
    @Override
    public E pop() {
        return stack.deleteLast();
    }

    /**
     * O(1)
     * @return
     */
    @Override
    public E peek() {
        return stack.getLast();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append('[');
        for (int i = 0; i < stack.getSize(); i++) {
            res.append(stack.get(i));
            if (i != stack.getSize() - 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
//队列结构
public final class EQueue<E> implements TQueue<E> {

    private Array<E> data;

    public EQueue() {
        data = new Array<>();
    }

    public EQueue(int capacity) {
        data = new Array<>(capacity);
    }

    public EQueue(int capacity, float limit) {
        data = new Array<>(capacity, limit);
    }

    @Override
    public void put(E e) {
        data.put(e);
    }

    @Override
    public E remove() {
        return data.delete(0);
    }

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

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

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

其中Array这个数据结构,来自于上篇文章’Data Structure Array’，其实就是数组的底层实现，非常简单
从代码中可以看到，无论是栈结构还是队列结构均是对Array的封装，对外屏蔽了Array的部分方法，添加了各自独有的方法从而实现了栈和队列。

其他

  • 本文源码的com.eddie.structure中
  • 下篇文章将开始更复杂的数据结构