畫重點(diǎn)！Java重要的面試題：棧和隊列的實(shí)現(xiàn)

面試的時候，棧和隊列經(jīng)常會成對出現(xiàn)來考察。本文包含棧和隊列的如下考試內(nèi)容：

（1）棧的創(chuàng)建

（2）隊列的創(chuàng)建

（3）兩個棧實(shí)現(xiàn)一個隊列

（4）兩個隊列實(shí)現(xiàn)一個棧

（5）設(shè)計含最小函數(shù)min()的棧，要求min、push、pop、的時間復(fù)雜度都是O(1)

（6）判斷棧的push和pop序列是否一致

1、棧的創(chuàng)建：

我們接下來通過鏈表的形式來創(chuàng)建棧，方便擴(kuò)充。

代碼實(shí)現(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é)點(diǎn)將作為當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
            current = node;  //讓current結(jié)點(diǎn)永遠(yuǎn)指向新添加的那個結(jié)點(diǎn)
        }
    }

    public Node pop() {
        if (current == null) {
            return null;
        }

        Node node = current; // current結(jié)點(diǎn)是我們要出棧的結(jié)點(diǎn)
        current = current.pre;  //每出棧一個結(jié)點(diǎn)后，current后退一位
        return node;

    }

    class Node {
        int data;
        Node pre;  //我們需要知道當(dāng)前結(jié)點(diǎn)的前一個結(jié)點(diǎn)

        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)鍵。

運(yùn)行效果：

image.png

2、隊列的創(chuàng)建：

隊列的創(chuàng)建有兩種形式：基于數(shù)組結(jié)構(gòu)實(shí)現(xiàn)（順序隊列）、基于鏈表結(jié)構(gòu)實(shí)現(xiàn)（鏈?zhǔn)疥犃校?/p>

我們接下來通過鏈表的形式來創(chuàng)建隊列，這樣的話，隊列在擴(kuò)充時會比較方便。隊列在出隊時，從頭結(jié)點(diǎn)head開始。

代碼實(shí)現(xiàn)：

入棧時，和在普通的鏈表中添加結(jié)點(diǎn)的操作是一樣的；出隊時，出的永遠(yuǎn)都是head結(jié)點(diǎn)。

public class Queue {
    public Node head;
    public Node curent;

    //方法：鏈表中添加結(jié)點(diǎn)
    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é)點(diǎn)就是我們要出隊的結(jié)點(diǎn)
        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());

    }
}

運(yùn)行效果：

image.png

3、兩個棧實(shí)現(xiàn)一個隊列：

思路：

棧1用于存儲元素，棧2用于彈出元素，負(fù)負(fù)得正。

說的通俗一點(diǎn)，現(xiàn)在把數(shù)據(jù)1、2、3分別入棧一，然后從棧一中出來（3、2、1），放到棧二中，那么，從棧二中出來的數(shù)據(jù)（1、2、3）就符合隊列的規(guī)律了，即負(fù)負(fù)得正。

完整版代碼實(shí)現(xiàn)：

import java.util.Stack;

/**
 * Created by smyhvae on 2015/9/9.
 */
public class Queue {

    private Stack<Integer> stack1 = new Stack<>();//執(zhí)行入隊操作的棧
    private Stack<Integer> stack2 = new Stack<>();//執(zhí)行出隊操作的棧

    //方法：給隊列增加一個入隊的操作
    public void push(int data) {
        stack1.push(data);

    }

