堆疊（Stack）
堆疊是一種特殊的線性表，只能在一端進行操作
往堆疊中添加元素的操作，一般叫做push，入堆疊
從堆疊中移除元素的操作，一般叫做pop，出堆疊（只能移除堆疊頂元素，也叫做彈出堆疊頂元素）
后進先出的原則，Last In First Out，LIFO
這里說的堆疊和記憶體中的堆疊空間是兩個不同的概念
堆疊的介面設計
下面我們就來自己設計一個堆疊的介面
堆疊的結構我們可以使用之前學過的動態陣列和鏈表來進一步實作
首先，我們需要確定對外的介面有哪些？
完整的設計代碼如下
import com.company.list.ArrayList;
import com.company.list.List;
public class Stack<E> {
private List<E> list = new ArrayList<>();
public void clear() {
list.clear();
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void push(E element) {
list.add(element);
}
public E pop() {
return list.remove(list.size() - 1);
}
public E top() {
return list.get(list.size() - 1);
}
}
設計點的詳細講解：
1.我們可以將動態陣列或者鏈表作為成員變數來在內部呼叫
對應要引入其相關父類已經宣告介面，這里就不再重復粘貼代碼了
public class Stack<E> {
private List<E> list = new ArrayList<>();
// private List<E> list = new LinkedList<>();
....
}
2.push操作就是在list最后添加元素，所以選擇動態陣列或者鏈表的復雜度都是一樣的
public void push(E element) {
list.add(element);
}
3.pop操作就是移除list最后的元素
public E pop() {
return list.remove(list.size() - 1);
}
4.top操作就是獲取堆疊頂的元素，也就是獲取list最后的元素
public E top() {
return list.get(list.size() - 1);
}
堆疊的應用場景
瀏覽器的前進和后退
軟體的撤銷和恢復功能
練習題
1.給定一段字串，判斷有效的括號
題目概述
題目鏈接：
https://leetcode-cn.com/problems/valid-parentheses/
題解：
第一種方式
可以回圈遍歷字串，只有有成對的符號就置為空字符，回圈結束后查看字串是否為空，如果不為空證明有無效的字串
這種方式最簡單，但是效率很低，回圈遍歷不說，還會一直創建新的字串來分配，不建議
public class Solution {
public boolean isValid(String s) {
while (s.contains("{}")
|| s.contains("[]")
|| s.contains("()")) {
s = s.replace("{}", "");
s = s.replace("()", "");
s = s.replace("[]", "");
}
return s.isEmpty();
}
}
第二種方式
1.利用堆疊的特性，將左字符壓入堆疊
2.然后遇到右字符，如果堆疊是空的，說明括號無效；如果堆疊不為空，則讓左字符出堆疊進行對比
如果左右字符不匹配，說明括號無效；如果匹配繼續回圈下一個字符
3.所有字符遍歷完畢后，如果堆疊為空，說明括號有效；如果堆疊不為空，說明括號無效
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int len = s.length();
for (int i = 0; i < len; i++) {
char c = s.charAt(i); // 獲取某一個位置的字符
if (c == '(' || c == '{' || c == '[') { // 左括號
stack.push(c);
} else { // 右括號
if (stack.isEmpty()) return false;
char left = stack.pop();
if (left == '(' && c != ')') return false;
if (left == '{' && c != '}') return false;
if (left == '[' && c != ']') return false;
}
}
return stack.isEmpty();
}
}
第三種方式
在第二種方式的基礎上，利用HashMap提前先將括號以key-value的形式存盤，然后遍歷時都從HashMap中取出value來做對比
public class Solution {
private static HashMap<Character, Character> map = new HashMap<>();
static {
// key - value
map.put('(', ')');
map.put('{', '}');
map.put('[', ']');
}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int len = s.length();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (map.containsKey(c)) { // 左括號
stack.push(c);
} else { // 右括號
if (stack.isEmpty()) return false;
if (c != map.get(stack.pop())) return false;
}
}
return stack.isEmpty();
}
}
佇列（Queue）
單端佇列
佇列是一種特殊的線性表，只能在頭尾兩端進行操作
隊尾（rear）：只能從隊尾添加元素，一般叫做enQueue，入隊
隊頭（front）：只能從隊頭移除元素，一般叫做deQueue，出隊
先進先出原則，Frist In Frist Out，FIFO
佇列的介面設計
下面我們就來自己設計一個佇列的介面
佇列的結構我們也可以使用之前學的動態陣列和鏈表來進一步實作
首先，我們需要確定對外的介面有哪些？
完整的設計代碼如下
import com.company.list.LinkedList;
import com.company.list.List;
public class Queue<E> {
private List<E> list = new LinkedList<>();
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void clear() {
list.clear();
}
// 入隊
public void enQueue(E element) {
list.add(element);
}
// 出隊
public E deQueue() {
return list.remove(0);
}
// 獲取隊頭元素
public E front() {
return list.get(0);
}
}
設計點的詳細講解：
1.佇列主要是往頭尾操作元素，所以優先使用雙向鏈表
public class Queue<E> {
private List<E> list = new LinkedList<>();
....
}
2.入隊操作，就是在鏈表尾節點增加元素
public void enQueue(E element) {
list.add(element);
}
3.出隊操作，就是洗掉鏈表首節點的元素
public E deQueue() {
return list.remove(0);
}
4.獲取隊頭元素就是獲取鏈表首節點的元素
public E front() {
return list.get(0);
}
雙端佇列（Deque）
雙端佇列是能在頭尾兩端添加、洗掉的佇列
英文deque是double ended queue的意思
雙端佇列的介面設計
下面我們就來自己設計一個雙端佇列的介面
雙端佇列的結構也是在鏈表的基礎上來實作的
對外的介面有以下這些
完整的設計代碼如下
import com.company.list.LinkedList;
import com.company.list.List;
public class Deque<E> {
private List<E> list = new LinkedList<>();
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public void clear() {
list.clear();
}
// 從隊尾入隊
public void enQueueRear(E element) {
list.add(element);
}
// 從隊頭出隊
public E deQueueFront() {
return list.remove(0);
}
// 從隊頭入隊
public void enQueueFront(E element) {
list.add(0, element);
}
// 從隊尾出隊
public E deQueueRear() {
return list.remove(list.size() - 1);
}
// 獲取佇列的頭元素
public E front() {
return list.get(0);
}
// 獲取佇列的尾元素
public E rear() {
return list.get(list.size() - 1);
}
}
設計點的詳細講解：
其實同佇列相似，更多注意的是對于鏈表頭尾節點入隊出隊時的操作
回圈佇列（Circle Queue）
其實佇列底層也可以使用動態陣列實作，并且各項介面也可以優化到0(1)的時間復雜度
這個用陣列實作并且優化之后的佇列也叫做回圈佇列
回圈佇列的介面設計
下面我們就來自己設計一個回圈佇列的介面
完整的設計代碼如下
@SuppressWarnings("unchecked")
public class CircleQueue<E> {
private int front; // 用來記錄隊頭在哪里
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10; // 默認容量
public CircleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
front = 0;
size = 0;
}
// 入隊
public void enQueue(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
// 出隊
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
public E front() {
return elements[front];
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capcacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
// 索引映射
private int index(int index) {
index += front;
return index - (index >= elements.length ? elements.length : 0);
}
/**
* 保證要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
}
設計點的詳細講解：
1.增加一個成員變數front來記錄隊頭的位置
public class CircleQueue<E> {
private int front;
....
}
2.封裝索引映射函式，傳進來的對外索引值會轉換成陣列的真實索引
索引映射的原因：
-
入隊操作是在隊尾增加元素，而在陣列中對外的索引可能是處于陣列的最后一個位置，那么增加元素就需要往陣列頭部插入，所以要做好對外索引和真實索引的轉換
-
反之出隊操作的索引位置也可能是在陣列的起始位置，那么洗掉元素的位置就是
front的上一個元素位置，也就是陣列的最后的位置
一開始采用的計算公式如下：
private int index(int index) {
return (index + front) % elements.length
}
由于乘*、除/、模%、浮點數運算，CPU都會執行更多操作來實作運算，所以效率會低
對于模運算也有一些規律可循：
已知n >= 0, m > 0
n % m 等價于 n - (m > n ? 0 : m)
能實作規律的前提是 n < 2m
然后我們將映射函式做了優化：
而且index + front所得的值永遠都是小于elements.length的2倍的，那么模運算的規律就可以使用
private int index(int index) {
index += front;
return index - (index >= elements.length ? elements.length : 0);
}
3.入隊操作時先判斷是否需要擴容，如果需要擴容，就建一個新的陣列，然后將元素按照真實的索引對應添加到新陣列中，這時陣列的對外索引和真實索引是一致的
擴容操作時，記錄隊頭的front欄位要重置為0
入隊操作就是通過對外索引找到真實索引在陣列中添加元素，front指向新的隊頭元素
public void enQueue(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
4.出隊操作就是通過front找到陣列的真實索引位置，置空元素
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
5.清空佇列時，需要遍歷所有陣列元素，然后找到其真實索引的元素置空
front也要歸零
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
front = 0;
size = 0;
}
回圈雙端佇列（Circle Deque）
回圈雙端佇列是可以進行兩端添加、洗掉操作的回圈佇列
回圈雙端佇列的介面設計
下面我們就來自己設計一個回圈雙端佇列的介面
回圈雙端佇列是在回圈佇列的基礎上增加了從頭部入隊和從尾部出隊兩個函式
@SuppressWarnings("unchecked")
public class CircleDeque<E> {
private int front; // 用來記錄隊頭在哪里
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
front = 0;
size = 0;
}
/**
* 從尾部入隊
* @param element
*/
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 從頭部出隊
* @param element
*/
public E deQueueFront() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
/**
* 從頭部入隊
* @param element
*/
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
/**
* 從尾部出隊
* @param element
*/
public E deQueueRear() {
int rearIndex = index(size - 1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
public E front() {
return elements[front];
}
public E rear() {
return elements[index(size - 1)];
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capcacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
private int index(int index) {
index += front;
if (index < 0) { // 如果計算小于0，說明真實的首元素索引也是0，需要往陣列最后一位插入
return index + elements.length;
}
return index - (index >= elements.length ? elements.length : 0);
}
/**
* 保證要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
}
設計點的詳細講解：
1.從頭部入隊操作，也要先考慮是否需要擴容
插入元素的位置也就是隊頭的上一個，所以找到真實的索引位置添加元素，并且更新front的值
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
2.從尾部出隊操作，通過索引映射找到其真實的索引位置，然后將該元素置空
public E deQueueRear() {
int rearIndex = index(size - 1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
練習題
1.用堆疊實作佇列
題目概述
題目鏈接：
https://leetcode-cn.com/problems/implement-queue-using-stacks/
題解：
1.準備兩個堆疊：inStack、outStack
2.入隊時，push到inStack中
3.出隊時，如果outStack為空，將inStack的元素全部逐一出堆疊，push到outStack，outStack
彈出堆疊頂元素
如果outStack不為空，彈出堆疊頂元素
import java.util.Stack;
public class MyQueue {
private Stack<Integer> inStack;
private Stack<Integer> outStack;
/** Initialize your data structure here. */
public MyQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
/** 入隊 */
public void push(int x) {
inStack.push(x);
}
/** 出隊 */
public int pop() {
checkOutStack();
return outStack.pop();
}
/** 獲取隊頭元素 */
public int peek() {
checkOutStack();
// 獲取隊頭的順序是從outStack中取出的
return outStack.peek();
}
/** 是否為空 */
public boolean empty() {
// 兩個堆疊里都沒有元素了才能叫空
return inStack.isEmpty() && outStack.isEmpty();
}
private void checkOutStack() {
// 如果outStack為空，就把inStack的元素都壓入堆疊
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272765.html
標籤：其他
上一篇：資料結構與演算法（五）堆疊、佇列