个人博客

栈和队列

2021/5/1

# 栈

# 栈的定义

栈是一个后进先出（Last In Fist Out, LIFO）的线性表，它要求只在表尾进行删除和插入操作。

所谓的栈，其实就是一个特殊的线性表（顺序表、链表），但是它在操作上有一些特殊的要求和限制：

  • 栈的元素必须“后进先出”
  • 栈的操作只能在这个线性表的表尾进行。
  • 对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

# 栈的插入和删除操作

栈的插入操作（Push），叫做进栈，也称为压栈，入栈。

栈的删除操作（Pop），叫做出栈，也称为弹栈。

# 存储结构

因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也分为栈的顺序存储结构和栈的连式存储结构。

# 顺序存储结构

栈的顺序结构

最开始栈中不包含任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

# 链式存储结构

栈的链式存储

# 队列

# 定义

队列 (Queue) 是一种限定性的有序线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出 (Fist In Fist Out，缩写为FIFO)的特性。

  1. 在队列中，允许插入的一端叫做队尾(rear)；
  2. 允许删除的一端则称为队头(front)。
  3. 队列是一个有序列表，可以用数组或是链表来实现。
  4. 遵循先进先出的原则。即:先存入队列的数据，要先取出。

# 抽象数据类型

数据元素：可以是任意类型的数据，但必须属于同一个数据对象。

关系：队列中数据元素之间是线性关系。

基本操作:

  1. 初始化操作。使用构造方法设置一个空队列。
  2. isEmpty():判空操作。若队列为空，则返回TRUE，否则返回FALSE。
  3. isFull():判满操作。若队列为满,则返回TRUE，否则返回FALSE。
  4. getSize():获取队列元素个数。
  5. add(E e):进队操作。在队列Q的队尾插入e。如果队满，抛出异常。
  6. poll():出队操作。使队列Q的队头元素出队，并用e返回其值。如果队空，抛出异常。
  7. getHead ():取队头元素操作。用e取得队头元素的值。如果队列为空，则返回null。
  8. clear():队列置空操作。将队列Q置为空队列。
  9. destroy():队列销毁操作。释放队列的空间。

# 顺序存储

队列的一种顺序存储称为顺序队列。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组Queue[maxSize]。

# 数组队列

由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针 front和 rear。

  • front：指示队头元素在数组中的位置;
  • rear：指示真实队尾元素相邻的下一个位置。

# 思路分析

  • 初始化队列时，令front = rear = 0。
  • 判断队空的条件：front == rear。
  • 判断队满的条件：rear == maxSize。
  • 入队时，若尾指针rear 小于队列的最大下标 maxSize,则将数据存入rear所指的数组元素中,否则无法存入数据；然后将尾指针往后移: rear + 1。
  • 出队时，若队列不为空，取出队头指针front所指的元素；然后将尾指针往后移: front + 1。

# 代码实现

定义接口方法：

/**
 * description:自定义队列接口
 *
 * @author RenShiWei
 * Date: 2021/5/29 20:45
 **/
public interface Queue<E> {

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

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

    /**
     * @return 队列的可承载元素个数
     */
    int getCapacity();

    /**
     * @return 队列元素个数
     */
    int getSize();

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    void add(E e);

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    E poll();

    /**
     * 获取队首元素
     *
     * @return 队首元素
     */
    E getHead();

}
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

数组队列实现：

/**
 * description:数组队列
 *
 * @author RenShiWei
 * Date: 2021/5/29 20:41
 **/
public class ArrayQueue<E> implements Queue<E> {

    /** 表示可存储元素的最大容量 */
    private int maxSize;
    /** 队列头 */
    private int front;
    /** 队列尾 */
    private int rear;
    /** 该数据用于存放数据，模拟队列 */
    private E[] data;

