a、下標(biāo)最后再往后(offset 小于 array.length): index = (index + offset) % array.length。通俗一點(diǎn)，就是如果我們的數(shù)組大小為8，下標(biāo)走到了7，再往后如何回到0，我們可以（index+1）%8來(lái)實(shí)現(xiàn)。

b、下標(biāo)最前再往前的時(shí)候，我們特殊判斷一下，將其置為數(shù)組大小減一即可。

（2）區(qū)分隊(duì)列的滿(mǎn)與空

我們可以給數(shù)組預(yù)留一個(gè)位置，如果rear+1=front，則表示隊(duì)列已滿(mǎn)；如果rear=front，表示隊(duì)列為空。這個(gè)情況下，我們需要考慮隊(duì)列大小的問(wèn)題，在定義數(shù)組大小時(shí)，需要比原有的大一。

【代碼如下】

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] array;
 
    //構(gòu)造方法
    public MyCircularQueue(int k) {
       //因?yàn)轭A(yù)留位置的緣故，數(shù)組的大小要定義為k+1
       this.array=new int[k+1];
    }
    //入隊(duì)
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.array[this.rear]=value;
        this.rear=(this.rear+1)%this.array.length;
        return true;
    }
    //出隊(duì)
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.array.length;
        return true;
    }
    //獲取隊(duì)頭
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.array[front];
    }
    //獲取隊(duì)尾
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index=-1;
        if(this.rear==0){
            index=this.array.length-1;
        }else{
            index=this.rear-1;
        }
        return this.array[index];
    }
    //判斷是否為空
    public boolean isEmpty() {
        if(this.front==this.rear){
            return true;
        }
        return false;
    }
    //判斷隊(duì)列是否滿(mǎn)
    public boolean isFull() {
        if((this.rear+1)%this.array.length==this.front){
            return true;
        }
        return false;
    }
}

2、隊(duì)列實(shí)現(xiàn)棧

【OJ鏈接】

因?yàn)闂５南冗M(jìn)后出、隊(duì)列的先進(jìn)先出原則。我們需要兩個(gè)隊(duì)列來(lái)實(shí)現(xiàn)棧。當(dāng)兩個(gè)隊(duì)列都為空時(shí)，棧為空。

入棧（push）：第一次入棧無(wú)所謂，兩個(gè)隊(duì)列都為空，隨便選擇一個(gè)隊(duì)列入隊(duì)即可；后面入棧時(shí)，肯定會(huì)有一個(gè)隊(duì)列不為空，找到不為空的隊(duì)列，進(jìn)行入隊(duì)操作。
出棧（pop）：首先棧為空時(shí)，不能進(jìn)行出棧操作；棧不為空時(shí)，肯定有一個(gè)隊(duì)列為空（queue1），一個(gè)隊(duì)列不為空（queue2），將queue1中的size-1個(gè)元素出棧到queue2中（特別注意不能將求queue1大小的函數(shù)放進(jìn)循環(huán)里，queue進(jìn)行出隊(duì)操作時(shí)，其大小是改變的），最后將queue1中最后一個(gè)元素進(jìn)行出隊(duì)最為返回值。
獲取棧頂元素（top）：和出棧差不多，就不細(xì)說(shuō)了

【代碼如下】

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
 
    //構(gòu)造方法
    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }
    //入棧
    public void push(int x) {
        if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }
    //出棧
    public int pop() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int size=queue2.size();
            for(int i=0;i<size-1;++i){
                int x=queue2.poll();
                queue1.offer(x);
            }
            return queue2.poll();
        }else{
            int size=queue1.size();
            for(int i=0;i<size-1;++i){
                int x=queue1.poll();
                queue2.offer(x);
            }
            return queue1.poll();
        }
    }
    //獲取棧頂元素
    public int top() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int x=-1;
            int size=queue2.size();
            for(int i=0;i<size;++i){
                x=queue2.poll();
                queue1.offer(x);
            }
           return x;
        }else{
            int size=queue1.size();
            int x=-1;
            for(int i=0;i<size;++i){
                x=queue1.poll();
                queue2.offer(x);
            }
            return x;
        }
    }
    //判斷棧是否為空
    public boolean empty() {
        if(queue1.isEmpty()&&queue2.isEmpty()){
            return true;
        }
        return false;
    }
}

