隊列是先入先出的結(jié)構(gòu),這和下壓棧的規(guī)則一樣竟秫,實現(xiàn)一個隊列和實現(xiàn)一個下壓棧很類似情龄,所以我們可以先設定一個變量pointer指向棧頂,將新元素添加到array[pointer]之中寂恬,然后對pointer自增,出隊的時候莱没,彈出棧頂?shù)脑丶纯伞?/p>
可以先設置隊列的規(guī)則:
public interface IQueue<T> {
void push(T item);
T pop();
T peek();
int size();
boolean isEmpty();
void resize(int capacity);
}
在添加和刪除的時候初肉,需要判斷數(shù)組的非空元素的個數(shù),對數(shù)組做對應的resize:
1.push的時候饰躲,如果pointer == array.length,就將數(shù)組的容量擴充一倍
2.pop的時候牙咏,如果pointer == array.length / 4,就將數(shù)組的容量減少一半
隊列的具體代碼如下:
public class ArrayQueue<T> implements IQueue<T> {
private T[] items;
private int pointer;//指向棧頂
public T ArrayQueue() {
this.items = (T[]) new Object[10];
}
@Override
public void push(T item) {
if(pointer == items.length) resize(2 * items.length);
items[pointer++] = item;
}
@Override
public T pop() {
T item = items[pointer - 1];
//防止對象游離
items[pointer -1] = null;
pointer --;
if(pointer > 0 && pointer == items.length /4) resize(items.length / 2);
return item;
}
/**
* 出隊但不刪除
* @return
*/
@Override
public T peek() {
return items[pointer - 1];
}
@Override
public int size() {
return pointer;
}
@Override
public boolean isEmpty() {
return pointer == 0;
}
@Override
public void resize(int capacity) {
if(capacity >= pointer){
T[] temp = (T[]) new Object[capacity];
for(int i = 0; i < capacity; i++){
temp[i] = items[i];
}
items = temp;
}
}
}