1.設(shè)計(jì)含min函數(shù)的棧，要求min、push和pop的時間復(fù)雜度都是o(1)。 算法思想：需要設(shè)計(jì)一個輔助棧，用來存儲當(dāng)前棧中元素的最小值。網(wǎng)上有人說存儲當(dāng)前棧中元素的最小值的所在位置，雖然能節(jié)省空間，這其實(shí)是不對的，因?yàn)槲以谡{(diào)用Min函數(shù)的時候，只能得到位置，還要對存儲元素的棧不斷的pop，才能得到最小值——時間復(fù)雜度o(1)。 所以，還是在輔助棧中存儲元素吧。 此外，還要額外注意Push操作，第一個元素不用比較，自動成為最小值入棧。其它元素每次都要和棧頂元素比較，小的那個放到棧頂。
public class NewStack{PRivate Stack dataStack;private Stack mindataStack;public NewStack(){dataStack = new Stack();mindataStack = new Stack();}public void Push(int element){dataStack.Push(element);if (mindataStack.Count == 0)mindataStack.Push(element);else if (element <= (int)mindataStack.Peek())mindataStack.Push(element);else //(element > mindataStack.Peek)mindataStack.Push(mindataStack.Peek());}public int Pop(){if (dataStack.Count == 0)throw new Exception(“The stack is empty”);mindataStack.Pop();return (int)dataStack.Pop();}public int Min(){if (dataStack.Count == 0)throw new Exception(“The stack is empty”);return (int)mindataStack.Peek();}}2.設(shè)計(jì)含min函數(shù)的棧的另解 話說，和青菜臉呆久了，就沾染了上海小市民意識，再加上原本我就很摳門兒，于是對于上一題目，我把一個棧當(dāng)成兩個用，就是說，每次push，先入站當(dāng)前元素，然后入棧當(dāng)前棧中最小元素；pop則每次彈出2個元素。 算法代碼如下所示（這里最小元素位于當(dāng)前元素之上，為了下次比較方便）：
public class NewStack{private Stack stack;public NewStack(){stack = new Stack();}public void Push(int element){if (stack.Count == 0){stack.Push(element);stack.Push(element);}else if (element <= (int)stack.Peek()){stack.Push(element);stack.Push(element);}else //(element > stack.Peek){object min = stack.Peek();stack.Push(element);stack.Push(min);}}public int Pop(){if (stack.Count == 0)throw new Exception(“The stack is empty”);stack.Pop();return (int)stack.Pop();}public int Min(){if (stack.Count == 0)throw new Exception(“The stack is empty”);return (int)stack.Peek();}}之所以說我這個算法比較叩門，是因?yàn)槲抑皇褂昧艘粋€棧，空間復(fù)雜度o(N)，節(jié)省了一半的空間（算法1的空間復(fù)雜度o(2N)）。 3.用兩個棧實(shí)現(xiàn)隊(duì)列 實(shí)現(xiàn)隊(duì)列，就要實(shí)現(xiàn)它的3個方法：Enqueue（入隊(duì)）、Dequeue（出隊(duì)）和Peek（隊(duì)頭）。 1）stack1存的是每次進(jìn)來的元素，所以Enqueue就是把進(jìn)來的元素push到stack1中。 2）而對于Dequeue，一開始stack2是空的，所以我們把stack1中的元素全都pop到stack2中，這樣stack2的棧頂就是隊(duì)頭。只要stack2不為空，那么每次出隊(duì)，就相當(dāng)于stack2的pop。 3）接下來，每入隊(duì)一個元素，仍然push到stack1中。每出隊(duì)一個元素，如果stack2不為空，就從stack2中pop一個元素；如果stack2為空，就重復(fù)上面的操作——把stack1中的元素全都pop到stack2中。 4）Peek操作，類似于Dequeue，只是不需要出隊(duì)，所以我們調(diào)用stack2的Peek操作。當(dāng)然，如果stack2為空，就把stack1中的元素全都pop到stack2中。 5）注意邊界的處理，如果stack2和stack1都為空，才等于隊(duì)列為空，此時不能進(jìn)行Peek和Dequeue操作。 按照上述分析，算法實(shí)現(xiàn)如下：
public class NewQueue{private Stack stack1;private Stack stack2;public NewQueue(){stack1 = new Stack();stack2 = new Stack();}public void Enqueue(int element){stack1.Push(element);}public int Dequeue(){if (stack2.Count == 0){if (stack1.Count == 0)throw new Exception(“The queue is empty”);elsewhile (stack1.Count > 0)stack2.Push(stack1.Pop());}return (int)stack2.Pop();}public int Peek(){if (stack2.Count == 0){if (stack1.Count == 0)throw new Exception(“The queue is empty”);elsewhile (stack1.Count > 0)stack2.Push(stack1.Pop());}return (int)stack2.Peek();}}4.用兩個隊(duì)列實(shí)現(xiàn)棧 這個嘛，就要queue1和queue2輪流存儲數(shù)據(jù)了。這個“輪流”發(fā)生在Pop和Peek的時候，假設(shè)此時我們把所有數(shù)據(jù)存在queue1中（此時queue2為空），我們把queue1的n-1個元素放到queue2中，queue中最后一個元素就是我們想要pop的元素，此時queue2存有n-1個元素（queue1為空）。 至于Peek，則是每次轉(zhuǎn)移n個數(shù)據(jù)，再轉(zhuǎn)移最后一個元素的時候，將其計(jì)下并返回。 那么Push的操作，則需要判斷當(dāng)前queue1和queue2哪個為空，將新元素放到不為空的隊(duì)列中。
public class NewStack{private Queue queue1;private Queue queue2;public NewStack(){queue1 = new Queue();queue2 = new Queue();}public void Push(int element){if (queue1.Count == 0)queue2.Enqueue(element);elsequeue1.Enqueue(element);}public int Pop(){if (queue1.Count == 0 && queue2.Count == 0)throw new Exception(“The stack is empty”);if (queue1.Count > 0){while (queue1.Count > 1){queue2.Enqueue(queue1.Dequeue());}//還剩一個return (int)queue1.Dequeue();}else //queue2.Count > 0{while (queue2.Count > 1){queue1.Enqueue(queue2.Dequeue());}//還剩一個return (int)queue2.Dequeue();}}public int Peek(){if (queue1.Count == 0 && queue2.Count == 0)throw new Exception(“The stack is empty”);int result = 0;if (queue1.Count > 0){while (queue1.Count > 1){queue2.Enqueue(queue1.Dequeue());}//還剩一個result = (int)queue1.Dequeue();queue2.Enqueue(result);}else //queue2.Count > 0{while (queue2.Count > 1){queue1.Enqueue(queue2.Dequeue());}//還剩一個result = (int)queue2.Dequeue();queue1.Enqueue(result);}return result;}}5.棧的push、pop序列是否一致 輸入兩個整數(shù)序列。其中一個序列表示棧的push順序，判斷另一個序列有沒有可能是對應(yīng)的pop順序。為了簡單起見，我們假設(shè)push序列的任意兩個整數(shù)都是不相等的。 比如輸入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一個pop系列。因?yàn)榭梢杂腥缦碌膒ush和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，這樣得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。 網(wǎng)上的若干算法都太復(fù)雜了，現(xiàn)提出包氏算法如下： 先for循環(huán)把a(bǔ)rr1中的元素入棧，并在每次遍歷時，檢索arr2中可以pop的元素。如果循環(huán)結(jié)束，而stack中還有元素，就說明arr2序列不是pop序列。
static boolJudgeSequenceIsPossible(int[] arr1,int[] arr2){Stack stack = new Stack();for (int i = 0, j = 0; i < arr1.Length; i++){stack.Push(arr1[i]);while(stack.Count > 0 && (int)stack.Peek() == arr2[j]){stack.Pop();j++;}}return stack.Count == 0;}6.遞歸反轉(zhuǎn)一個棧，要求不得重新申請一個同樣的棧，空間復(fù)雜度o(1) 算法思想：漢諾塔的思想，非常復(fù)雜，玩過九連環(huán)的人都想得通的.
static void ReverseStack(ref Stack stack){if (stack.Count == 0)return;object top = stack.Pop();ReverseStack(ref stack);if (stack.Count == 0){stack.Push(top);return;}object top2 = stack.Pop();ReverseStack(ref stack);stack.Push(top);ReverseStack(ref stack);stack.Push(top2);}7.給棧排個序 本題目是上一題目的延伸
static void Sort(ref Stack stack){if (stack.Count == 0)return;object top = stack.Pop();Sort(ref stack);if (stack.Count == 0){stack.Push(top);return;}object top2 = stack.Pop();if ((int)top > (int)top2){stack.Push(top);Sort(ref stack);stack.Push(top2);}else{stack.Push(top2);Sort(ref stack);stack.Push(top);}}8.如何用一個數(shù)組實(shí)現(xiàn)兩個棧 繼續(xù)我所提倡的摳門兒思想，也不枉我和青菜臉相交一場。 網(wǎng)上流傳著兩種方法： 方法1 采用交叉索引的方法 一號棧所占數(shù)組索引為0, 2, 4, 6, 8……(K*2) 二號棧所占數(shù)組索引為1，3，5，7，9 ……(K*2 + 1) 算法實(shí)現(xiàn)如下：
public class NewStack{object[] arr;int top1;int top2;public NewStack(int capticy){arr = new object[capticy];top1 = -1;top2 = -2;}public void Push(int type, object element){if (type == 1){if (top1 + 2 >= arr.Length)throw new Exception(“The stack is full”);else{top1 += 2;arr[top1] = element;}}else //type==2{if (top2 + 2 >= arr.Length)throw new Exception(“The stack is full”);else{top2 += 2;arr[top2] = element;}}}public object Pop(int type){object obj = null;if (type == 1){if (top1 == -1)throw new Exception(“The stack is empty”);else{obj = arr[top1];arr[top1] = null;top1 -= 2;}}else //type == 2{if (top2 == -2)throw new Exception(“The stack is empty”);else{obj = arr[top2];arr[top2] = null;top2 -= 2;}}return obj;}public object Peek(int type){if (type == 1){if (top1 == -1)throw new Exception(“The stack is empty”);return arr[top1];}else //type == 2{if (top2 == -2)throw new Exception(“The stack is empty”);return arr[top2];}}}方法2： 第一個棧A：從最左向右增長 第二個棧B：從最右向左增長
public class NewStack{object[] arr;int top1;int top2;public NewStack(int capticy){arr = new object[capticy];top1 = 0;top2 = capticy;}public void Push(int type, object element){if (top1 == top2)throw new Exception(“The stack is full”);if (type == 1){arr[top1] = element;top1++;}else //type==2{top2–;arr[top2] = element;}}public object Pop(int type){object obj = null;if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);else{top1–;obj = arr[top1];arr[top1] = null;}}else //type == 2{if (top2 == arr.Length)throw new Exception(“The stack is empty”);else{obj = arr[top2];arr[top2] = null;top2++;}}return obj;}public object Peek(int type){if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);return arr[top1 - 1];}else //type == 2{if (top2 == arr.Length)throw new Exception(“The stack is empty”);return arr[top2];}}}綜合比較上述兩種算法，我們發(fā)現(xiàn)，算法1實(shí)現(xiàn)的兩個棧，每個都只有n/2個空間大小；而算法2實(shí)現(xiàn)的兩個棧，如果其中一個很小，另一個則可以很大，它們的和為常數(shù)n。
9.如何用一個數(shù)組實(shí)現(xiàn)三個棧 最后，讓我們把摳門兒進(jìn)行到底，相信看完本文，你已經(jīng)從物質(zhì)和精神上都升級為一個摳門兒主義者。 如果還使用交叉索引的辦法，每個棧都只有N/3個空間。 讓我們只好使用上個題目的第2個方法，不過這只能容納2個棧，我們還需要一個位置存放第3個棧，不如考慮數(shù)組中間的位置——第3個棧的增長規(guī)律可以如下： 第1個入棧C的元素進(jìn)mid處 第2個入棧C的元素進(jìn)mid+1處 第3個入棧C的元素進(jìn)mid-1處 第4個入棧C的元素進(jìn)mid+2處 這個方法的好處是， 每個棧都有接近N/3個空間。
public class NewStack{object[] arr;int top1;int top2;int top3_left;int top3_right;bool isLeft;public NewStack(int capticy){arr = new object[capticy];top1 = 0;top2 = capticy;isLeft = true;top3_left = capticy / 2;top3_right = top3_left + 1;}public void Push(int type, object element){if (type == 1){if (top1 == top3_left + 1)throw new Exception(“The stack is full”);arr[top1] = element;top1++;}else if (type == 2){if (top2 == top3_right)throw new Exception(“The stack is full”);top2–;arr[top2] = element;}else //type==3{if (isLeft){if (top1 == top3_left + 1)throw new Exception(“The stack is full”);arr[top3_left] = element;top3_left–;}else{if (top2 == top3_right)throw new Exception(“The stack is full”);arr[top3_right] = element;top3_right++;}isLeft = !isLeft;}}public object Pop(int type){object obj = null;if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);else{top1–;obj = arr[top1];arr[top1] = null;}}else if (type == 2){if (top2 == arr.Length)throw new Exception(“The stack is empty”);else{obj = arr[top2];arr[top2] = null;top2++;}}else //type==3{if (top3_right == top3_left + 1)throw new Exception(“The stack is empty”);if (isLeft){top3_left++;obj = arr[top3_left];arr[top3_left] = null;}else{top3_right–;obj = arr[top3_right];arr[top3_right] = null;}isLeft = !isLeft;}return obj;}public object Peek(int type){if (type == 1){if (top1 == 0)throw new Exception(“The stack is empty”);return arr[top1 - 1];}else if (type == 2){if (top2 == arr.Length)throw new Exception(“The stack is empty”);return arr[top2];}else //type==3{if (top3_right == top3_left + 1)throw new Exception(“The stack is empty”);if (isLeft)return arr[top3_left + 1];elsereturn arr[top3_right - 1];}}}新聞熱點(diǎn)
疑難解答
