程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> Java完成棧和隊列面試題

Java完成棧和隊列面試題

編輯:關於JAVA

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棧和隊列的經典面試標題,願望可以贊助年夜家順遂經由過程面試。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved