---
tags: 提升程式設計師的面試力
---
# Chapter 3 | Stacks and Queues
## 實作堆疊
Stack 是使用 Last In First Out (LIFO) 後進先出原則的數據結構。
有些題目中，使用堆疊儲存資料比陣列更好。
基本的常見運算有：
* isEmpty()：檢查堆疊是否為空？若堆疊內無任何元素即返回 true，反之返回 false
* push(elements)：新增一個或多個元素到堆疊頂部
* pop()：移除堆疊頂部元素，同時返回被移除的元素
* peek() 或 top()：僅返回堆疊元素，不做任何修改
相較於 array，stack 只支援 pop 或 push 這類的方法（只能從尾取資料），而不能直接取出中間的項目，目的是要限制開發者的操作，以避免對該資料結構做了不適當的操作。
pop跟push之時間複雜度皆為常數, 即O(1)
### 實作堆疊的範例程式碼
```java=
package Introduction;
import java.util.EmptyStackException;
public class MyStack<T> {
private static class StackNode<T> {
private T data;
private StackNode<T> next;
public StackNode(T data) {
this.data = data;
}
public T getData() {
return data;
}
}
private StackNode<T> top;
public T pop() {
if (top == null) throw new EmptyStackException();
T item = top.getData();
top = top.next;
return item;
}
public void push(T item) {
StackNode<T> t = new StackNode<T>(item);
t.next = top;
top = t;
}
public T peek() {
if (top == null) throw new EmptyStackException();
return top.data;
}
public boolean isEmpty() {
return top == null;
}
}
```
堆疊常用於遞迴演算法。
有時在遞迴過程中需要將暫時資料推到堆疊上，然後再回頭移除他們。
堆疊也可以用於迭代的實作遞迴演算法。
## 面試題目
### 3.1 一對三:如何以單一陣列實作三個堆疊。
Three in One:
Describe how you could use a single array to implement three stacks.
### SOLUTION
---
### Approach 1: Fixed Division 固定分隔
* For stack 1, we will use [0, n/3).
* For stack 2, we will use [ n/3 , 2n/3 ) .
* For stack 3, we will use [ 2n/3 , n) .
```java=
package Q3_01_Three_in_One;
import java.util.EmptyStackException;
import CtCILibrary.AssortedMethods;
public class FixedMultiStack {
private int numberOfStacks = 3;
private int stackCapacity;
private int[] values;
private int[] sizes;
public FixedMultiStack(int stackSize) {
stackCapacity = stackSize;
values = new int[stackSize * numberOfStacks];
sizes = new int[numberOfStacks];
}
/* Push value onto stack. */
public void push(int stackNum, int value) throws FullStackException {
/* Check that we have space for the next element */
if (isFull(stackNum)) {
throw new FullStackException();
}
/* Increment stack pointer and then update top value. */
sizes[stackNum]++;
values[indexOfTop(stackNum)] = value;
}
/* Pop item from top stack. */
public int pop(int stackNum) {
if (isEmpty(stackNum)) {
throw new EmptyStackException();
}
int topIndex = indexOfTop(stackNum);
int value = values[topIndex]; // Get top
values[topIndex] = 0; // Clear
sizes[stackNum]--; // Shrink
return value;
}
/* Return top element. */
public int peek(int stackNum) {
if (isEmpty(stackNum)) {
throw new EmptyStackException();
}
return values[indexOfTop(stackNum)];
}
/* Return if stack is empty. */
public boolean isEmpty(int stackNum) {
return sizes[stackNum] == 0;
}
/* Return if stack is full. */
public boolean isFull(int stackNum) {
return sizes[stackNum] == stackCapacity;
}
/* Returns index of the top of the stack. */
private int indexOfTop(int stackNum) {
int offset = stackNum * stackCapacity;
int size = sizes[stackNum];
return offset + size - 1;
}
public int[] getValues() {
return values;
}
public int[] getStackValues(int stackNum) {
int[] items = new int[sizes[stackNum]];
for (int i = 0; i < items.length; i++) {
items[i] = values[stackNum * stackCapacity + i];
}
return items;
}
public String stackToString(int stackNum) {
int[] items = getStackValues(stackNum);
return stackNum + ": " + AssortedMethods.arrayToString(items);
}
}
```
### 3.2 堆疊最小值: 如何設計除了push 與 pop 外還具有回傳最小元素的 min 函式的堆疊? push、pop、與 min 都應該以 O(1) 時間操作。
Stack Min:
How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
push(5); // stack is {5}, min is 5
push(6); // stack is {6, 5}, min is 5
push(3); // stack is {3, 6, 5}, min is 3
push(7); // stack is {7, 3, 6, 5}, min is 3
pop(); // pops 7. stack is {3, 6, 5}, min is 3
pop(); // pops 3. stack is {6, 5}. min is 5.
### SOLUTION
---
* minstack 必須判斷「欲新增的資料」是否有比「目前最上面」還要小。
* 如果有就把「欲新增的資料」push()進minstack，此時該資料會位在Stack的「最上面」，可以保證minstack的「最上面」資料就是datastack中的「最小值」。
```java=
package Q3_02_Stack_Min;
import java.util.Stack;
public class StackWithMin extends Stack<NodeWithMin> {
public void push(int value) {
int newMin = Math.min(value, min());
super.push(new NodeWithMin(value, newMin));
}
public int min() {
if (this.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return peek().min;
}
}
}
```
```java=
package Q3_02_Stack_Min;
class NodeWithMin {
public int value;
public int min;
public NodeWithMin(int v, int min){
value = v;
this.min = min;
}
}
```
```java=
package Q3_02_Stack_Min;
import java.util.Stack;
public class StackWithMin2 extends Stack<Integer> {
Stack<Integer> s2;
public StackWithMin2() {
s2 = new Stack<Integer>();
}
public void push(int value){
if (value <= min()) {
s2.push(value);
}
super.push(value);
}
public Integer pop() {
int value = super.pop();
if (value == min()) {
s2.pop();
}
return value;
}
public int min() {
if (s2.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return s2.peek();
}
}
}
```
### 3.3 Stack of Plates:
想像一下，一疊盤子，如果堆得太高，它很可能會倒，因此在現實生活中，如果盤子堆到一定高度，我們就會重新堆新的一疊。
實現一個新的資料結構 SetOfStack 來模擬這樣現象。
SetOfStack 當中包含很多的堆疊，當一個堆疊達到上限的時候，啟用下一個堆疊。
SetOfStack.push 和 SetOfStack.pop 應該和普通堆疊的操作一樣。
### SOLUTION
---
* 每次 push()都必須將元素放到最近使用的一個堆疊中，在這個堆疊已經滿了情況下，那就必須建一個新的堆疊，然後放進堆疊。
* pop()也必須要在最近的一個堆疊上操作，如果最後一個堆疊是空的話，就應該將其移除。
* 可以用Stack of Stacks來解決，當 push 超過 capacity 的時候，追加一個Stack。
* 每次 pop 都從 top Stack 中 pop。
```java=
package Q3_03_Stack_of_Plates;
import java.util.ArrayList;
import java.util.EmptyStackException;
public class SetOfStacks {
ArrayList<Stack> stacks = new ArrayList<Stack>();
public int capacity;
public SetOfStacks(int capacity) {
this.capacity = capacity;
}
public Stack getLastStack() {
if (stacks.size() == 0) {
return null;
}
return stacks.get(stacks.size() - 1);
}
public void push(int v) {
Stack last = getLastStack();
if (last != null && !last.isFull()) { // add to last
last.push(v);
} else { // must create new stack
Stack stack = new Stack(capacity);
stack.push(v);
stacks.add(stack);
}
}
public int pop() {
Stack last = getLastStack();
if (last == null) throw new EmptyStackException();
int v = last.pop();
if (last.size == 0) {
stacks.remove(stacks.size() - 1);
}
return v;
}
public int popAt(int index) {
return leftShift(index, true);
}
public int leftShift(int index, boolean removeTop) {
Stack stack = stacks.get(index);
int removed_item;
if (removeTop) removed_item = stack.pop();
else removed_item = stack.removeBottom();
if (stack.isEmpty()) {
stacks.remove(index);
} else if (stacks.size() > index + 1) {
int v = leftShift(index + 1, false);
stack.push(v);
}
return removed_item;
}
public boolean isEmpty() {
Stack last = getLastStack();
return last == null || last.isEmpty();
}
}
```
#### Follow Up: Implement popAt(int index)
進階： 實現一個函數 popAt(int index)，指定在哪個堆疊上執行 pop 操作。
### SOLUTION
---
* 如果在Stack 1 pop了一個元素，那麼就得把 Stack 2的一個元素移到Stack 1裡去，以此類推把Stack 3、4、5 …的都挪動一下。
```java=
package Q3_03_Stack_of_Plates;
import java.util.ArrayList;
import java.util.EmptyStackException;
public class SetOfStacks {
ArrayList<Stack> stacks = new ArrayList<Stack>();
public int capacity;
public SetOfStacks(int capacity) {
this.capacity = capacity;
}
public Stack getLastStack() {
if (stacks.size() == 0) {
return null;
}
return stacks.get(stacks.size() - 1);
}
public void push(int v) {
Stack last = getLastStack();
if (last != null && !last.isFull()) { // add to last
last.push(v);
} else { // must create new stack
Stack stack = new Stack(capacity);
stack.push(v);
stacks.add(stack);
}
}
public int pop() {
Stack last = getLastStack();
if (last == null) throw new EmptyStackException();
int v = last.pop();
if (last.size == 0) {
stacks.remove(stacks.size() - 1);
}
return v;
}
public int popAt(int index) {
return leftShift(index, true);
}
public int leftShift(int index, boolean removeTop) {
Stack stack = stacks.get(index);
int removed_item;
if (removeTop) removed_item = stack.pop();
else removed_item = stack.removeBottom();
if (stack.isEmpty()) {
stacks.remove(index);
} else if (stacks.size() > index + 1) {
int v = leftShift(index + 1, false);
stack.push(v);
}
return removed_item;
}
public boolean isEmpty() {
Stack last = getLastStack();
return last == null || last.isEmpty();
}
}
```
```java=
package Q3_03_Stack_of_Plates;
import java.util.EmptyStackException;
public class Stack {
private int capacity;
public Node top;
public Node bottom;
public int size = 0;
public Stack(int capacity) {
this.capacity = capacity;
}
public boolean isFull() {
return capacity == size;
}
public void join(Node above, Node below) {
if (below != null) below.above = above;
if (above != null) above.below = below;
}
public boolean push(int v) {
if (size >= capacity) return false;
size++;
Node n = new Node(v);
if (size == 1) bottom = n;
join(n, top);
top = n;
return true;
}
public int pop() {
if (top == null) throw new EmptyStackException();
Node t = top;
top = top.below;
size--;
return t.value;
}
public boolean isEmpty() {
return size == 0;
}
public int removeBottom() {
Node b = bottom;
bottom = bottom.above;
if (bottom != null) bottom.below = null;
size--;
return b.value;
}
}
```
參考資料:
https://www.programiz.com/dsa/stack
https://alrightchiu.github.io/SecondRound/stack-neng-gou-zai-o1qu-de-zui-xiao-zhi-de-minstack.html
Sign in with Wallet
Connect another wallet