目錄???????

前言

1、棧

?2、隊(duì)列

2.1、實(shí)現(xiàn)隊(duì)列

2.2、循環(huán)隊(duì)列

---

前言

上一篇中我們介紹了數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)中的《動(dòng)態(tài)數(shù)組》，本篇我們繼續(xù)來學(xué)習(xí)兩種基本的數(shù)據(jù)結(jié)構(gòu)——棧和隊(duì)列。

1、棧

特點(diǎn)：棧也是一種線性結(jié)構(gòu)，相比數(shù)組，棧對(duì)應(yīng)的操作是數(shù)組的子集，只能從一端添加元素，也只能從同一端取出元素，這一端稱為棧頂。棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，即Last In First Out(LIFO)。

上面說到棧對(duì)應(yīng)的操作是數(shù)組的子集，因此我們就基于上一篇中實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組來快速的實(shí)現(xiàn)一個(gè)棧。

首先定義一個(gè)接口，定義相關(guān)功能方法：

然后讓棧來實(shí)現(xiàn)接口中的具體功能：

import arr.Array;public class ArrayStack<E> implements Stack<E> {Array<E> array;public ArrayStack(int capacity) {array = new Array<>(capacity);}public ArrayStack() {array = new Array<>();}public int getCapacity() {return array.getCapacity();}@Overridepublic int getSize() {return array.getSize();}@Overridepublic boolean isEmpty() {return array.isEmpty();}@Overridepublic void push(E e) {array.addLast(e);}@Overridepublic E pop() {return array.removeLast();}@Overridepublic E peek() {return array.getLast();}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append("Stack").append("[");for (int i = 0; i < array.getSize(); i++) {res.append(array.get(i));if (i != array.getSize() - 1) {res.append(",");}}res.append("] Top");return res.toString();}
}

寫一個(gè)測(cè)試方法：

執(zhí)行結(jié)果如下：

?2、隊(duì)列

2.1、實(shí)現(xiàn)隊(duì)列

隊(duì)列也是一種線性結(jié)構(gòu)，相比數(shù)組，隊(duì)列對(duì)應(yīng)的操作也是數(shù)組的子集，隊(duì)列只能從一端（隊(duì)尾）添加元素，只能從另一端（隊(duì)首）取出元素。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)（先到先得），即：First In First Out（FIFO）。

由于隊(duì)列對(duì)應(yīng)的操作同樣是數(shù)組的子集，那么我們讓然也是基于上一篇中實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組來快速的實(shí)現(xiàn)一個(gè)棧。?

定義一個(gè)接口，定義相關(guān)功能方法：

然后讓隊(duì)列來實(shí)現(xiàn)接口中的具體功能：

import arr.Array;public class ArrayQueue<E> implements Queue<E> {private Array<E> array;public ArrayQueue(int capacity) {array = new Array<>(capacity);}public ArrayQueue(){array = new Array<>();}public int getCapacity(){return array.getCapacity();}@Overridepublic int getSize() {return array.getSize();}@Overridepublic boolean isEmpty() {return array.isEmpty();}@Overridepublic void enqueue(E e) {array.addLast(e);}@Overridepublic E dequeue() {return array.removeFirst();}@Overridepublic E getFront() {return array.getFirst();}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append("Queue:").append("Front [");for (int i = 0; i < array.getSize(); i++) {res.append(array.get(i));if (i != array.getSize() - 1) {res.append(",");}}res.append("] tail");return res.toString();}
}

同樣的寫一個(gè)測(cè)試類：

?

執(zhí)行結(jié)果如下：

2.2、循環(huán)隊(duì)列

初始時(shí)front和tail都是指向下標(biāo)為0的位置，當(dāng)有元素入隊(duì)時(shí)，tail指向該元素的下一個(gè)位置（(tail+1)%capacity），元素出隊(duì)時(shí)，front向后移動(dòng)一個(gè)位置，因此，循環(huán)隊(duì)列有元素出隊(duì)時(shí)，無需讓所有的元素都移動(dòng)一個(gè)位置，只需讓front的指向移動(dòng)一次即可，示意圖如下：

?????????

下面我們來通過代碼看一下循環(huán)隊(duì)列該怎么實(shí)現(xiàn)：

public class LoopQueue<E> implements Queue<E> {private E[] data;private int front, tail;private int size;public LoopQueue(int capacity) {data = (E[]) new Object[capacity + 1];front = 0;tail = 0;size = 0;}public LoopQueue() {this(10);}public int getCapacity() {return data.length - 1;}@Overridepublic int getSize() {return size;}@Overridepublic boolean isEmpty() {return front == tail;}@Overridepublic void enqueue(E e) {if ((tail + 1) % data.length == front) {resize(getCapacity() * 2);}data[tail] = e;tail = (tail + 1) % data.length;size++;}private void resize(int newCapacity) {E[] newdata = (E[]) new Object[newCapacity + 1];for (int i = 0; i < size; i++) {newdata[i] = data[(i + front) % data.length];}data = newdata;front = 0;tail = size;}@Overridepublic E dequeue() {if (isEmpty()) {throw new IllegalArgumentException("隊(duì)列為空");}E ret = data[front];data[front] = null;front = (front + 1) % data.length;size--;if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {resize(getCapacity() / 2);}return null;}@Overridepublic E getFront() {if (isEmpty()) {throw new IllegalArgumentException("隊(duì)列為空");}return data[front];}@Overridepublic String toString() {StringBuilder res = new StringBuilder();res.append(String.format("Queue: size=%d,capacity=%d\n", size, getCapacity())).append("front [");for (int i = front; i != tail; i = (i + 1) % data.length) {res.append(data[i]);if ((i+1)%data.length != tail) {res.append(",");}}res.append("] tail");return res.toString();}
}

同樣的測(cè)試程序：

執(zhí)行結(jié)果如下：

好了，關(guān)于棧和隊(duì)列的內(nèi)容就說這么多吧，咱們下期再會(huì)！

祝：工作順利！