一. 棧
- 介紹
??棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。限定僅能在表尾進(jìn)行插入和刪除操作。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
??棧是一種后進(jìn)先出（Last In First Out LIFO）的數(shù)據(jù)結(jié)構(gòu)。
棧
??棧在計(jì)算機(jī)中有著不可思議的作用，比如撤銷（Undo）操作、java程序調(diào)用的虛擬機(jī)棧、臨時(shí)存儲(chǔ)運(yùn)算數(shù)據(jù)的操作數(shù)棧等等。
- 實(shí)現(xiàn)
public interface Stack<E> {
//將元素入棧
public void push(E item) ;
//將元素出棧
public E pop() ;
// 獲取棧頂元素
public E peek() ;
// 棧是否為空
public boolean isEmpty();
}
//我們可以使用之前自定義的數(shù)組方式實(shí)現(xiàn)，只需要每次都從尾部添加和移除元素即可。
public class ArrayStack<E> implements Stack<E> {
private Array<E> array = new Array<>();
@Override
public void push(E item) {
array.addLast(item);
}
@Override
public E pop() {
return array.removeLast();
}
......
}
二. 隊(duì)列
- 定義
??隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。
入隊(duì)和出隊(duì)操作
??隊(duì)列是一種先進(jìn)先出（First In First Out）的線性結(jié)構(gòu)。
- 實(shí)現(xiàn)
public interface Queue<E> {
//獲得 隊(duì)列中的元素個(gè)數(shù)
int getSize();
// 隊(duì)列是否為空
boolean isEmpty();
//入隊(duì)
void enqueue(E e);
//出隊(duì)
E dequeue();
//獲得隊(duì)首元素
E getFront();
}
//同樣，我們可以使用之前自定義的動(dòng)態(tài)數(shù)組完成隊(duì)列的實(shí)現(xiàn)，只需要向數(shù)組尾部添加元素，從數(shù)組頭部獲取即可
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array = new Array<>();
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue() {
return array.removeFirst();
}
......
}
- 擴(kuò)展
??我們使用數(shù)組實(shí)現(xiàn)隊(duì)列時(shí)，在出隊(duì)時(shí)，由于移除的是數(shù)組中第一個(gè)位置的元素，所以會(huì)導(dǎo)致數(shù)組的其他元素往左移，使得出隊(duì)的時(shí)間復(fù)雜度變?yōu)?O(n)。
??所以我們可以將數(shù)組看做成一個(gè)環(huán)，在元素出隊(duì)時(shí)不進(jìn)行元素的移動(dòng)，而是修改隊(duì)首的指針；而在入隊(duì)時(shí)，當(dāng)數(shù)組的右側(cè)已經(jīng)無法容納元素時(shí)，在擴(kuò)容之前會(huì)首先尋找數(shù)組的左側(cè)是否有空閑的位置，如果有出隊(duì)的操作，則表示有空閑的位置，我們直接將入隊(duì)的元素放置到數(shù)組的左側(cè)，如果沒有空閑的位置，則進(jìn)行擴(kuò)容。具體流程如下：
入隊(duì)和出隊(duì)操作
public class LoopQueue<T> implements Queue<T>{
private T[] data;
private int font;
private int tail;
private int size;
public LoopQueue(int cap){
data = (T[])new Object[cap + 1];
}
@Override
public void enqueue(T t) {
//按照?qǐng)D中描述, 當(dāng) (tail + 1) % n = font 進(jìn)行擴(kuò)容
if((tail + 1) % data.length == font) resize(data.length * 2);
// 放置元素， 修改 tail 指向
data[tail] = t;
tail = (tail + 1)% data.length;
size ++;
}
@Override
public T dequeue() {
if(size == 0) return null;
//出隊(duì)，修改 font 指針指向
T ret = data[font];
font = (font + 1)% data.length;
size -- ;
return ret;
}
private void resize(int newcap){
T[] newArr =(T[]) new Object[newcap];
int len = data.length;
for (int i = 0; i <= size; i++) {
newArr[i] = data[(font + i) % len];
}
this.data = newArr;
font = 0;
tail = size;
}
}