    /**
     * 初始化队列
     *
     * @param arrMaxSize 初始队列最大容量
     */
    @SuppressWarnings("unchecked")
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        data = (E[]) new Object[maxSize];
        front = 0;
        rear = 0;
    }

    /**
     * @return 是否队空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否队满
     */
    @Override
    public boolean isFull() {
        return rear == maxSize;
    }

    /**
     * @return 队列元素个数
     */
    @Override
    public int getSize() {
        return rear - front;
    }

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            throw new IllegalArgumentException("队列已满，不能入队！");
        }
        data[rear++] = e;
    }

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空，不能出队！");
        }
        //出队位置置null
        E temp = data[front];
        data[front++] = null;
        return temp;
    }

    /**
     * 获取队首元素
     * 如果队空，返回null
     *
     * @return 队首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    /**
     * @return 队列的可承载元素个数
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 队列的有效容量（未使用的空间数量）
     */
    public int getEmptyCount() {
        return maxSize - rear;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for (int i = front; i < rear; i++) {
            res.append(data[i]);
            if (i != rear - 1) {
                res.append(", ");
            }
        }
        res.append("] rear");
        return res.toString();
    }

    /**
     * 队列测试
     */
    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>(5);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):输出队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("p(poll):从队列取出数据");
            System.out.println("h(getHead):查看队列头的数据");
            System.out.println("n(isEmpty):是否队空");
            System.out.println("f(isFull):是否队满");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("当前队列：" + queue.toString() + "\t元素个数：" + queue.getSize() + "\t有效容量：" + queue.getEmptyCount());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("请输入一个整数");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出队元素：%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("队首元素：%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("队空：" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("队满：" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        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
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

# 分析

# 假溢出现象

在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素。当rear == maxSize - 1 时，认为队满。但此时不一定是真的队满，因为随着部分元素的出队，数组前面会出现一些空单元，如下图所示。由于只能在队尾入队，使得上述空单元无法使用。把这种现象称为假溢出。

image-20210529183259424

问题：目前这个数组使用一次就不能用（出队的空间），没有达到复用的效果。可使用算法将其改造成环形队列（取模：%）。

# 环形队列

为了解决假溢出现象并使得队列空间得到充分利用,一个较巧妙的办法是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，我们形象地称之为循环队列。

# 思路分析

  • 初始化队列时，令front = rear = 0。front指向队列的第一个元素，rear指向队列最后一个元素的后一个位置（希望损失一个位置作为约定，用来区分队空和队满）。
  • 判断队空的条件：front == rear。
  • 判断队满的条件：(rear + 1) % maxSize == front。
  • 队列中的元素个数：(rear + maxSize - front) % maxSize。
  • 入队时，将数据存入rear所指的数组元素中，指针变化：rear = ( rear+1) % maxSize。
  • 出队时，将数据存入front所指的数组元素中，指针变化：front = ( front+1 ) % maxSize。

下图给出了循环队列的几种情况：

image-20210530163134963

# 代码实现

/**
 * description:循环队列
 *
 * @author RenShiWei
 * Date: 2021/5/30 16:38
 **/
public class LoopQueue<E> implements Queue<E> {

    /** 存储元素 数组的长度（有效长度需要-1） */
    private int maxSize;
    /** 队列头 */
    private int front;
    /** 队列尾 */
    private int rear;
    /** 该数据用于存放数据，模拟队列 */
    private E[] data;

    /**
     * 初始化环形队列
     *
     * @param arrMaxSize 初始队列容量
     */
    @SuppressWarnings("unchecked")
    public LoopQueue(int arrMaxSize) {
        //循环队列需要有意识浪费一个空间
        maxSize = arrMaxSize + 1;
        data = (E[]) new Object[maxSize];
    }

    /**
     * @return 是否队空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否队满
     */
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * @return 队列的可承载元素个数
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 队列元素个数
     */
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            throw new IllegalArgumentException("队列已满，不能入队！");
        }
        data[rear] = e;
        //rear指针后移一位
        rear = (rear + 1) % maxSize;
    }

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空，不能出队！");
        }
        E temp = data[front];
        //出队位置置null
        data[front] = null;
        //front指针后移一位
        front = (front + 1) % maxSize;
        return temp;
    }

    /**
     * 获取队首元素
     * 如果队空，返回null
     *
     * @return 队首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != rear) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    /**
     * 队列测试
     */
    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>(5);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):输出队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("p(poll):从队列取出数据");
            System.out.println("h(getHead):查看队列头的数据");
            System.out.println("n(isEmpty):是否队空");
            System.out.println("f(isFull):是否队满");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("当前队列：" + queue.toString());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("请输入一个整数");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出队元素：%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("队首元素：%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("队空：" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("队满：" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        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
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

# 分析

相比数组队列来说，循环队列解决了数组空间不能再次利用的问题。但依然存在一些问题：

  • 当队列真的满的时候就不能再进行入队操作了。但是从我们常用的ArrayList来分析，在存储空间允许的条件下是可以一直添加元素的。
  • 当数组元素频繁进行入队或者出队操作时，可能造成空间的浪费。循环队列其实只利用了有限的存储空间，但是在最初实例化循环队列的时候，如果空间声明的很大，那么会造成一定程度上的空间浪费。
    • 假设，声明一个容量为20的循环队列，但每次入队2个元素后，又出队2个元素，那么实际只利用了很有限的空间，造成了空间浪费，但又不能声明的空间太小，并不能保证未来每次只入队或者出队2个元素。

因此，是否可以实现动态的将循环队列进行扩容或者缩容，上述两个问题，可以利用下面的==动态循环队列==来实现。

当然，上述的数组队列，也可以改造成动态的，但是出队元素的空间依然会浪费，所以没必要进行实现。

# 动态循环队列

为了解决循环队列，队满不能入队，以及频繁入队出队引起的空间浪费，而引出动态循环队列的概念。即在队满时进行扩容，在队列元素个数下降到一定情况下进行缩容。

# 思路分析

  • 除了入队和出队操作，其他操作均与循环队列相同。
  • 循环队列存储元素的数组容量变更思路：使用==扩容一倍/缩容一倍==的新数组接收原来循环队列存储的元素。接收后，将front指针置为0；将rear指针值到最后一个元素的位置（即存储有效元素的数量）。
  • 什么时候扩容：队满
  • 什么时候缩容：队列元素只有1/4，并且缩容后容量不为0。
    • 数组容量为0时，缩容会出现异常
    • 为什么不在队列元素只有1/2时缩容？当数组元素为一半的时候一次添加，一次删除，造成的一直扩容和减小的操作。

# 代码实现

/**
 * description:动态循环
 *
 * @author RenShiWei
 * Date: 2021/5/30 17:06
 **/
public class DynamicLoopQueue<E> implements Queue<E> {

    /** 存储元素 数组的长度（有效长度需要-1） */
    private int maxSize;
    /** 队列头 */
    private int front;
    /** 队列尾 */
    private int rear;
    /** 该数据用于存放数据，模拟队列 */
    private E[] data;

    /**
     * 初始化环形队列
     *
     * @param arrMaxSize 初始队列容量
     */
    @SuppressWarnings("unchecked")
    public DynamicLoopQueue(int arrMaxSize) {
        //循环队列需要有意识浪费一个空间
        maxSize = arrMaxSize + 1;
        data = (E[]) new Object[maxSize];
    }

    /**
     * @return 是否队空
     */
    @Override
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * @return 是否队满
     */
    @Override
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * @return 队列的可承载元素个数
     */
    @Override
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @return 队列元素个数
     */
    @Override
    public int getSize() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 队尾入队
     *
     * @param e 入队元素
     */
    @Override
    public void add(E e) {
        if (isFull()) {
            //队满不再进行报错，而是进行动态扩容
            resize(getCapacity() * 2);
        }
        data[rear] = e;
        //rear指针后移一位
        rear = (rear + 1) % maxSize;
    }

    /**
     * 队首出队
     *
     * @return 出队元素
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空，不能出队！");
        }
        E temp = data[front];
        //出队位置置null
        data[front] = null;
        //front指针后移一位
        front = (front + 1) % maxSize;

        //当数组实际元素减小到空间的一半的时候，对其进行缩小
        //if(size == data.length / 2)
        /*
            解决当一半的时候一次添加，一次删除，造成的一直扩容和减小的操作，
            增加必须要扩容，所以可以让缩容变得更懒时在进行，即1/4时
            data.length / 2 != 0防止数组大小最后变成0，造成异常
        */
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return temp;
    }

    /**
     * 获取队首元素
     * 如果队空，返回null
     *
     * @return 队首元素
     */
    @Override
    public E getHead() {
        return data[front];
    }

    /**
     * 扩容方法
     *
     * @param newCapacity 扩容后的队列大小
     */
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        //有多个元素循环多少次
        for (int i = 0; i < getSize(); i++) {
            //循环队列会发生偏移，重新赋值给新数组
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        maxSize = data.length;
        //重置指针
        front = 0;
        rear = getSize();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != rear; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != rear) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    /**
     * 队列测试
     */
    public static void main(String[] args) {
        DynamicLoopQueue<Integer> queue = new DynamicLoopQueue<>(3);
        Scanner sc = new Scanner(System.in);
        char c;
        boolean loop = true;
        while (loop) {
            System.out.println("s(toString):输出队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("p(poll):从队列取出数据");
            System.out.println("h(getHead):查看队列头的数据");
            System.out.println("n(isEmpty):是否队空");
            System.out.println("f(isFull):是否队满");
            c = sc.next().charAt(0);
            switch (c) {
                case 's':
                    System.out.println("当前队列：" + queue.toString());
                    break;
                case 'e':
                    sc.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("请输入一个整数");
                    queue.add(sc.nextInt());
                    break;
                case 'p':
                    System.out.printf("出队元素：%d\n", queue.poll());
                    break;
                case 'h':
                    System.out.printf("队首元素：%d\n", queue.getHead());
                    break;
                case 'n':
                    System.out.println("队空：" + queue.isEmpty());
                    break;
                case 'f':
                    System.out.println("队满：" + queue.isFull());
                    break;
                default:
                    break;
            }
        }
        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
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