java为什么不推荐使用stack_栈和队列的面试题Java实现，Stack类继承于Vector这两个类都不推荐使用...
在 thinking in java中看到過說Stack類繼承于Vector，而這兩個(gè)類都不推薦使用了，但是在做一到OJ題時(shí)，我用LinkedList來模擬棧和直接用Stack，發(fā)現(xiàn)在進(jìn)行入棧出棧操作時(shí)Stack的速度竟然還快一點(diǎn)
然而需要多線程的時(shí)候有Collections.synchronizedList，還有java.util.concurrent包下的。所以還是忘了這貨吧。
Java 中還有非常多的地方使用到了棧。
棧是一種數(shù)據(jù)結(jié)構(gòu)，所以它使用的非常普遍。面試中遇到它的可能性也比較大，所以還是很有必要掌握的。
java.util.Stack?類 Java 官方已經(jīng)不在建議使用了。現(xiàn)在官方推薦使用?java.util.Deque。類似下面的用法：
Deque stack = new ArrayDeque();
那么 Java 為什么不推薦使用 Stack 呢？為什么 Stack 被廢棄了呢？
很簡單，因?yàn)?Stack 是 JDK 1.0 的產(chǎn)物。它繼承自 Vector，Vector 都不被推薦使用了，你說 Stack 還會(huì)被推薦嗎？
當(dāng)初 JDK1.0 在開發(fā)時(shí)，可能為了快速的推出一些基本的數(shù)據(jù)結(jié)構(gòu)操作，所以推出了一些比較粗糙的類。比如，Vector、Stack、Hashtable等。這些類中的一些方法加上了 synchronized 關(guān)鍵字，容易給一些初級程序員在使用上造成一些誤解！而且在之前的幾個(gè)版本中，性能還不怎么好。
基于 Vector 實(shí)現(xiàn)的棧 Stack。底層實(shí)際上還是數(shù)組，所以還是存在需要擴(kuò)容。Vector 是由數(shù)組實(shí)現(xiàn)的集合類，他包含了大量集合處理的方法。而 Stack 之所以繼承 Vector，是為了復(fù)用 Vector 中的方法，來實(shí)現(xiàn)進(jìn)棧(push)、出棧(pop)等操作。這里就是 Stack 設(shè)計(jì)不好的地方，既然只是為了實(shí)現(xiàn)棧，不用鏈表來單獨(dú)實(shí)現(xiàn)，而是為了復(fù)用簡單的方法而迫使它繼承 Vector，Stack 和 Vector 本來是毫無關(guān)系的。這使得 Stack 在基于數(shù)組實(shí)現(xiàn)上效率受影響，另外因?yàn)槔^承 Vector 類，Stack 可以復(fù)用 Vector 大量方法，這使得 Stack 在設(shè)計(jì)上不嚴(yán)謹(jǐn)。
基于上一篇文章中，我們對棧存在的一個(gè)基本認(rèn)識(shí)，下面我們使用 LinkedList 自己實(shí)現(xiàn)一個(gè)棧。
package com.xttblog;
import java.util.LinkedList;
public class Stack {
LinkedList list;
public Stack(){
list = new LinkedList();
}
public E pop(){
return list.removeLast();
}
public void push(E o){
list.add(o);
}
public E getTop(){
return list.getLast();
}
public boolean isEmpty(){
return list.size()==0;
}
public int size(){
return list.size();
}
}
棧的最基本的特征是LIFO(Last In First Out)，因此棧又被稱為后進(jìn)先出的線性表。所以上面采用 LinkedList 實(shí)現(xiàn)的棧看起來也非常的簡單。雖然簡單，但我們并不需要重復(fù)的輪子。Java 提供了 Deuqe。Deque 是繼承自 Queue，而 Stack 是繼承自 Vector。Java 中的 Deuqe，即“double ended queue”的縮寫，是 Java 中的雙端隊(duì)列集合類型。Deque 具備普通隊(duì)列 FIFO 的功能，同時(shí)它也具備了 Stack 的 LIFO 功能，并且保留了 push 和 pop 函數(shù)，所以使用起來應(yīng)該是一點(diǎn)障礙都沒有。
ArrayDeque 是 Deque 接口的一種具體實(shí)現(xiàn)，是依賴于可變數(shù)組來實(shí)現(xiàn)的。ArrayDeque 沒有容量限制，可根據(jù)需求自動(dòng)進(jìn)行擴(kuò)容。ArrayDeque 可以作為棧來使用，效率要高于 Stack。ArrayDeque 也可以作為隊(duì)列來使用，效率相較于基于雙向鏈表的 LinkedList 也要更好一些。注意，ArrayDeque 不支持為 ?null 的元素。
棧和隊(duì)列的面試題Java實(shí)現(xiàn)
二、棧和隊(duì)列：
面試的時(shí)候，棧和隊(duì)列經(jīng)常會(huì)成對出現(xiàn)來考察。本文包含棧和隊(duì)列的如下考試內(nèi)容：
(1)棧的創(chuàng)建
(2)隊(duì)列的創(chuàng)建
(3)兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
(4)兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧
(5)設(shè)計(jì)含最小函數(shù)min()的棧，要求min、push、pop、的時(shí)間復(fù)雜度都是O(1)
(6)判斷棧的push和pop序列是否一致
1、棧的創(chuàng)建：
我們接下來通過鏈表的形式來創(chuàng)建棧，方便擴(kuò)充。
代碼實(shí)現(xiàn)：
1 public classStack {
2
3 publicNode head;
4 publicNode current;
5
6
7 //方法：入棧操作
8 public void push(intdata) {
9 if (head == null) {
10 head = newNode(data);
11 current =head;
12 } else{
13 Node node = newNode(data);
14 node.pre = current;//current結(jié)點(diǎn)將作為當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
15 current = node; //讓current結(jié)點(diǎn)永遠(yuǎn)指向新添加的那個(gè)結(jié)點(diǎn)
16 }
17 }
18
19 publicNode pop() {
20 if (current == null) {
21 return null;
22 }
23
24 Node node = current; //current結(jié)點(diǎn)是我們要出棧的結(jié)點(diǎn)
25 current = current.pre; //每出棧一個(gè)結(jié)點(diǎn)后，current后退一位
26 returnnode;
27
28 }
29
30
31 classNode {
32 intdata;
33 Node pre; //我們需要知道當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
34
35 public Node(intdata) {
36 this.data =data;
37 }
38 }
39
40
41 public static voidmain(String[] args) {
42
43 Stack stack = newStack();
44 stack.push(1);
45 stack.push(2);
46 stack.push(3);
47
48 System.out.println(stack.pop().data);
49 System.out.println(stack.pop().data);
50 System.out.println(stack.pop().data);
51 }
52
53 }
入棧操作時(shí)，14、15行代碼是關(guān)鍵。
運(yùn)行效果：
2、隊(duì)列的創(chuàng)建：
隊(duì)列的創(chuàng)建有兩種形式：基于數(shù)組結(jié)構(gòu)實(shí)現(xiàn)(順序隊(duì)列)、基于鏈表結(jié)構(gòu)實(shí)現(xiàn)(鏈?zhǔn)疥?duì)列)。
我們接下來通過鏈表的形式來創(chuàng)建隊(duì)列，這樣的話，隊(duì)列在擴(kuò)充時(shí)會(huì)比較方便。隊(duì)列在出隊(duì)時(shí)，從頭結(jié)點(diǎn)head開始。
代碼實(shí)現(xiàn)：
入棧時(shí)，和在普通的鏈表中添加結(jié)點(diǎn)的操作是一樣的；出隊(duì)時(shí)，出的永遠(yuǎn)都是head結(jié)點(diǎn)。
1 public classQueue {
2 publicNode head;
3 publicNode curent;
4
5 //方法：鏈表中添加結(jié)點(diǎn)
6 public void add(intdata) {
7 if (head == null) {
8 head = newNode(data);
9 curent =head;
10 } else{
11 curent.next = newNode(data);
12 curent =curent.next;
13 }
14 }
15
16 //方法：出隊(duì)操作
17 public int pop() throwsException {
18 if (head == null) {
19 throw new Exception("隊(duì)列為空");
20 }
21
22 Node node = head; //node結(jié)點(diǎn)就是我們要出隊(duì)的結(jié)點(diǎn)
23 head = head.next; //出隊(duì)之后，head指針向下移
24
25 returnnode.data;
26
27 }
28
29
30 classNode {
31 intdata;
32 Node next;
33
34 public Node(intdata) {
35 this.data =data;
36 }
37 }
38
39
40 public static void main(String[] args) throwsException {
41 Queue queue = newQueue();
42 //入隊(duì)操作
43 for (int i = 0; i < 5; i++) {
44 queue.add(i);
45 }
46
47 //出隊(duì)操作
48 System.out.println(queue.pop());
49 System.out.println(queue.pop());
50 System.out.println(queue.pop());
51
52 }
53 }
運(yùn)行效果：
3、兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列：
思路：
棧1用于存儲(chǔ)元素，棧2用于彈出元素，負(fù)負(fù)得正。
說的通俗一點(diǎn)，現(xiàn)在把數(shù)據(jù)1、2、3分別入棧一，然后從棧一中出來(3、2、1)，放到棧二中，那么，從棧二中出來的數(shù)據(jù)(1、2、3)就符合隊(duì)列的規(guī)律了，即負(fù)負(fù)得正。
完整版代碼實(shí)現(xiàn)：
1 importjava.util.Stack;
2
3 /**
4 * Created by smyhvae on 2015/9/9.
5 */
6 public classQueue {
7
8 private Stack stack1 = new Stack<>();//執(zhí)行入隊(duì)操作的棧
9 private Stack stack2 = new Stack<>();//執(zhí)行出隊(duì)操作的棧
10
11
12 //方法：給隊(duì)列增加一個(gè)入隊(duì)的操作
13 public void push(intdata) {
14 stack1.push(data);
15
16 }
17
18 //方法：給隊(duì)列正價(jià)一個(gè)出隊(duì)的操作
19 public int pop() throwsException {
20
21
22 if (stack2.empty()) {//stack1中的數(shù)據(jù)放到stack2之前，先要保證stack2里面是空的(要么一開始就是空的，要么是stack2中的數(shù)據(jù)出完了)，不然出隊(duì)的順序會(huì)亂的，這一點(diǎn)很容易忘
23
24 while (!stack1.empty()) {
25 stack2.push(stack1.pop());//把stack1中的數(shù)據(jù)出棧，放到stack2中【核心代碼】
26 }
27
28 }
29
30 if (stack2.empty()) { //stack2為空時(shí)，有兩種可能：1、一開始，兩個(gè)棧的數(shù)據(jù)都是空的；2、stack2中的數(shù)據(jù)出完了
31 throw new Exception("隊(duì)列為空");
32 }
33
34 returnstack2.pop();
35 }
36
37 public static void main(String[] args) throwsException {
38 Queue queue = newQueue();
39 queue.push(1);
40 queue.push(2);
41 queue.push(3);
42
43 System.out.println(queue.pop());
44
45 queue.push(4);
46
47 System.out.println(queue.pop());
48 System.out.println(queue.pop());
49 System.out.println(queue.pop());
50
51 }
52
53 }
注意第22行和第30行代碼的順序，以及注釋，需要仔細(xì)理解其含義。
運(yùn)行效果：
4、兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧：
思路：
將1、2、3依次入隊(duì)列一， 然后最上面的3留在隊(duì)列一，將下面的2、3入隊(duì)列二，將3出隊(duì)列一，此時(shí)隊(duì)列一空了，然后把隊(duì)列二中的所有數(shù)據(jù)入隊(duì)列一；將最上面的2留在隊(duì)列一，將下面的3入隊(duì)列二。。。依次循環(huán)。
代碼實(shí)現(xiàn)：
1 importjava.util.ArrayDeque;
2 importjava.util.Queue;
3
4 /**
5 * Created by smyhvae on 2015/9/9.
6 */
7 public classStack {
8
9 Queue queue1 = new ArrayDeque();
10 Queue queue2 = new ArrayDeque();
11
12 //方法：入棧操作
13 public void push(intdata) {
14 queue1.add(data);
15 }
16
17 //方法：出棧操作
18 public int pop() throwsException {
19 intdata;
20 if (queue1.size() == 0) {
21 throw new Exception("棧為空");
22 }
23
24 while (queue1.size() != 0) {
25 if (queue1.size() == 1) {
26 data =queue1.poll();
27 while (queue2.size() != 0) { //把queue2中的全部數(shù)據(jù)放到隊(duì)列一中
28 queue1.add(queue2.poll());
29 returndata;
30 }
31 }
32 queue2.add(queue1.poll());
33 }
34 throw new Exception("棧為空");//不知道這一行的代碼是什么意思
35 }
36
37 public static void main(String[] args) throwsException {
38 Stack stack = newStack();
39
40 stack.push(1);
41 stack.push(2);
42 stack.push(3);
43
44 System.out.println(stack.pop());
45 System.out.println(stack.pop());
46 stack.push(4);
47 }
48 }
運(yùn)行效果：
5、設(shè)計(jì)含最小函數(shù)min()的棧，要求min、push、pop、的時(shí)間復(fù)雜度都是O(1)。min方法的作用是：就能返回是棧中的最小值。【微信面試題】
普通思路：
一般情況下，我們可能會(huì)這么想：利用min變量，每次添加元素時(shí)，都和min元素作比較，這樣的話，就能保證min存放的是最小值。但是這樣的話，會(huì)存在一個(gè)問題：如果最小的元素出棧了，那怎么知道剩下的元素中哪個(gè)是最小的元素呢？
改進(jìn)思路：
這里需要加一個(gè)輔助棧，用空間換取時(shí)間。輔助棧中，棧頂永遠(yuǎn)保存著當(dāng)前棧中最小的數(shù)值。具體是這樣的：原棧中，每次添加一個(gè)新元素時(shí)，就和輔助棧的棧頂元素相比較，如果新元素小，就把新元素的值放到輔助棧中，如果新元素大，就把輔助棧的棧頂元素再copy一遍放到輔助棧的棧頂；原棧中，出棧時(shí)，
完整代碼實(shí)現(xiàn)：
1 importjava.util.Stack;
2
3 /**
4 * Created by smyhvae on 2015/9/9.
5 */
6 public classMinStack {
7
8 private Stack stack = new Stack();
9 private Stack minStack = new Stack(); //輔助棧：棧頂永遠(yuǎn)保存stack中當(dāng)前的最小的元素
10
11
12 public void push(intdata) {
13 stack.push(data); //直接往棧中添加數(shù)據(jù)
14
15 //在輔助棧中需要做判斷
16 if (minStack.size() == 0 || data
17 minStack.push(data);
18 } else{
19 minStack.add(minStack.peek()); //【核心代碼】peek方法返回的是棧頂?shù)脑?/p>
20 }21 }
22
23 public int pop() throwsException {
24 if (stack.size() == 0) {
25 throw new Exception("棧中為空");
26 }
27
28 int data =stack.pop();
29 minStack.pop(); //核心代碼
30 returndata;
31 }
32
33 public int min() throwsException {
34 if (minStack.size() == 0) {
35 throw new Exception("棧中空了");
36 }
37 returnminStack.peek();
38 }
39
40 public static void main(String[] args) throwsException {
41 MinStack stack = newMinStack();
42 stack.push(4);
43 stack.push(3);
44 stack.push(5);
45
46 System.out.println(stack.min());
47 }
48 }
6、判斷棧的push和pop序列是否一致：
通俗一點(diǎn)講：已知一組數(shù)據(jù)1、2、3、4、5依次進(jìn)棧，那么它的出棧方式有很多種，請判斷一下給出的出棧方式是否是正確的？
例如：
數(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(錯(cuò)誤)
完整版代碼：
1 importjava.util.Stack;
2
3 /**
4 * Created by smyhvae on 2015/9/9.
5 */
6 public classStackTest {
7
8
9 //方法：data1數(shù)組的順序表示入棧的順序。現(xiàn)在判斷data2的這種出棧順序是否正確
10 public static boolean sequenseIsPop(int[] data1, int[] data2) {
11 Stack stack = new Stack(); //這里需要用到輔助棧
12
13 for (int i = 0, j = 0; i < data1.length; i++) {
14 stack.push(data1[i]);
15
16 while (stack.size() > 0 && stack.peek() ==data2[j]) {
17 stack.pop();
18 j++;
19 }20 }
21 return stack.size() == 0;22 }
23
24
25 public static voidmain(String[] args) {
26
27 Stack stack = new Stack();
28
29 int[] data1 = {1, 2, 3, 4, 5};
30 int[] data2 = {4, 5, 3, 2, 1};
31 int[] data3 = {4, 5, 2, 3, 1};
32
33 System.out.println(sequenseIsPop(data1, data2));
34 System.out.println(sequenseIsPop(data1, data3));
35 }
36 }
代碼比較簡潔，但也比較難理解，要仔細(xì)體會(huì)。
運(yùn)行效果：
總結(jié)
以上是生活随笔為你收集整理的java为什么不推荐使用stack_栈和队列的面试题Java实现，Stack类继承于Vector这两个类都不推荐使用...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： matlab 水文频率曲线,【求助】如何
- 下一篇： vue替换全部符合’字符串_技术成长日记