Bagaimana untuk melaksanakan timbunan dan baris gilir Java-javaTutorial-php.cn

1. Laksanakan baris gilir pekeliling

[pautan OJ]

Baris gilir pekeliling biasanya dilaksanakan melalui tatasusunan. Kita perlu menyelesaikan beberapa masalah.

(1) Gelung pelaksanaan subskrip tatasusunan

a. Secara lebih ringkas, jika saiz tatasusunan kami ialah 8, dan subskrip mencapai 7, bagaimana untuk kembali kepada 0 kemudian, kami boleh mencapainya dengan (indeks+1)%8.

Bagaimana untuk melaksanakan timbunan dan baris gilir Java

b. Apabila subskrip adalah yang pertama dan kemudian ke hadapan, kami membuat pertimbangan khas dan menetapkannya kepada saiz tatasusunan tolak satu.

(2) Bezakan antara baris gilir penuh dan kosong

Kita boleh menempah kedudukan untuk tatasusunan Jika belakang+1=depan, bermakna barisan penuh; bermakna barisan sudah penuh. Dalam kes ini, kita perlu mempertimbangkan saiz barisan Apabila menentukan saiz tatasusunan, ia perlu lebih besar daripada saiz asal.

Bagaimana untuk melaksanakan timbunan dan baris gilir Java

[Kod adalah seperti berikut]

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] array;
 
    //构造方法
    public MyCircularQueue(int k) {
       //因为预留位置的缘故，数组的大小要定义为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;
    }
}

Salin selepas log masuk

2. Timbunan pelaksanaan baris gilir

[Pautan OJ]

Kerana Prinsip pertama-masuk-akhir-keluar tindanan dan prinsip pertama-masuk-keluar-dahulu bagi baris gilir. Kami memerlukan dua baris gilir untuk melaksanakan timbunan. Apabila kedua-dua baris gilir kosong, timbunan itu kosong.

Tekan: Tidak kira kali pertama anda menolak ke dalam tindanan Anda boleh memilih mana-mana baris gilir apabila anda menolak ke dalam tindanan nanti , pasti akan ada baris gilir tidak kosong Cari baris gilir yang tidak kosong dan lakukan operasi enqueue.
Pop: Pertama, apabila tindanan kosong, operasi pop tidak boleh dilakukan apabila tindanan tidak kosong, mesti ada satu baris gilir yang kosong (baris gilir1), dan satu baris gilir yang tidak Kosong (baris gilir2), pop saiz-1 elemen dalam baris gilir1 ke baris gilir2 (beri perhatian khusus untuk tidak meletakkan fungsi untuk mencari saiz baris gilir1 ke dalam gelung. Apabila baris gilir dinyah gilir, saiznya berubah), dan akhirnya Elemen terakhir dalam baris gilir1 ditapis dan merupakan nilai pulangan.
Mendapatkan elemen atas timbunan (atas): Ia hampir sama dengan melonjakkan timbunan, jadi saya tidak akan pergi ke butiran

[Kod adalah seperti berikut]

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
 
    //构造方法
    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;
    }
}

Salin selepas log masuk

3. Baris gilir pelaksanaan tindanan

[pautan OJ]

Masih sama seperti di atas, dua tindanan (tindanan1, stack2) diperlukan. Berbeza daripada pelaksanaan gilir tindanan, enqueueing hanya boleh beroperasi pada tindanan yang sama. Jika kedua-dua tindanan kosong, baris gilir kosong.

Masukkan pasukan (tolak): Ia dinyatakan bahawa stack1 digunakan untuk menyertai pasukan. Setiap kali anda menyertai baris gilir, hanya tolak stack1 ke dalam tindanan.
Dequeue (pop): Memerlukan stack2 untuk melaksanakan operasi dequeue. Jika baris gilir kosong, operasi dequeue tidak boleh dilakukan. Apabila stack2 kosong, kita perlu memasukkan semua elemen dalam stack1 ke dalam stack2, dan kemudian pop stack2. Jika stack2 tidak kosong, hanya pop stack2 terus.
Dapatkan elemen permulaan baris gilir (peek): Ia adalah sama seperti operasi pop Pada akhirnya, anda hanya perlu mendapatkan elemen atas tindanan2.

[Kod adalah seperti berikut]

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    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;
    }
}

Salin selepas log masuk

4. Laksanakan tindanan minimum

[Pautan OJ]

Sebenarnya, ia adalah untuk Cari elemen terkecil timbunan dalam kerumitan masa O(1). Dua tindanan diperlukan untuk melaksanakannya, dan satu tindanan digunakan untuk operasi pop dan tolak. Hanya pastikan bahawa tidak kira bagaimana anda beroperasi, elemen teratas tindanan yang lain ialah unsur terkecil daripada tindanan semasa.

Dua tindanan1 dan tindanan2, operasi stesen semuanya dalam tindanan1:

Menolak: Jika ia ditolak ke tindanan buat kali pertama, kita perlu untuk meletakkannya juga Dalam tindanan2, untuk menolak seterusnya, elemen yang ditolak dibandingkan dengan elemen atas tindanan2 Jika ia lebih kecil daripada elemen atas tindanan2, ia dimasukkan ke dalam tindanan2.
Pop: Apabila muncul tindanan1, bandingkan dengan elemen atas tindanan2 Jika ia sama dengan unsur atas tindanan2, tindanan2.

Ini memastikan elemen teratas tindanan2 sentiasa elemen terkecil tindanan1. Nota: Jika dua elemen minimum yang sama ditolak ke dalam tindanan dalam tindanan1, tindanan2 perlu ditolak ke dalam tindanan.

[Kod adalah seperti berikut]

class MinStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    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();
    }
}

Salin selepas log masuk

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan timbunan dan baris gilir Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!