จัดคิวโดยใช้ Stacks


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคโคไลท์ อะโดบี อเมซอน เดอชอว์ Flipkart แซคส์โกลด์แมน InfoEdge InMobi MakeMyTrip MAQ ไมโครซอฟท์ สแตนลี่ย์มอร์แกน คำพยากรณ์ Walmart Labs
คิว กอง

ต่อคิวโดยใช้ไฟล์ กอง ปัญหาเราต้องใช้ฟังก์ชันต่อไปนี้ของคิวโดยใช้ฟังก์ชันมาตรฐานของโครงสร้างข้อมูลสแต็ก

  1. Enqueue: เพิ่มองค์ประกอบที่ท้ายคิว
  2. Dequeue: ลบองค์ประกอบออกจากจุดเริ่มต้นของคิว

ตัวอย่าง

Input:
เอ็นคิว (5)
เอ็นคิว (11)
เอ็นคิว (39)
Dequeue () // ส่งกลับ 5
เอ็นคิว (12)
Dequeue () // ส่งกลับ 11
Dequeue () // ส่งกลับ 39
Output:
5
11
39

ขั้นตอนวิธี

คิวสามารถใช้งานได้โดยใช้สองสแต็กมีสองวิธีในการใช้คิวโดยใช้สแต็กอันดับแรกโดยการดำเนินการจัดคิวที่มีค่าใช้จ่ายสูงและอันดับที่สองโดยทำให้การดำเนินการจัดคิวมีค่าใช้จ่ายสูง

วิธีที่ 1 (การดำเนินการจัดคิวแบบเสียค่าใช้จ่าย) สำหรับการจัดคิวโดยใช้กองซ้อน

สร้างสองสแต็ก st1 และ st2 เห็นภาพไฟล์ คิว ใน st1 ด้านบนของ st1 อยู่หน้าคิวและการเลื่อนลงใน st1 จะคล้ายกับการเลื่อนไปข้างหน้าในคิว

จัดคิว (x)

การผลัก x ไปทางด้านหลังของคิวจะเหมือนกับการดัน x ไปที่ด้านล่างของสแต็ก st1

  1. ลบองค์ประกอบทั้งหมดออกจาก st1 แล้วดันไปที่ st2
  2. กด x ไปที่ st2
  3. ลบองค์ประกอบทั้งหมดออกจาก st2 แล้วดันกลับไปที่ st1

ความซับซ้อนของเวลา = บน

จัดคิวโดยใช้ Stacks

Dequeue ()

การนำองค์ประกอบออกจากด้านหน้าของคิวจะคล้ายกับการลบส่วนบนของสแต็ก st1 ดังนั้นถ้า st1 ไม่ว่างให้ป๊อปด้านบนของ st1 แล้วย้อนกลับ

ความซับซ้อนของเวลา = O (1)

ความซับซ้อนของพื้นที่โดยรวมของวิธีที่ 1 = O (n)

รหัส JAVA สำหรับคิวโดยใช้ Stacks

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Enqueue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // push x to st2
        st2.push(x);

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty return and remove the top of st1
        return st1.pop();
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();
        
        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

รหัส C ++

#include<bits/stdc++.h> 
using namespace std;

// Costly Enqueue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // push x to st2
    st2.push(x);
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty return and remove the top of st1
    int top = st1.top();
    st1.pop();
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

วิธีที่ 2 (การดำเนินการยกเลิกคิวเสียค่าใช้จ่าย) สำหรับคิวโดยใช้สแต็ค

สร้างสองสแต็ก st1 และ st2 แสดงภาพคิวใน st1 ด้านบนของ st1 แสดงถึงด้านหลังของคิวการเลื่อนขึ้นใน st1 จะคล้ายกับการเลื่อนไปข้างหน้าในคิว

จัดคิว (x)

การผลัก x ไปทางด้านหลังของคิวจะคล้ายกับการดัน x ไปที่ด้านบนสุดของ stack_st1 ดังนั้นดัน x ไปด้านบนของ st1

ความซับซ้อนของเวลา = O (1)

Dequeue ()

การนำองค์ประกอบออกจากด้านหน้าของคิวจะคล้ายกับการลบองค์ประกอบออกจากด้านล่างของ stack_st1 ดังนั้นหาก st1 ไม่ว่างเปล่า

  1. ลบองค์ประกอบทั้งหมดออกจาก st1 แล้วดันไปที่ st2
  2. เปิดด้านบนของ st2 และเก็บไว้ในตัวแปรด้านบน
  3. ลบองค์ประกอบทั้งหมดออกจาก st2 แล้วดันกลับไปที่ st1
  4. กลับด้านบน

ความซับซ้อนของเวลา = O (n)

จัดคิวโดยใช้ Stacks

ความซับซ้อนของพื้นที่โดยรวมของวิธีที่ 2 = O (n)

รหัส JAVA

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Dequeue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // push x to top of st1
        st1.push(x);
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // pop the top of st2 and store it in a variable top
        int top = st2.pop();

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
        
        // return top
        return top;
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();

        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

รหัส C ++

#include<bits/stdc++.h> 
using namespace std;

// Costly Dequeue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // push x to top of st1
    st1.push(x);
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // pop the top of st2 and store it in a variable top
    int top = st2.top();
    st2.pop();
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
    
    // return top
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

อ้างอิง 1     เอกสารอ้างอิง 2