關(guān)于java棧和隊列的經(jīng)典面試題目總結(jié)
面試的時候，棧和隊列經(jīng)常會成對出現(xiàn)來考察。本文包含棧和隊列的如下考試內(nèi)容：
（1）棧的創(chuàng)建
�。�2）隊列的創(chuàng)建
�。�3）兩個棧實現(xiàn)一個隊列
�。�4）兩個隊列實現(xiàn)一個棧
�。�5）設計含最小函數(shù)min()的棧，要求min、push、pop、的時間復雜度都是O(1)
�。�6）判斷棧的push和pop序列是否一致
1、棧的創(chuàng)建：
我們接下來通過鏈表的形式來創(chuàng)建棧，方便擴充。
代碼實現(xiàn)：
public class Stack {public Node head; public Node current;//方法：入棧操作 public void push(int data) { if (head == null) { head = new Node(data); current = head; } else { Node node = new Node(data); node.pre = current;//current結(jié)點將作為當前結(jié)點的前驅(qū)結(jié)點 current = node; //讓current結(jié)點永遠指向新添加的那個結(jié)點 } }public Node pop() { if (current == null) { return null; }Node node = current; // current結(jié)點是我們要出棧的結(jié)點 current = current.pre; //每出棧一個結(jié)點后，current后退一位 return node;}class Node { int data; Node pre; //我們需要知道當前結(jié)點的前一個結(jié)點public Node(int data) { this.data = data; } }public static void main(String[] args) {Stack stack = new Stack(); stack.push(1); stack.push(2); stack.push(3);System.out.println(stack.pop().data); System.out.println(stack.pop().data); System.out.println(stack.pop().data); }}
入棧操作時，14、15行代碼是關(guān)鍵。
運行效果：
2、隊列的創(chuàng)建：
隊列的創(chuàng)建有兩種形式：基于數(shù)組結(jié)構(gòu)實現(xiàn)（順序隊列）、基于鏈表結(jié)構(gòu)實現(xiàn)（鏈式隊列）。
我們接下來通過鏈表的形式來創(chuàng)建隊列，這樣的話，隊列在擴充時會比較方便。隊列在出隊時，從頭結(jié)點head開始。
代碼實現(xiàn)：
入棧時，和在普通的鏈表中添加結(jié)點的操作是一樣的'；出隊時，出的永遠都是head結(jié)點。
public class Queue { public Node head; public Node curent;//方法：鏈表中添加結(jié)點 public void add(int data) { if (head == null) { head = new Node(data); curent = head; } else { curent.next = new Node(data); curent = curent.next; } }//方法：出隊操作 public int pop() throws Exception { if (head == null) { throw new Exception("隊列為空"); }Node node = head; //node結(jié)點就是我們要出隊的結(jié)點 head = head.next; //出隊之后，head指針向下移return node.data;}class Node { int data; Node next;public Node(int data) { this.data = data; } }public static void main(String[] args) throws Exception { Queue queue = new Queue(); //入隊操作 for (int i = 0; i < 5; i++) { queue.add(i); }//出隊操作 System.out.println(queue.pop()); System.out.println(queue.pop()); System.out.println(queue.pop());}}
運行效果：
3、兩個棧實現(xiàn)一個隊列：
思路：
棧1用于存儲元素，棧2用于彈出元素，負負得正。
說的通俗一點，現(xiàn)在把數(shù)據(jù)1、2、3分別入棧一，然后從棧一中出來（3、2、1），放到棧二中，那么，從棧二中出來的數(shù)據(jù)（1、2、3）就符合隊列的規(guī)律了，即負負得正。
完整版代碼實現(xiàn)：
import java.util.Stack;/*** Created by smyhvae on 2015/9/9.*/public class Queue {private Stack
注意第22行和第30行代碼的順序，以及注釋，需要仔細理解其含義。
運行效果：
4、兩個隊列實現(xiàn)一個棧：
思路：
將1、2、3依次入隊列一， 然后最上面的3留在隊列一，將下面的2、3入隊列二，將3出隊列一，此時隊列一空了，然后把隊列二中的所有數(shù)據(jù)入隊列一；將最上面的2留在隊列一，將下面的3入隊列二。。。依次循環(huán)。
代碼實現(xiàn)：
import java.util.ArrayDeque;import java.util.Queue;/*** Created by smyhvae on 2015/9/9.*/public class Stack {Queue
運行效果：
5、設計含最小函數(shù)min()的棧，要求min、push、pop、的時間復雜度都是O(1)。min方法的作用是：就能返回是棧中的最小值�！疚⑿琶嬖囶}】
普通思路：
一般情況下，我們可能會這么想：利用min變量，每次添加元素時，都和min元素作比較，這樣的話，就能保證min存放的是最小值。但是這樣的話，會存在一個問題：如果最小的元素出棧了，那怎么知道剩下的元素中哪個是最小的元素呢？
改進思路：
這里需要加一個輔助棧，用空間換取時間。輔助棧中，棧頂永遠保存著當前棧中最小的數(shù)值。具體是這樣的：原棧中，每次添加一個新元素時，就和輔助棧的棧頂元素相比較，如果新元素小，就把新元素的值放到輔助棧中，如果新元素大，就把輔助棧的棧頂元素再copy一遍放到輔助棧的棧頂；原棧中，出棧時，
完整代碼實現(xiàn)：
import java.util.Stack;/*** Created by smyhvae on 2015/9/9.*/public class MinStack {private Stack
運行效果：
6、判斷棧的push和pop序列是否一致：
通俗一點講：已知一組數(shù)據(jù)1、2、3、4、5依次進棧，那么它的出棧方式有很多種，請判斷一下給出的出棧方式是否是正確的？
例如：
數(shù)據(jù)：
1、2、3、4、5
出棧1：
5、4、3、2、1（正確）
出棧2：
4、5、3、2、1（正確）
出棧3：
4、3、5、1、2（錯誤）
完整版代碼：
import java.util.Stack;/*** Created by smyhvae on 2015/9/9.
代碼比較簡潔，但也比較難理解，要仔細體會。
運行效果：
以上就是有關(guān)java棧和隊列的經(jīng)典面試題目，希望可以幫助大家順利通過面試。
【關(guān)于java棧和隊列的經(jīng)典面試題目總結(jié)】相關(guān)文章：