棧和隊列相關的一些問題
棧和隊列相關的一些問題
作者：Grey
原文地址：
最小棧
題目鏈接見：LeetCode 155. Min Stack
主要思路
準備兩個棧，一個棧叫 stack, 用於記錄原始數據信息； 一個棧叫 min，用來存此時原始棧中的最小值，和 stack 同步增長，只不過 min 棧在每次 push 的時候，要用當前值和 min 棧頂部元素比較一下，如果 min 頂部元素較小，則 min 棧不 push 原始數，而是再次 push 一次 min 頂部的元素，這樣每次 min 頂部的元素，就是原始棧中最小的那個值；
此外，彈出的時候，min 棧跟隨 stack 棧同步彈出元素即可。
完整代碼如下
class MinStack {
Stack<Integer> stack;
Stack<Integer> min;
public MinStack() {
stack = new Stack<>();
min = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (min.isEmpty()) {
min.push(val);
} else {
min.push(Math.min(min.peek(),val));
}
}
public void pop() {
stack.pop();
min.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
用雙鏈表實現棧和隊列
主要思路：使用雙向鏈表實現一個雙端隊列，然後用雙端隊列去實現棧和隊列。
雙向鏈表的數據結構定義為
private final static class Node<T> {
public T data;
// 下一個節點
public Node<T> next;
// 上一個節點
public Node<T> last;
public Node(T data) {
this.data = data;
}
}
雙端隊列（可以從頭部進，頭部出，也可以從尾部進，尾部出）的數據結構定義如下：
public final static class DoubleEndsQueue<T> {
public Node<T> head;
public Node<T> tail;
public void addFromHead(T value) {
// TODO
// 從頭部進入
}
public void addFromBottom(T value) {
// TODO
// 從尾部進入
}
public T popFromHead() {
// TODO
// 從頭部彈出
}
public T popFromBottom() {
// TODO
// 從尾部彈出
}
public boolean isEmpty() {
return head == null || tail == null;
}
}
如果我們可以實現上述雙端隊列，那麼實現棧和隊列就很簡單了，不贅述，直接上代碼。
使用自定義雙端隊列實現棧結構代碼如下：
public final static class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
if (null == queue || isEmpty()) {
return null;
}
return queue.popFromHead();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
使用自定義雙端隊列實現隊列結構代碼如下：
public final static class MyQueue<T> {
private DoubleEndsQueue<T> queue;
public MyQueue() {
queue = new DoubleEndsQueue<>();
}
public void push(T value) {
if (null == queue) {
return;
}
queue.addFromHead(value);
}
public T poll() {
if (isEmpty()) {
return null;
}
return queue.popFromBottom();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}
雙端隊列的幾個主要方法
void addFromHead(T value): 從頭部進入
主要思路
1.如果鏈表沒初始化，則新建頭節點和尾部節點。
2.如果鏈表已經有元素了，則新建一個元素，並連上頭節點，然後把頭節點上一個節點設置為新建節點。
3.頭節點指向新建節點。
代碼如下
public void addFromHead(T value) {
Node<T> node = new Node<>(value);
if (head == null) {
tail = node;
} else {
node.next = head;
head.last = node;
}
head = node;
}
void addFromBottom(T value): 從尾部進入
主要思路
1.如果鏈表沒初始化，則新建頭節點和尾部節點。
2.如果鏈表已經有元素了，則新建一個元素，尾部節點的下一個節點設置為這個新建節點，這個新建節點的上一個節點指向尾節點。
3.尾節點指向新建節點。
代碼如下
public void addFromBottom(T value) {
Node<T> node = new Node<>(value);
if (tail == null) {
head = node;
} else {
tail.next = node;
node.last = tail;
}
tail = node;
}
T popFromHead(): 從頭部彈出
主要思路：
-
如果是空鏈表，直接返回 null。
-
如果非空，但是只有一個節點，則把頭部和尾部節點都置為空即可。
-
如果不止一個節點，則先找到頭節點的下一個節點，然後把這個節點的上一個節點置為空，然後把頭節點指向其下一個節點。
代碼如下
public T popFromHead() {
if (null == head || tail == null) {
return null;
}
T data = head.data;
if (head == tail) {
head = null;
tail = null;
return data;
}
head = head.next;
head.last = null;
return data;
}
T popFromBottom(): 從尾部彈出
主要思路：
-
如果是空鏈表，直接返回 null。
-
如果非空，但是只有一個節點，則把頭部和尾部節點都置為空即可。
-
如果不止一個節點，則先找到尾節點的上一個節點，然後把這個節點的下一個節點置為空，然後把尾節點指向其上一個節點。
主要代碼
public T popFromBottom() {
if (tail == null || head == null) {
return null;
}
T data = tail.data;
if (tail == head) {
tail = null;
head = null;
return data;
}
tail = tail.last;
tail.next = null;
return data;
}
LeetCode 有同樣的題目，鏈接見：LeetCode 641. Design Circular Deque
註：LeetCode 這題需要多引入兩個變量，一個是 size ，用於標識當前鏈表長度，一個是 capacity, 標識當前隊列可以擴展的最大長度。其餘方法和上述例子一樣處理。
LeetCode 641. Design Circular Deque 這題完整代碼如下
package leetcode.medium;
/**
* 用雙向鏈表實現雙端隊列
*
* @link <a href="//leetcode-cn.com/problems/design-circular-deque/">雙向鏈表實現雙端隊列</a>
* @see snippet.Code_0011_DoubleEndsToStackAndQueue
*/
public class LeetCode_0641_DesignCircularDeque {
class MyCircularDeque {
// 雙向鏈表
static class DoubleNode {
public int val;
public DoubleNode next;
public DoubleNode last;
public DoubleNode(int v) {
val = v;
}
}
// 頭節點
DoubleNode head;
// 尾節點
DoubleNode tail;
// 當前元素數量
int size;
// 容量
int capacity;
public MyCircularDeque(int k) {
capacity = k;
}
// 頭部進
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
if (isEmpty()) {
// 鏈表是空的，先初始化
head = tail = new DoubleNode(value);
} else {
// 新建節點
DoubleNode newHead = new DoubleNode(value);
newHead.next = head;
head.last = newHead;
head = newHead;
}
size++;
return true;
}
// 尾部進
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
if (isEmpty()) {
head = tail = new DoubleNode(value);
} else {
DoubleNode rearNode = new DoubleNode(value);
tail.next = rearNode;
rearNode.last = tail;
tail = rearNode;
}
size++;
return true;
}
// 頭部出
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
if (size == 1) {
head = tail = null;
} else {
// 不止一個元素
DoubleNode newHead = head.next;
newHead.last = null;
head = newHead;
}
size--;
return true;
}
// 尾部出
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
if (size == 1) {
head = tail = null;
} else {
DoubleNode newRear = tail.last;
newRear.next = null;
tail = newRear;
}
size--;
return true;
}
// 獲取頭部元素
public int getFront() {
if (isEmpty()) {
return -1;
} else {
return head.val;
}
}
// 獲取尾部元素
public int getRear() {
if (isEmpty()) {
return -1;
} else {
return tail.val;
}
}
// 判斷鏈表是否為空
public boolean isEmpty() {
return size == 0;
}
// 判斷鏈表是否滿
public boolean isFull() {
return size == capacity;
}
}
}
使用棧來實現隊列
題目描述見：LeetCode 232. Implement Queue using Stacks
主要思路
使用兩個棧，一個是 push 棧，一個是 pop 棧，通過這兩個棧互相導入的方式實現隊列操作，每次入隊列的元素，會直接存到 push 棧中，在隊列彈出數據的時候，從 pop 棧中彈出，不過彈出需要按如下規則來處理
-
先將 push 棧中的內容一次性導入到 pop 棧中，然後 pop 棧彈出的元素，即為隊列要彈出的元素。
-
只有 pop 棧空了才能導數據。
-
pop 棧不為空不用導數據。
完整代碼見
class MyQueue {
private final Stack<Integer> push;
private final Stack<Integer> pop;
public MyQueue() {
push = new Stack<>();
pop = new Stack<>();
}
public void push(int x) {
push.push(x);
}
public int pop() {
while (!push.isEmpty()) {
pop.push(push.pop());
}
int result = pop.pop();
while (!pop.isEmpty()) {
push.push(pop.pop());
}
return result;
}
public int peek() {
while (!push.isEmpty()) {
pop.push(push.pop());
}
int result = pop.peek();
while (!pop.isEmpty()) {
push.push(pop.pop());
}
return result;
}
public boolean empty() {
return push.isEmpty();
}
}
使用隊列來實現棧
使用兩個隊列，一個隊列是 data 隊列，一個隊列是 help 隊列，每次棧要存入數據的時候，其實是存在 data 隊列中，但是棧在彈出數據的時候，要先把 data 隊列裏面的數據先一一存入 help 隊列，然後把最後一個要存入的數據彈出，然後把 data 和 help 兩個隊列互換，在下一輪操作中，繼續以上流程操作即可。
完整代碼見
class MyStack {
private Queue<Integer> data;
private Queue<Integer> help;
public MyStack() {
data = new LinkedList<>();
help = new LinkedList<>();
}
// 從尾部進
public void push(int x) {
data.offer(x);
}
public int pop() {
int result = 0;
while (!data.isEmpty()) {
int x = data.poll();
if (data.isEmpty()) {
result = x;
} else {
help.offer(x);
}
}
Queue<Integer> t = data;
data = help;
help = t;
return result;
}
public int top() {
int result = 0;
while (!data.isEmpty()) {
int x = data.poll();
help.offer(x);
if (data.isEmpty()) {
result = x;
}
}
Queue<Integer> t = data;
data = help;
help = t;
return result;
}
public boolean empty() {
return data.isEmpty();
}
}
數組實現不超過固定大小的循環隊列
題目鏈接見：LeetCode 622. Design Circular Queue
使用數組可以實現，但是需要一些輔助變量，首先需要這兩個變量來判斷隊列是否為空或者已經滿了
// 當前隊列的元素有多少了
private int size;
// 當前隊列可以支持的最大元素個數是多少
private final int limit;
其次，需要定義兩個指針，用於標識當前的出隊列位置和當前的入隊列位置。
// 當前的出隊列位置
private int popIndex;
// 當前的入隊列位置
private int pushIndex;
核心方法是如下兩個
// 入隊列
public boolean enQueue(int value) {
if (isFull()) {
// 滿了無法入隊列
return false;
}
// 元素增加1
size++;
// 入隊列的位置把元素填上
arr[pushIndex] = value;
// 尾指針當前應該是入隊列的位置
rear = pushIndex;
// 下一個入隊列的位置
pushIndex = next(pushIndex);
return true;
}
// 出隊列
public boolean deQueue() {
if (isEmpty()) {
// 空了怎麼入隊
return false;
}
// 元素減少一個
size--;
// 到下一個出隊列的位置即可
// 不需要處理當前出隊列的位置，因為後續這個位置會被新的元素覆蓋
popIndex = next(popIndex);
return true;
}
其中的 next方法就是循環下標的意思
// 循環下標
// 0，1，2，3...N, 0, 1, 2....N, 0, 1,2...
private int next(int pre) {
return pre < limit - 1 ? pre + 1 : 0;
}
完整代碼見
class MyCircularQueue {
private final int[] arr;
// 當前的出隊列位置
private int popIndex;
// 當前的入隊列位置
private int pushIndex;
private int rear;
// 當前隊列的元素有多少了
private int size;
// 當前隊列可以支持的最大元素個數是多少
private final int limit;
public MyCircularQueue(int k) {
limit = k;
arr = new int[limit];
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
size++;
arr[pushIndex] = value;
rear = pushIndex;
pushIndex = next(pushIndex);
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
size--;
popIndex = next(popIndex);
return true;
}
public int Front() {
return isEmpty() ? -1 : arr[popIndex];
}
public int Rear() {
return isEmpty() ? -1 : arr[rear];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
private int next(int pre) {
return pre < limit - 1 ? pre + 1 : 0;
}
}
