棧的理論描述
棧是一個(gè)有序線性表熊经，只能在表的一端（成為棧頂泽艘，top）執(zhí)行插入和刪除操作。最后插入的元素將第一個(gè)被刪除镐依。所以棧也稱為后進(jìn)先出（Last In First Out）或先進(jìn)后出（First In Last Out）線性表匹涮。棧主要有兩個(gè)操作，一個(gè)入棧（push）槐壳，表示在棧中插入一個(gè)元素然低，一個(gè)出棧（pop），表示將棧頂元素刪除务唐。試圖對(duì)空棧執(zhí)行出棧操作稱為UnderFlow雳攘，對(duì)滿棧執(zhí)行入棧操作稱為OverFlow。
棧的抽象數(shù)據(jù)結(jié)構(gòu)
棧的主要操作：
- void push(int data):將data插入棧
- int pop():刪除并返回最后一個(gè)插入棧的元素
棧的輔助操作
- int top():返回最后一個(gè)插入棧的元素
- int size():返回存儲(chǔ)在棧中元素的個(gè)數(shù)
- int isEmpty():判斷棧中是否有元素
- int StackFull():判斷棧中是否存滿元素
異常
pop和top操作在椃愕眩空的時(shí)候是不能操作的吨灭。試圖對(duì)空棧執(zhí)行pop和top會(huì)拋出異常。試圖對(duì)滿棧執(zhí)行push操作也會(huì)拋出異常刑巧。
代碼實(shí)現(xiàn)
棧抽象數(shù)據(jù)結(jié)構(gòu)有多種實(shí)現(xiàn)方式：
- 基于簡(jiǎn)單數(shù)組的實(shí)現(xiàn)方法
- 基于動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)方法
- 基于鏈表的實(shí)現(xiàn)方法
簡(jiǎn)單數(shù)組：
public class DynArrayStack {
private int top;
private int capacity;
private int[] array;
public DynArrayStack(){
capacity = 1;
array = new int[capacity];
top = -1;
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isStackFull() {
return (top == capacity -1);
}
public void push(int data) {
if (isStackFull()) {
System.out.println("Stack overflow!");
}else {
array[++top] = data;
}
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty!");
return 0;
}else {
return array[top--];
}
}
}
動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)方法大致一樣喧兄，只是比上面的多了當(dāng)?shù)竭_(dá)數(shù)組最大容量的時(shí)候?qū)⑷萘繑U(kuò)大到現(xiàn)有的一倍。
private void doubleSize(){
int newArray[] = new int[capacity << 1];
System.arraycopy(array, 0, newArray, 0, capacity);
capacity = capacity << 1;
array = newArray;
}
public void push(int data) {
if (isStackFull()) {
doubleSize();
}else {
array[++top] = data;
}
}
鏈表的棧實(shí)現(xiàn)方式：
public class LLStack {
private LinkedNode headNode;
public LLStack(){}
public void push(int data) {
if (headNode == null) {
headNode = new LinkedNode(data);
}else if (headNode.getData() == null) {
headNode.setData(data);
}else {
LinkedNode node = new LinkedNode(data);
node.setNext(headNode);
headNode = node;
}
}
public int pop(){
if (headNode == null) {
throw new EmptyStackException("Stack Empty");
}
int data = headNode.getData();
headNode = headNode.getNext();
return data;
}
public int top(){
return headNode == null ? null : headNode.getData();
}
public boolean isEmpty(){
return headNode == null || headNode.getData() == null;
}
}
各種實(shí)現(xiàn)方式的比較：
基于數(shù)組實(shí)現(xiàn)的棧：
- 各個(gè)操作都是常數(shù)時(shí)間開銷
- 每隔一段時(shí)間倍增的開銷教大
- n個(gè)操作的任意序列的平攤時(shí)間開銷為O(n)
基于鏈表實(shí)現(xiàn)的棧：
- 棧規(guī)模增加減少都很簡(jiǎn)潔
- 各個(gè)操作都是常數(shù)時(shí)間開銷
- 每個(gè)操作都要使用額外的時(shí)間和空間開銷來處理指針
應(yīng)用
- IDE和編譯器中符號(hào)匹配
- 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
- 實(shí)現(xiàn)函數(shù)調(diào)用（包括遞歸）
棧的相關(guān)問題
eg：計(jì)算跨度：給定數(shù)組A啊楚，A[i]的跨度S[i]定義為：滿足A[j]<=
A[j+1]而且在A[i]前的連續(xù)元素A[j]的最大個(gè)數(shù)吠冤。如圖
/* time:O(n), space:(n) */
public int[] findingSpans(int[] inputArray) {
int[] spans = new int[inputArray.length];
Stack<Integer> stack = new Stack();
int p;
for (int i = 0; i < inputArray.length; i++) {
while (!stack.isEmpty() && inputArray[i] > inputArray[stack.pop()]) {
stack.pop();
}
if (stack.isEmpty()) {
p = -1;
}else {
p = stack.top();
}
spans[i] = i - p;
stack.push(i);
}
return spans;
}
eg:設(shè)計(jì)一個(gè)可以把棧中元素按照升序排列的排序算法，并且不能限定棧的實(shí)現(xiàn)方法恭理。
/* time:O(n^2) , space:O(n) */
public Stack<Integer> sort(Stack<Integer> s) {
Stack<Integer> r = new Stack<>();
while (!s.isEmpty()) {
int temp = s.pop();
while (!r.isEmpty() && r.peek() > temp) {
s.push(r.pop());
}
r.push(temp);
}
return r;
}
eg：刪除所有相鄰的重復(fù)元素：給定一個(gè)數(shù)字?jǐn)?shù)組拯辙，刪除相鄰的重復(fù)數(shù)字，結(jié)果數(shù)組中不能有任何相鄰的重復(fù)數(shù)字蚯斯。
| input | 1, 5, 6, 8, 8, 0, 1, 1, 0, 6, 5 |
|---|---|
| optput | 1 |
/* space:O(n) , time:O(n) */
public int removeAdjacentDuplicates(int[] a){
int stkptr = -1;
int i = 0;
while (i < a.length) {
if (stkptr == -1 || a[stkptr] != a[i]) {
stkptr++;
a[stkptr] = a[i];
}else {
while (i < a.length && a[stkptr] == a[i]) {
i++;
}
stkptr--;
}
}
return stkptr;
}
隊(duì)列的理論描述
定義：隊(duì)列是一種只能在一端插入（隊(duì)尾）薄风，在另一端（隊(duì)首）的有序線性表饵较。隊(duì)列中第一個(gè)插入就是第一個(gè)被刪除的元素拍嵌。所以隊(duì)列是一種先進(jìn)先出（FIFO,first in first out）或者后進(jìn)后出（LILO,last in last out）線性表。
隊(duì)列的抽象數(shù)據(jù)結(jié)構(gòu)
隊(duì)列的主要操作：
- void enQueue(int data):將data插入隊(duì)列
- int deQueue():刪除并返回隊(duì)首的元素
棧的輔助操作
- int front():返回隊(duì)首元素
- int size():返回存儲(chǔ)在隊(duì)列中元素的個(gè)數(shù)
- int isEmpty():判斷隊(duì)列中是否存儲(chǔ)了元素
異常
- 隊(duì)空時(shí)異常（執(zhí)行deQueue操作）
- 隊(duì)滿時(shí)異常（執(zhí)行enQueue操作）
代碼實(shí)現(xiàn)
基于循環(huán)數(shù)組
為什么需要循環(huán)數(shù)組循诉？由隊(duì)列定義横辆，在一端插入，一端刪除茄猫。 當(dāng)執(zhí)行多次插入和刪除操作后狈蚤，就可以容易地發(fā)現(xiàn)數(shù)組靠前位置的空間被浪費(fèi)了，所以基于簡(jiǎn)單數(shù)組實(shí)現(xiàn)隊(duì)列不是一個(gè)靠譜的方法划纽。循環(huán)數(shù)組剛好可以用來解決這個(gè)問題
public class DynArrayQueue {
private int front;
private int rear;
private int capacity;
private int[] array;
public DynArrayQueue(){
capacity = 1;
front = rear = -1;
array = new int[capacity];
}
public boolean isEmpty() {
return front == -1;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
public int getSize() {
if (front == -1) {
return 0;
}
int size = (capacity + rear + 1 - front);
if (size == 0) {
return capacity;
}else {
return size;
}
}
public void resizeQueue() {
int initCapacity = capacity;
capacity *= 2;
int[] old = array;
array = new intp[capacity];
for (int i = 0; i < old.length; i++) {
array[i] = old[i];
}
if (front > rear) {
for (int i = 0; i < front; i++) {
array[i + capacity] = array[i];
array[i] = null;
}
rear += initCapacity;
}
}
public void enQueue(int data) {
if (isFull()) {
resizeQueue();
}
rear = (rear + 1) % capacity;
array[rear] = data;
if (front == -1) {
front = rear;
}
}
public int deQueue(){
int data = null;
if (isEmpty()) {
throw new EmptyQueueException("Queue is empty");
}else {
data = array[front];
if (front == rear) {
front = rear = -1;
}else {
front = (front + 1) % capacity;
}
}
return data;
}
}
基于動(dòng)態(tài)循環(huán)數(shù)組
基于上面的理解脆侮，循環(huán)數(shù)組其實(shí)還是有個(gè)問題，就是當(dāng)分配給數(shù)組的個(gè)數(shù)到達(dá)最大值的時(shí)候勇劣，再插入元素就會(huì)溢出靖避，所以有了動(dòng)態(tài)循環(huán)數(shù)組潭枣。
public class DynArrayQueue {
private int front;
private int rear;
private int capacity;
private int[] array;
public DynArrayQueue(){
capacity = 1;
front = rear = -1;
array = new int[capacity];
}
public boolean isEmpty() {
return front == -1;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
public int getSize() {
return ((capacity - front + rear + 1)%capacity);
}
public void enQueue(int data) {
if (isFull()) {
throw new QueueOverFlowException("queue overflow");
}
rear = (rear + 1) % capacity;
array[rear] = data;
if (front == -1) {
front = rear;
}
}
public int deQueue(){
int data = null;
if (isEmpty()) {
throw new EmptyQueueException("Queue is empty");
}else {
data = array[front];
if (front == rear) {
front = rear = -1;
}else {
front = (front + 1) % capacity;
}
}
return data;
}
}
基于鏈表
public class LLQueue {
private LinkedListNode<Integer> frontNode;
private LinkedListNode<Integer> rearNode;
public boolean isEmpty() {
return frontNode == null;
}
public void enQueue(int data){
LinkedListNode newNode = new LinkedListNode(data);
if (rearNode != null) {
rearNode.setNext(newNode);
}else {
frontNode = rearNode = newNode;
}
}
public int deQueue() {
int data;
if (isEmpty()) {
throw new EmptyQueueEmptyException("Queue Empty");
}
data = frontNode.getData();
frontNode = frontNode.getNext();
return data;
}
}
鏈表和數(shù)組的對(duì)比和棧是一樣的區(qū)別：鏈表需要花費(fèi)指針這些額外的空間，但是操作和思路都很簡(jiǎn)便幻捏。
應(yīng)用
- 操作系統(tǒng)根據(jù)任務(wù)到達(dá)的順序調(diào)度任務(wù)（如打印隊(duì)列）
- 模擬現(xiàn)實(shí)世界中的隊(duì)列
- 多道程序設(shè)計(jì)
- 異步數(shù)據(jù)傳輸
隊(duì)列的相關(guān)問題
eg：如果需要反向輸出隊(duì)列中元素盆犁，應(yīng)該用什么數(shù)據(jù)結(jié)構(gòu)？
答：
public Queue<Integer> reverseQueue(Queue<Integer> queue){
Stack stack = new Stack<Integer>();
while(!queue.isEmpty(){
stack.push(queue.deQueue());
}
while(!stack.isEmpty()){
queue.enQueue(stack.poll());
}
return queue;
}
eg：用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)接口篡九。
解答：
public class StackWithTwoQueues {
LLQueue queue1;
LLQueue queue2;
public StackWithTwoQueues(){
queue1 = new LLQueue();
queue2 = new LLQueue();
}
public void push(int data) {
if (queue1.isEmpty()) {
queue2.enQueue(data);
}else {
queue1.enQueue(data);
}
}
public int pop(){
int i, size, value;
i = 0;
if (queue1.isEmpty()) {
size = queue2.getSize();
while (i < size -1) {
queue1.enQueue(queue2.deQueue());
i++;
}
value = queue2.deQueue();
}else {
size = queue1.getSize();
while (i < size -1) {
queue2.enQueue(queue1.deQueue());
i++;
}
value = queue1.deQueue();
}
return 0;
}
}
eg：給定一個(gè)整數(shù)棧谐岁，如何檢查棧中每隊(duì)相鄰數(shù)字是否是連續(xù)的。每對(duì)數(shù)字的值可以是遞增或遞減的榛臼。如果棧中元素的個(gè)數(shù)是奇數(shù)伊佃，那么組隊(duì)時(shí)忽略棧頂元素。例如沛善，假設(shè)棧中元素為[4,5,-2,-3,11,10,5,6,20]锭魔，那算法應(yīng)該輸出真，因?yàn)槊繉?duì)二元組(4,5),(-2,-3),(11,10)和(5,6)都是連續(xù)數(shù)字路呜。
解答：
public boolean checkStackPairwiseOrder(Stack<Integer> s) {
boolean pairwiseOrder = true;
LLQueue queue = new LLQueue();
while (!s.isEmpty()) {
queue.enQueue(s.pop());
}
while (!queue.isEmpty()) {
s.push(queue.enQueue());
}
while (!s.isEmpty()) {
int n = s.pop();
if (!s.isEmpty()) {
int m = s.pop();
queue.add(m);
if (Math.abs(n - m) != 1) {
pairwiseOrder = false;
break;
}
}
}
return pairwiseOrder;
}
eg：給定一個(gè)整數(shù)k和一個(gè)整數(shù)隊(duì)列迷捧，如何把隊(duì)列中前k個(gè)元素逆置，其余的元素保持不變胀葱？例如漠秋，如果k等于4，隊(duì)列中元素序列為[10,20,30,40,50,60,70,80,90]抵屿，那么應(yīng)該輸出[40,30,20,10,50,60,70,80,90]庆锦。
解答:
public void reverseQueueFirstKElements(int k, Queue<Integer> q) {
if (q == null || k > q.getSize()) {
throw new IllegalArgumentException();
}
if (k > 0) {
Stack<Integer> stack = new Stack<Integer>();
for(int i=0;i<k;i++){
stack.push(q.remove());
}
while(!stack.isEmpty()){
q.add(stack.pop());
}
for (int i = 0; i < q.size() - k; i++) {
q.add(q.remove());
}
}
}
