数据结构（三）| 用数组实现队列和栈
锲而舍之，朽木不折；锲而不舍，金石可镂。 ---荀子《劝学》
在上一篇文章 数据结构（二）| 队列与栈 中，我用双向链表实现了队列和栈，本文用数组来实现。
用数组实现栈
由于栈的逻辑结构是先进后出，后进去的先出来，图解如下：
用数组实现栈
从图解看出，用数组实现栈时比较简单，只需要维护index的值防止数组越界即可，代码实现：
public class MyStack {
private int[] array;
private int index;
public MyStack(int size) {
this.array = new int[size];
}
//入栈
public void push(int value) {
if (index >= array.length) {
throw new RuntimeException("栈满，不让加了");
}
array[index++] = value;
}
//出栈
public int pop() {
if (index <= 0) {
throw new RuntimeException("栈空，不能取出");
}
return array[--index];
}
}
用数组实现队列
我们再来图解分析一下，如何用数组实现队列。
入队列，依次加入1,2,3,4,5：
队列达到给定数组的长度个元素后，下面来分析一下从队列取出数据、再添加数据的过程：
要符合队列的先进先出特性，这个数组就像一个循环数组，当队列满（指队列元素个数达到指定数组长度）了，取出元素，再继续添加元素的时候，index又来到了开始的位置，如此往复。
现在我们假设两个指针，begin和end，再增加一个变量size来表示队列当前元素个数。
当size大于指定数组长度时，就不能往队列里插入数据了；当size<0时，就不能从队列取数据了——也就是说用这个size变量来控制能否push和pop。
当要插入数据时，将要插入的数据放到end的位置，然后让end++，此时需要注意下标越界的问题，若end大于等于size了，就需要将end设置到0的位置了，图解如下：
插入数据
当要取出数据时，因为队列的先进先出特点，最先进入到队列的数据在begin位置，所以从begin位置取数，同时让begin++，来到新的最早进入队列的数据位置，同理也要注意begin的下标是否越界。如下图所示：
利用begin和end指针操作队列
从上面的分析可知，插入数据和取出数据用size和begin、end指针就可以完成。
用数组实现队列的代码如下：
public static class MyQueue {
private int[] array;
private int begin;
private int end;
private int size;
public MyQueue (int limit) {
this.array = new int[limit];
this.begin = 0;
this.end = 0;
this.size = 0;
}
public void push (int value) {
size++;
if (size > array.length) {
throw new RuntimeException("队列满了");
}
array[end] = value;
end++;
//针对end越界的处理
if (end >= array.length) {
end = 0;
}
}
public int pop () {
size--;
if (size < 0) {
throw new RuntimeException("队列已空");
}
int result = array[begin];
begin++;
//针对begin越界的处理
if (begin >= array.length) {
begin = 0;
}
return result;
}
}
小结
用数组实现有技巧，需要根据size来控制是否能插入取出，然后借助辅助指针来移动并记录数组下标。
仍然建议画图加深理解。
腾讯云开发者
