Java完成棧和隊列面試題。本站提示廣大學習愛好者：（Java完成棧和隊列面試題）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成棧和隊列面試題正文
面試的時刻，棧和隊列常常會成對湧現來考核。本文包括棧和隊列的以下測驗內容：
（1）棧的創立
（2）隊列的創立
（3）兩個棧完成一個隊列
（4）兩個隊列完成一個棧
（5）設計含最小函數min()的棧，請求min、push、pop、的時光龐雜度都是O(1)
（6）斷定棧的push和pop序列能否分歧
1、棧的創立：
我們接上去經由過程鏈表的情勢來創立棧，便利擴大。
代碼完成：
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結點將作為以後結點的先驅結點
current = node; //讓current結點永久指向新添加的誰人結點
}
}
public Node pop() {
if (current == null) {
return null;
}
Node node = current; // current結點是我們要出棧的結點
current = current.pre; //每出棧一個結點後，current撤退退卻一名
return node;
}
class Node {
int data;
Node pre; //我們須要曉得以後結點的前一個結點
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行代碼是症結。
運轉後果：
2、隊列的創立：
隊列的創立有兩種情勢：基於數組構造完成（次序隊列）、基於鏈表構造完成（鏈式隊列）。
我們接上去經由過程鏈表的情勢來創立隊列，如許的話，隊列在擴大時會比擬便利。隊列在出隊時，從頭結點head開端。
代碼完成：
入棧時，和在通俗的鏈表中添加結點的操作是一樣的；出隊時，出的永久都是head結點。
public class Queue {
public Node head;
public Node curent;
//辦法：鏈表中添加結點
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結點就是我們要出隊的結點
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、兩個棧完成一個隊列：
思緒：
棧1用於存儲元素，棧2用於彈出元素，負負得正。
說的淺顯一點，如今把數據1、2、3分離入棧一，然後從棧一中出來（3、2、1），放到棧二中，那末，從棧二中出來的數據（1、2、3）就相符隊列的紀律了，即負負得正。
完全版代碼完成：
import java.util.Stack;
/**
* Created by smyhvae on 2015/9/9.
*/
public class Queue {
private Stack<Integer> stack1 = new Stack<>();//履行入隊操作的棧
private Stack<Integer> stack2 = new Stack<>();//履行出隊操作的棧
//辦法：給隊列增長一個入隊的操作
public void push(int data) {
stack1.push(data);
}
//辦法：給隊列正價一個出隊的操作
public int pop() throws Exception {
if (stack2.empty()) {//stack1中的數據放到stack2之前，先要包管stack2外面是空的（要末一開端就是空的，要末是stack2中的數據出完了），否則出隊的次序會亂的，這一點很輕易忘
while (!stack1.empty()) {
stack2.push(stack1.pop());//把stack1中的數據出棧，放到stack2中【焦點代碼】
}
}
if (stack2.empty()) { //stack2為空時，有兩種能夠：1、一開端，兩個棧的數據都是空的；2、stack2中的數據出完了
throw new Exception("隊列為空");
}
return stack2.pop();
}
public static void main(String[] args) throws Exception {
Queue queue = new Queue();
queue.push(1);
queue.push(2);
queue.push(3);
System.out.println(queue.pop());
queue.push(4);
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
}
}
留意第22行和第30行代碼的次序，和正文，須要細心懂得其寄義。
運轉後果：
4、兩個隊列完成一個棧：
思緒：
將1、2、3順次入隊列一， 然後最下面的3留在隊列一，將上面的2、3入隊列二，將3出隊列一，此時隊列一空了，然後把隊列二中的一切數據入隊列一；將最下面的2留在隊列一，將上面的3入隊列二。。。順次輪回。
代碼完成：
import java.util.ArrayDeque;
import java.util.Queue;
/**
* Created by smyhvae on 2015/9/9.
*/
public class Stack {
Queue<Integer> queue1 = new ArrayDeque<Integer>();
Queue<Integer> queue2 = new ArrayDeque<Integer>();
//辦法：入棧操作
public void push(int data) {
queue1.add(data);
}
//辦法：出棧操作
public int pop() throws Exception {
int data;
if (queue1.size() == 0) {
throw new Exception("棧為空");
}
while (queue1.size() != 0) {
if (queue1.size() == 1) {
data = queue1.poll();
while (queue2.size() != 0) { //把queue2中的全體數據放到隊列一中
queue1.add(queue2.poll());
return data;
}
}
queue2.add(queue1.poll());
}
throw new Exception("棧為空");//不曉得這一行的代碼是甚麼意思
}
public static void main(String[] args) throws Exception {
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push(4);
}
}
運轉後果：
5、設計含最小函數min()的棧，請求min、push、pop、的時光龐雜度都是O(1)。min辦法的感化是：就可以前往是棧中的最小值。【微信面試題】
通俗思緒：
普通情形下，我們能夠會這麼想：應用min變量，每次添加元素時，都和min元素作比擬，如許的話，就可以包管min寄存的是最小值。然則如許的話，會存在一個成績：假如最小的元素出棧了，那怎樣曉得剩下的元素中哪一個是最小的元素呢？
改良思緒：
這裡須要加一個幫助棧，用空間換取時光。幫助棧中，棧頂永久保留著以後棧中最小的數值。詳細是如許的：原棧中，每次添加一個新元素時，就和幫助棧的棧頂元素比擬較，假如新元素小，就把新元素的值放到幫助棧中，假如新元素年夜，就把幫助棧的棧頂元素再copy一遍放到幫助棧的棧頂；原棧中，出棧時，
完全代碼完成：
import java.util.Stack;
/**
* Created by smyhvae on 2015/9/9.
*/
public class MinStack {
private Stack<Integer> stack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>(); //幫助棧：棧頂永久保留stack中以後的最小的元素
public void push(int data) {
stack.push(data); //直接往棧中添加數據
//在幫助棧中須要做斷定
if (minStack.size() == 0 || data < minStack.peek()) {
minStack.push(data);
} else {
minStack.add(minStack.peek()); //【焦點代碼】peek辦法前往的是棧頂的元素
}
}
public int pop() throws Exception {
if (stack.size() == 0) {
throw new Exception("棧中為空");
}
int data = stack.pop();
minStack.pop(); //焦點代碼
return data;
}
public int min() throws Exception {
if (minStack.size() == 0) {
throw new Exception("棧中空了");
}
return minStack.peek();
}
public static void main(String[] args) throws Exception {
MinStack stack = new MinStack();
stack.push(4);
stack.push(3);
stack.push(5);
System.out.println(stack.min());
}
}
運轉後果：
6、斷定棧的push和pop序列能否分歧：
淺顯一點講：已知一組數據1、2、3、4、5順次進棧，那末它的出棧方法有許多種，請斷定一下給出的出棧方法能否是准確的？
例如：
數據：
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.
*/
public class StackTest {
//辦法：data1數組的次序表現入棧的次序。如今斷定data2的這類出棧次序能否准確
public static boolean sequenseIsPop(int[] data1, int[] data2) {
Stack<Integer> stack = new Stack<Integer>(); //這裡須要用到幫助棧
for (int i = 0, j = 0; i < data1.length; i++) {
stack.push(data1[i]);
while (stack.size() > 0 && stack.peek() == data2[j]) {
stack.pop();
j++;
}
}
return stack.size() == 0;
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
int[] data1 = {1, 2, 3, 4, 5};
int[] data2 = {4, 5, 3, 2, 1};
int[] data3 = {4, 5, 2, 3, 1};
System.out.println(sequenseIsPop(data1, data2));
System.out.println(sequenseIsPop(data1, data3));
}
}
代碼比擬簡練，但也比擬難懂得，要細心領會。
運轉後果：
以上就是有關java棧和隊列的經典面試標題，願望可以贊助年夜家順遂經由過程面試。
