锲而舍之,朽木不折;锲而不舍,金石可镂。 ---荀子《劝学》
在上一篇文章 数据结构(二)| 队列与栈 中,我用双向链表实现了队列和栈,本文用数组来实现。
由于栈的逻辑结构是先进后出,后进去的先出来,图解如下:
用数组实现栈
从图解看出,用数组实现栈时比较简单,只需要维护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来控制是否能插入取出,然后借助辅助指针来移动并记录数组下标。
仍然建议画图加深理解。