棧（stack）是限定僅在表尾進行插入和刪除操作的線性表耙考。
隊列（queue）是一種先進先出（First In First Out）的線性表定欧。
一猴伶、棧
1.棧的定義
棧頂：允許插入和刪除的一端為棧頂
棧底：另一端
棧是一種后進先出（Last In First Out）的線性表膜蛔，簡稱 LIFO 結(jié)構(gòu)霉咨。既然棧是一種只允許在尾端進行刪除操作的線性表，那么線性表的特性它全部都有拇派。根據(jù)存儲結(jié)構(gòu)的不同荷辕，棧可以分成：順序棧和鏈棧件豌。
2.順序棧
順序棧其實就是一個數(shù)組疮方，只不過需要在聲明的時候就確定長度。當頭指針 top 指向 -1 的時候茧彤，表示空棧骡显。一般將頭指針 top 指向尾端的元素。
進棧：需要注意棧是否已經(jīng)滿了（
top == MAX_SIZE - 1）,如果不滿曾掂，則壓入棧惫谤，同時 top 指針加一。出棧：需要注意棧是否為空棧（
top == - 1）,如果不空珠洗，則出棧溜歪，同時 top 指針減一。
時間復(fù)雜度均為 O(1)险污。
3.鏈棧
棧的鏈式存儲結(jié)構(gòu)痹愚，其實就是單鏈表，只不過它的頭指針不再指向頭結(jié)點蛔糯，而是指向最尾的節(jié)點（棧頂元素）拯腮。
進棧：將新節(jié)點的 next 指針指向 top，然后將 top 指針指向當前的新節(jié)點蚁飒，鏈表數(shù)量加一动壤。
出棧：保存尾節(jié)點，將 top 指針指向 top.next淮逻，釋放剛剛的尾節(jié)點琼懊，鏈表數(shù)量減一。
時間復(fù)雜度均為 O(1)爬早。
4.用途
Java 對棧（Stack）進行了封裝哼丈，可以直接使用，棧一般用作函數(shù)調(diào)用椛秆希或者 Activity 棧醉旦。
對于函數(shù)調(diào)用棧，在前行階段，對于每一層遞歸车胡，函數(shù)的局部變量檬输、參數(shù)值以及返回地址都被壓入棧中。在退回階段匈棘，位于棧頂?shù)木植孔兞可ゴ取?shù)值和返回地址被彈出，用于返回調(diào)用層次中執(zhí)行代碼的其余部分主卫，也就是恢復(fù)了調(diào)用的狀態(tài)逃默。
5.棧的面試題
-
劍指 Offer 面試題 21：定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min() 函數(shù)队秩。在該棧中笑旺，調(diào)用min()，push() 及 pop() 的時間復(fù)雜度都是 O(1)馍资。
思路：建立一個數(shù)據(jù)棧和輔助棧，輔助棧的棧頂每次壓入數(shù)據(jù)棧棧頂和輔助棧棧頂兩個元素中的最小值关噪，這樣當彈出一個數(shù)據(jù)棧的時候鸟蟹，對應(yīng)彈出一個輔助棧，因為兩者已經(jīng)關(guān)聯(lián)過大小了使兔，所以當下一次獲取最小值的時候必然跟上次已經(jīng)彈出的元素無關(guān)建钥。如果想要獲取最小的元素，直接彈出輔助棧的棧頂即可虐沥。
show my code
public class MinStack {
//數(shù)據(jù)棧
private Stack<Integer> data = new Stack<>();
//輔助棧
private Stack<Integer> min = new Stack<>();
/**
* 壓棧
* @param i
*/
public void add(Integer item) {
//數(shù)據(jù)棧直接入棧
data.push(item);
//輔助棧需要判斷熊经，確保入棧的是最小的元素
if(min.isEmpty() || item <= min.peek()) {
min.push(item);
}else {
min.push(min.peek());
}
}
/**
* 出棧
* @return
*/
public Integer pop() {
if(data.isEmpty() || min.isEmpty()) {
return -1;
}
//彈出輔助棧的棧頂
min.pop();
//彈出數(shù)據(jù)棧棧頂
return data.pop();
}
/**
* 獲取棧最小的元素
* @return
*/
public Integer min() {
if(data.isEmpty() || min.isEmpty()) {
return 0;
}
//直接彈出輔助棧的棧頂
return min.peek();
}
/**
* 打印棧
*/
public void printStack() {
System.out.print("棧元素: ");
for(Integer i:data) {
System.out.print(i+" ");
}
System.out.println("");
System.out.println("*************************");
}
}
測試過程及結(jié)果
public static void main(String[] args) {
MinStack stack = new MinStack();
stack.add(10);
stack.add(999);
stack.add(23);
stack.add(654);
stack.printStack();
System.out.println("出棧元素："+stack.pop());
stack.printStack();
System.out.println("Min 元素："+stack.min());
stack.printStack();
}
- 劍指 Offer 面試題 22：題目：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序欲险，請判斷二個序列是否為該棧的彈出順序镐依。假設(shè)壓入棧的所有數(shù)字均不相等。
思路：解決這個問題很直觀的想法就是建立一個輔助棧天试，把輸入的第一個序列中的數(shù)字依次壓入該輔助棧槐壳，并按照第二個序列的順序依次從該棧中彈出數(shù)字。
判斷一個序列是不是棧的彈出序列的規(guī)律：如果下一個彈出的數(shù)字剛好是棧頂數(shù)字喜每，那么直接彈出务唐。如果下一個彈出的數(shù)字不在棧頂，我們把壓棧序列中還沒有入棧的數(shù)字壓入輔助棧带兜，直到把下一個需要彈出的數(shù)字壓入棧頂為止枫笛。如果所有的數(shù)字都壓入棧了仍然沒有找到下一個彈出的數(shù)字，那么該序列不可能是一個彈出序列刚照。
show my code
/**
* 檢測一個棧的出棧順序是否存在
* @param push 數(shù)字的入棧順序
* @param pop 數(shù)字的出棧順序
* @return
*/
public static boolean verifyStackPopOrder(int push[],int pop[]){
//驗證輸入數(shù)據(jù)是否合法刑巧，壓棧和出棧的數(shù)組的長度必須一致
if(push == null || pop == null || push.length == 0 || pop.length == 0
|| push.length != pop.length){
System.out.println("輸入數(shù)據(jù)不合法");
return false;
}
//構(gòu)造輔助棧，作為數(shù)據(jù)棧
Stack<Integer> data = new Stack<>();
//壓棧數(shù)組的壓入位置
int pushIndex = 0;
//出棧數(shù)組的出棧位置
int popIndex = 0;
//遍歷出棧的數(shù)組，假如發(fā)現(xiàn)出棧的數(shù)據(jù)和壓棧的棧頂元素相同海诲，就將壓棧數(shù)據(jù)的棧頂元素彈出繁莹，否則一直壓入，
//直到壓棧元素和出棧的棧頂元素相等特幔，彈出壓棧的棧頂元素咨演，然后處理下一個出棧的棧頂元素
//未處理完出棧的數(shù)組
while(popIndex < pop.length){
//根據(jù)一個出棧的棧頂元素，遍歷入棧的數(shù)組蚯斯，直到找到相等的元素 或者全部已經(jīng)入棧
while(pushIndex < push.length && (data.isEmpty() || data.peek() != pop[popIndex])){
//壓數(shù)據(jù)進去數(shù)據(jù)棧
data.push(push[pushIndex]);
pushIndex ++;
}
//出棧棧頂元素找到和入棧的棧頂元素相同的薄风，數(shù)據(jù)棧棧頂元素出棧，繼續(xù)處理下一個出棧元素
if(data.peek() == pop[popIndex]){
data.pop();
popIndex ++;
//如果出棧順序正確拍嵌，那么所有數(shù)據(jù)棧元素都會被出棧遭赂，數(shù)據(jù)棧最后會變?yōu)榭盏臈? }else {
//全部已經(jīng)壓入棧，但是找不到和出棧棧頂元素相等的
return false;
}
}
//假如能運行到這里說明横辆，已經(jīng)全部壓入棧撇他，而且出棧的元素也已經(jīng)全部彈出，說明順序是正確的,這個肯定是true
return data.isEmpty();
}
測試過程及結(jié)果
public static void main(String[] args){
int[] push = {1, 2, 3, 4, 5};
int[] pop1 = {4, 5, 3, 2, 1};
int[] pop2 = {3, 5, 4, 2, 1};
int[] pop3 = {4, 3, 5, 1, 2};
int[] pop4 = {3, 5, 4, 1, 2};
System.out.println("人工計算為true狈蚤，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop1));
System.out.println("人工計算為true困肩，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop2));
System.out.println("人工計算為false，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop3));
System.out.println("人工計算為false脆侮，程序得出的出棧順序為: " + verifyStackPopOrder(push, pop4));
int[] push5 = {1};
int[] pop5 = {2};
System.out.println("人工計算為false锌畸，程序得出的出棧順序為: " + verifyStackPopOrder(push5, pop5));
int[] push6 = {1};
int[] pop6 = {1};
System.out.println("人工計算為true，程序得出的出棧順序為: " + verifyStackPopOrder(push6, pop6));
System.out.println("人工計算為false靖避，程序得出的出棧順序為: " + verifyStackPopOrder(null, null));
}
二潭枣、隊列
1.隊列的定義
隊頭：允許刪除的一端
隊尾：允許插入的一端
隊列是一種特殊的線性表，所以隊列也是具有順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的幻捏。
2.隊列的順序存儲結(jié)構(gòu)（循環(huán)隊列）
為了解決用數(shù)組來實現(xiàn)隊列的“假溢出”問題盆犁，我們一般將順序存儲結(jié)構(gòu)的隊列頭尾相接，這種把隊列的頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊列粘咖。
int front; // 頭指針
int rear蚣抗； // 尾指針
隊列滿的條件：
(rear+1) % QueueSize == front計算隊列長度公式：
length = （rear - front + QueueSize）% QueueSize
3.隊列的鏈式存儲結(jié)構(gòu)（鏈隊列）
隊列的鏈式結(jié)構(gòu)其實就是鏈表，只是有頭指針和尾指針瓮下。當隊列為空的時候翰铡，頭指針和尾指針都指向頭結(jié)點。
Node front; // 頭指針
Node rear讽坏； // 尾指針
入隊：在鏈表尾端插入一個節(jié)點
出隊：刪除頭結(jié)點的后繼節(jié)點
4.隊列的面試題
- 劍指 Offer 面試題 7：用兩個棧實現(xiàn)一個隊列锭魔。隊列的聲明如下，請實現(xiàn)它的兩個函數(shù)
appendTail()和deleteHead()路呜，分別完成在隊列尾部插入結(jié)點和在隊列頭部刪除結(jié)點的功能迷捧。
private Stack<T> stack1;
private Stack<T> stack2;
思路：我們從一個具體的例子來分析隊列的插入和刪除元素過程织咧，操作兩三次，你就會發(fā)現(xiàn)刪除一個元素的步驟：當 stack2 中不為空的時候漠秋，在
stack2 中的棧頂元素就是最先進入隊列的元素笙蒙，可以彈出。如果 stack2 為空時庆锦，我們把 stack1 的元素逐個彈出然后壓入 stack2 捅位，這樣就能保證
stack2 的棧元素順序就是進入隊列的順序。如果要使 stack1 的元素出棧搂抒，必須要彈完 stack2 的元素艇搀，然后將 stack1 的元素彈出壓入 stack2 ，再彈出 stack2 的元素求晶。入隊的步驟就是將其壓入 stack1 中焰雕。
show my code
public class CQueue {
public static void main(String[] args){
CQueue cQueue = new CQueue();
cQueue.appendTail(111);
cQueue.appendTail(222);
cQueue.appendTail(333);
System.out.println("出隊: " + cQueue.deleteHead());
System.out.println("出隊: " + cQueue.deleteHead());
cQueue.appendTail(444);
cQueue.appendTail(555);
System.out.println("出隊: " + cQueue.deleteHead());
System.out.println("出隊: " + cQueue.deleteHead());
System.out.println("出隊: " + cQueue.deleteHead());
}
//入隊的棧
private Stack<Integer> stack1 = new Stack<>();
// 出隊的棧
private Stack<Integer> stack2 = new Stack<>();
/**
* 入隊
* @param item
*/
public void appendTail(Integer item){
stack1.push(item);
}
/**
* 出隊
* @return
*/
public Integer deleteHead(){
//假如 stack2 為空棧，那么當前的隊列的頭結(jié)點肯定在 stack1 中芳杏，將 stack1 的元素全部彈出矩屁，然后入棧 stack2
if(stack2.isEmpty()){
while(stack1.size() > 0){
Integer i = stack1.peek();
stack1.pop();
stack2.push(i);
}
}
if(stack2.isEmpty()){
System.out.println("隊列為空，刪除失敗");
return -1;
}
Integer head = stack2.peek();
stack2.pop();
return head;
}
}
- 有個類似的題目：用兩個隊列實現(xiàn)棧爵赵。
思路：假設(shè)有兩個隊列Q1和Q2档插，當二者都為空時，入棧操作可以用入隊操作來模擬亚再，可以隨便選一個空隊列，假設(shè)選Q1進行入棧操作晨抡，現(xiàn)在假設(shè)a,b,c依次入棧了（即依次進入隊列Q1）氛悬， 這時如果想模擬出棧操作，則需要將c出棧耘柱，因為在棧頂如捅，這時候可以考慮用空隊列Q2，將a调煎，b依次從Q1中出隊镜遣， 而后進入隊列Q2，將Q1的最后一個元素c出隊即可士袄，此時Q1變?yōu)榱丝贞犃斜兀琎2中有兩個元素，隊頭元素為a娄柳，隊尾元素為b寓辱，接下來如果再執(zhí)行入棧操作，則需要將元素進入到Q1和Q2中的非空隊列赤拒，即進入Q2隊列秫筏，出棧的話诱鞠，就跟前面的一樣，將Q2除最后一個元素外全部出隊这敬，并依次進入隊列Q1航夺，再將Q2的最后一個元素出隊即可。
show my code
public class QueueToStack<T> {
//鏈隊
Queue<T> queueA = new LinkedList<>();
//鏈隊
Queue<T> queueB = new LinkedList<>();
/**
* 入棧
* @param value
*/
public void push(T value) {
if (queueA.size() == 0 && queueB.size() == 0) {//如果兩個隊列都是空的話,則隨便選擇一個隊列執(zhí)行入棧操作
queueA.add(value);
}else if (queueA.size() == 0 && queueB.size() != 0){///如果不是兩個隊列都是為空的話,則選擇非空的隊列入棧
queueB.add(value);
}else if (queueA.size() != 0 && queueB.size() == 0){
queueA.add(value);
}
}
/**
* 出棧
* @return
*/
public T pop() {
if (queueA.size() == 0 && queueB.size() == 0){
return null;
}
T result = null;
//將非空的隊列的元素按順序出隊崔涂，轉(zhuǎn)移到空的隊列阳掐，直到只有一個元素在非空隊列
if (queueA.size() == 0 && queueB.size() != 0){
while (queueB.size() > 0){
result = queueB.poll();
if (queueB.size()!=0){
queueA.add(result);
}
}
}else if (queueA.size() != 0 && queueB.size() == 0){
while (queueA.size() > 0){
result = queueA.poll();
if (queueA.size()!=0){
queueB.add(result);
}
}
}
return result;
}
public static void main(String[] args) {
QueueToStack<Integer> stack=new QueueToStack<>();
int tmp=0;
stack.push(1);
stack.push(2);
stack.push(3);
tmp=stack.pop();
System.out.println(tmp);//3
stack.push(4);
tmp=stack.pop();
System.out.println(tmp);//4
tmp=stack.pop();
System.out.println(tmp);//2
stack.push(5);
stack.push(6);
tmp=stack.pop();
System.out.println(tmp);//6
tmp=stack.pop();
System.out.println(tmp);//5
tmp=stack.pop();
System.out.println(tmp);//1
}
}
三、詩和遠方
好了,最后兩分鐘,念幾句我在初學棧和隊列時寫的人生感悟的小詩,希望也能引起你們的共鳴堪伍。
人生,就像是一個很大的棧演變锚烦。 出生時你赤條條地來到人世,慢慢地長大,漸漸地變老,最終還得赤條條地離開世間。
人生,又仿佛是一天一天小小的棧重現(xiàn)帝雇。 童年父母每天抱你不斷地進出家門,壯年你每天奔波于家與事業(yè)之間,老年你每天獨自路跚于養(yǎng)老院的門里屋前涮俄。
人生,更需要有進棧出棧精神的體現(xiàn)。在哪里跌倒,就應(yīng)該在哪里爬起來尸闸。無論陷入何等困境,只要抬頭就能仰望藍天,就有希望,不斷進取,你就可以讓出頭之日重現(xiàn)彻亲。困難不會永遠存在,強者才能勇往直前。
人生,其實就是一個大大的隊列演變吮廉。無知童年,快樂少年,稚傲青年,成熟中年,安逸晚年苞尝。
人生,又是一個又一個小小的隊列重現(xiàn)。 春夏秋冬輪回年年,早中晚夜循環(huán)天天宦芦。變化的是時間宙址，不變的是你對未來執(zhí)著的信念。
