欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?棧與隊列實戰(zhàn)真題訓(xùn)練

 更新時間:2022年04月02日 08:48:06   作者:Pretend..  
在編寫程序的時候,對于棧與隊列的應(yīng)用需要熟練的掌握,這樣才能夠確保寫出來的代碼有質(zhì)量。本文小編就以幾個題目詳細(xì)說說Java中的棧與隊列,需要的朋友可以參考一下

1、實現(xiàn)循環(huán)隊列

【OJ鏈接】

循環(huán)隊列一般通過數(shù)組實現(xiàn)。我們需要解決幾個問題。

(1)數(shù)組下標(biāo)實現(xiàn)循環(huán)

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

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

(2)區(qū)分隊列的滿與空

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

 【代碼如下】

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] array;
 
    //構(gòu)造方法
    public MyCircularQueue(int k) {
       //因為預(yù)留位置的緣故,數(shù)組的大小要定義為k+1
       this.array=new int[k+1];
    }
    //入隊
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.array[this.rear]=value;
        this.rear=(this.rear+1)%this.array.length;
        return true;
    }
    //出隊
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.array.length;
        return true;
    }
    //獲取隊頭
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.array[front];
    }
    //獲取隊尾
    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;
    }
    //判斷隊列是否滿
    public boolean isFull() {
        if((this.rear+1)%this.array.length==this.front){
            return true;
        }
        return false;
    }
}

2、隊列實現(xiàn)棧

【OJ鏈接】

因為棧的先進后出、隊列的先進先出原則。我們需要兩個隊列來實現(xiàn)棧。當(dāng)兩個隊列都為空時,棧為空。

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

【代碼如下】

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、棧實現(xiàn)隊列

【OJ鏈接】

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

  • 入隊(push):規(guī)定stack1用來入隊。每次入隊時,對stack1進行入棧操作即可。
  • 出隊(pop):規(guī)定stack2進行出隊操作。如果隊列為空時,不能進行出隊操作。當(dāng)stack2為空時,我們需要將stack1中所有元素出棧,放入stack2中,然后對stack2進行出棧操作。如果stack2不為空,則直接對stack2進行出棧操作即可。
  • 獲取隊列開頭元素(peek):和出棧操作相同,最后只需要獲取stack2的棧頂元素即可。

【代碼如下】

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //構(gòu)造方法
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入隊操作
    public void push(int x) {
        stack1.push(x);
    }
    //出隊操作
    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();
 
    }
    //獲取隊列開頭的元素
    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();
    }
    //判斷隊列是否為空
    public boolean empty() {
        if(stack1.empty()&&stack2.empty()){
            return true;
        }
        return false;
    }
}

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

【OJ鏈接】

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

兩個棧stack1、stack2,站的操作都在stack1中:

  • 入棧:如果第一次入棧,我們需要將其也放入stack2中,之后的入棧,將入棧元素與stack2的棧頂元素進行比較,如果其小于stack2的棧頂元素,則將其放入stack2中。
  • 出棧:對stack1出棧時,將其與stack2的棧頂元素進行比較,如果其等于stack2的棧頂元素,則對stack2進行出棧操作。

這樣就能保證stack2的棧頂元素總是stack1的最小元素。注意:如果stack1中入棧兩個相同的最小元素,都需要對stack2進行入棧。

【代碼如下】

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 棧與隊列實戰(zhàn)真題訓(xùn)練的文章就介紹到這了,更多相關(guān)Java 棧與隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • SpringBoot多表聯(lián)查(測試可用)

    SpringBoot多表聯(lián)查(測試可用)

    這篇文章主要介紹了SpringBoot多表聯(lián)查(測試可用)的相關(guān)資料,需要的朋友可以參考下
    2017-09-09
  • Java的繪圖模式使用淺析

    Java的繪圖模式使用淺析

    這篇文章主要介紹了Java的繪圖模式使用淺析,以一個小例子大概列舉了XOR模式下能干的一些事情,需要的朋友可以參考下
    2015-10-10
  • java開發(fā)環(huán)境的完整搭建過程

    java開發(fā)環(huán)境的完整搭建過程

    這篇文章主要給大家介紹了關(guān)于java開發(fā)環(huán)境的完整搭建過程,文中介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-02-02
  • SpringMVC中解決@ResponseBody注解返回中文亂碼問題

    SpringMVC中解決@ResponseBody注解返回中文亂碼問題

    這篇文章主要介紹了SpringMVC中解決@ResponseBody注解返回中文亂碼問題, 小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-04-04
  • Java后臺如何處理日期參數(shù)格式

    Java后臺如何處理日期參數(shù)格式

    這篇文章主要介紹了Java后臺如何處理日期參數(shù)格式問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-07-07
  • Java下利用Jackson進行JSON解析和序列化示例

    Java下利用Jackson進行JSON解析和序列化示例

    本篇文章主要介紹了Java下利用Jackson進行JSON解析和序列化示例,具有一定的參考價值,感興趣的小伙伴們可以參考一下。
    2017-02-02
  • 在java中 利用匿名內(nèi)部類進行較簡潔的雙括弧初始化的方法

    在java中 利用匿名內(nèi)部類進行較簡潔的雙括弧初始化的方法

    本篇文章小編將為大家介紹,關(guān)于在java中 利用匿名內(nèi)部類進行較簡潔的雙括弧初始化的方法,有需要的朋友可以參考一下
    2013-04-04
  • java 泛型的詳解及實例

    java 泛型的詳解及實例

    這篇文章主要介紹了java 泛型的詳解及實例的相關(guān)資料,希望通過本文大家能徹底掌握泛型的使用方法,需要的朋友可以參考下
    2017-08-08
  • java?獲取子串速率比較分析

    java?獲取子串速率比較分析

    這篇文章主要為大家介紹了java?獲取子串速率比較分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-12-12
  • 在idea環(huán)境下構(gòu)建springCloud項目

    在idea環(huán)境下構(gòu)建springCloud項目

    本篇文章主要介紹了在idea環(huán)境下構(gòu)建springCloud項目,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-11-11

最新評論