3、棧實(shí)現(xiàn)隊(duì)列

【OJ鏈接】

還是和上面一樣，需要用到兩個(gè)棧（stack1、stack2）。和實(shí)現(xiàn)棧列不同的是，入隊(duì)只能對(duì)同一個(gè)棧進(jìn)行操作。如果兩個(gè)棧都為空，則隊(duì)列為空。

入隊(duì)（push）：規(guī)定stack1用來(lái)入隊(duì)。每次入隊(duì)時(shí)，對(duì)stack1進(jìn)行入棧操作即可。
出隊(duì)（pop）：規(guī)定stack2進(jìn)行出隊(duì)操作。如果隊(duì)列為空時(shí)，不能進(jìn)行出隊(duì)操作。當(dāng)stack2為空時(shí)，我們需要將stack1中所有元素出棧，放入stack2中，然后對(duì)stack2進(jìn)行出棧操作。如果stack2不為空，則直接對(duì)stack2進(jìn)行出棧操作即可。
獲取隊(duì)列開(kāi)頭元素（peek）：和出棧操作相同，最后只需要獲取stack2的棧頂元素即可。

【代碼如下】

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //構(gòu)造方法
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入隊(duì)操作
    public void push(int x) {
        stack1.push(x);
    }
    //出隊(duì)操作
    public int pop() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.pop();
 
    }
    //獲取隊(duì)列開(kāi)頭的元素
    public int peek() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.peek();
    }
    //判斷隊(duì)列是否為空
    public boolean empty() {
        if(stack1.empty()&&stack2.empty()){
            return true;
        }
        return false;
    }
}

4、實(shí)現(xiàn)最小棧

【OJ鏈接】

其實(shí)就是要在O(1)的時(shí)間復(fù)雜度內(nèi)找到棧的最小元素。需要兩個(gè)棧來(lái)實(shí)現(xiàn)，一個(gè)棧來(lái)進(jìn)行出棧、入棧操作。只需要保證不管如何操作，另一個(gè)棧的棧頂元素都是當(dāng)前棧的最小元素即可。

兩個(gè)棧stack1、stack2，站的操作都在stack1中：

入棧：如果第一次入棧，我們需要將其也放入stack2中，之后的入棧，將入棧元素與stack2的棧頂元素進(jìn)行比較，如果其小于stack2的棧頂元素，則將其放入stack2中。
出棧：對(duì)stack1出棧時(shí)，將其與stack2的棧頂元素進(jìn)行比較，如果其等于stack2的棧頂元素，則對(duì)stack2進(jìn)行出棧操作。

這樣就能保證stack2的棧頂元素總是stack1的最小元素。注意：如果stack1中入棧兩個(gè)相同的最小元素，都需要對(duì)stack2進(jìn)行入棧。

【代碼如下】

class MinStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //構(gòu)造方法
    public MinStack() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入棧
    public void push(int val) {
        stack1.push(val);
        if(stack2.empty()){
            stack2.push(val);
        }else{
            if(val<=stack2.peek()){
                stack2.push(val);
            }
        }
    }
    //出棧
    public void pop() {
        int x=stack1.pop();
        if(x==stack2.peek()){
            stack2.pop();
        }
    }
    //獲取棧頂元素
    public int top() {
        return stack1.peek();
    }
    //獲取棧的最小元素
    public int getMin() {
        return stack2.peek();
    }
}

到此這篇關(guān)于Java 棧與隊(duì)列實(shí)戰(zhàn)真題訓(xùn)練的文章就介紹到這了,更多相關(guān)Java 棧與隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: