目錄???????

前言

1、棧

?2、隊列

2.1、實現(xiàn)隊列

2.2、循環(huán)隊列

---

前言

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

1、棧

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

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

首先定義一個接口，定義相關功能方法：

然后讓棧來實現(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();}
}

寫一個測試方法：

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

?2、隊列

2.1、實現(xiàn)隊列

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

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

定義一個接口，定義相關功能方法：

然后讓隊列來實現(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();}
}

同樣的寫一個測試類：

?

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

2.2、循環(huán)隊列

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

?????????

下面我們來通過代碼看一下循環(huán)隊列該怎么實現(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("隊列為空");}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("隊列為空");}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();}
}

同樣的測試程序：

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

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

祝：工作順利！