    //方法：給隊列正價一個出隊的操作
    public int pop() throws Exception {

        if (stack2.empty()) {//stack1中的數(shù)據(jù)放到stack2之前，先要保證stack2里面是空的（要么一開始就是空的，要么是stack2中的數(shù)據(jù)出完了），不然出隊的順序會亂的，這一點(diǎn)很容易忘

            while (!stack1.empty()) {
                stack2.push(stack1.pop());//把stack1中的數(shù)據(jù)出棧，放到stack2中【核心代碼】
            }

        }

        if (stack2.empty()) { //stack2為空時，有兩種可能：1、一開始，兩個棧的數(shù)據(jù)都是空的；2、stack2中的數(shù)據(jù)出完了
            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行代碼的順序，以及注釋，需要仔細(xì)理解其含義。

運(yùn)行效果：


image.png

4、兩個隊列實(shí)現(xiàn)一個棧：

思路：

將1、2、3依次入隊列一， 然后最上面的3留在隊列一，將下面的2、3入隊列二，將3出隊列一，此時隊列一空了，然后把隊列二中的所有數(shù)據(jù)入隊列一；將最上面的2留在隊列一，將下面的3入隊列二。。。依次循環(huán)。

代碼實(shí)現(xiàn)：

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中的全部數(shù)據(jù)放到隊列一中
                    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);
    }
}

運(yùn)行效果：
image.png

5、設(shè)計含最小函數(shù)min()的棧，要求min、push、pop、的時間復(fù)雜度都是O(1)。min方法的作用是：就能返回是棧中的最小值。【微信面試題】

普通思路：

一般情況下，我們可能會這么想：利用min變量，每次添加元素時，都和min元素作比較，這樣的話，就能保證min存放的是最小值。但是這樣的話，會存在一個問題：如果最小的元素出棧了，那怎么知道剩下的元素中哪個是最小的元素呢？

改進(jìn)思路：

這里需要加一個輔助棧，用空間換取時間。輔助棧中，棧頂永遠(yuǎn)保存著當(dāng)前棧中最小的數(shù)值。具體是這樣的：原棧中，每次添加一個新元素時，就和輔助棧的棧頂元素相比較，如果新元素小，就把新元素的值放到輔助棧中，如果新元素大，就把輔助棧的棧頂元素再copy一遍放到輔助棧的棧頂；原棧中，出棧時，

完整代碼實(shí)現(xiàn)：

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>(); //輔助棧：棧頂永遠(yuǎn)保存stack中當(dāng)前的最小的元素

    public void push(int data) {
        stack.push(data);  //直接往棧中添加數(shù)據(jù)

        //在輔助棧中需要做判斷
        if (minStack.size() == 0 || data < minStack.peek()) {
            minStack.push(data);
        } else {
            minStack.add(minStack.peek());   //【核心代碼】peek方法返回的是棧頂?shù)脑?        }
    }

    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());
    }
}
image.png

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（錯誤）

完整版代碼：

import java.util.Stack;

/**
 * Created by smyhvae on 2015/9/9.
 */
public class StackTest {

    //方法：data1數(shù)組的順序表示入棧的順序?，F(xiàn)在判斷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));
    }

代碼比較簡潔，但也比較難理解，要仔細(xì)體會。

運(yùn)行效果：


image.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Swift1> Swift和OC的區(qū)別1.1> Swift沒有地址/指針的概念1.2> 泛型1.3> 類型嚴(yán)謹(jǐn) 對...
    cosWriter閱讀 11,674評論 1贊 32
  • 棧 棧的英文單詞是Stack,它代表一種特殊的線性表，這種線性表只能在固定一端（通常認(rèn)為是線性表的尾端）進(jìn)行插入，...
    Jack921閱讀 1,627評論 0贊 5
  • 第一部分 HTML&CSS整理答案 1. 什么是HTML5？ 答：HTML5是最新的HTML標(biāo)準(zhǔn)。 注意：講述HT...
    kismetajun閱讀 28,827評論 1贊 45
  • 1.設(shè)計模式是什么？ 你知道哪些設(shè)計模式，并簡要敘述？設(shè)計模式是一種編碼經(jīng)驗(yàn)，就是用比較成熟的邏輯去處理某一種類型...
    龍飝閱讀 2,303評論 0贊 12
  • 1、實(shí)現(xiàn)一個棧，實(shí)現(xiàn)push和pop操作，并在O(1)的時間復(fù)雜度內(nèi)獲取當(dāng)前棧中的min值。 基本思路：設(shè)計一個類...
    Tim0227閱讀 869評論 0贊 1

友情鏈接更多精彩內(nèi)容