ใช้ Stack และ Queue โดยใช้ Deque


ระดับความยาก สะดวกสบาย
ถามบ่อยใน fanatics GE Healthcare MAQ Myntra วอลคอมม์
Dequeue คิว กอง

คำชี้แจงปัญหา

ปัญหา“ Implement Stack and Queue using Deque” จะเขียนอัลกอริทึมเพื่อใช้ Stack และ Queue โดยใช้ Deque (Doubly Ended Queue)

ตัวอย่าง (กอง)

Push(1)
Push(2)
Push(3)
Pop()
isEmpty()
Pop()
Size()
3
false
2
1

ตัวอย่าง (คิว)

Enqueue(1)
Enqueue(2)
Enqueue(3)
Dequeue
isEmpty()
Size()
Dequeue()
1
false
2
2

 

ขั้นตอนวิธี

A deque(Doubly Ended Queue) เป็นคิวประเภทพิเศษที่สามารถทำการแทรกและลบได้ทั้งสองด้าน คุณสมบัติที่น่าสนใจของ Deque นี้สามารถใช้เพื่อใช้งานสแต็กหรือคิวจากมัน
ภาพด้านล่างแสดง Deque

ใช้ Stack และ Queue โดยใช้ Deque

กอง

กอง เป็นโครงสร้างข้อมูล Last In First Out (LIFO) กล่าวคือองค์ประกอบจะโผล่ออกมาจากด้านเดียวกับที่ถูกผลัก ให้เราใช้ด้านหน้าของ Deque เพื่อดำเนินการ push และ pop สำหรับ stack

กด (x)

ในการดันองค์ประกอบ x ไปที่สแต็กเพียงแค่เพิ่มองค์ประกอบ x ที่ด้านหน้าของ Deque

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

ป๊อป ()

การดำเนินการป๊อปเกิดขึ้นที่ด้านเดียวกับของ Push นั่นคือการป๊อปองค์ประกอบจากสแต็กให้ลบองค์ประกอบที่อยู่ด้านหน้า deque และส่งคืน

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

มันว่างเปล่า()

หาก Deque ว่างเปล่าสแต็กจะว่างเปล่าก็จะไม่ใช่ ดังนั้นคืนค่า isEmpty ของ Deque

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

ขนาด()

ขนาดของสแต็กเท่ากับขนาดของ Deque ดังนั้นให้กลับขนาดของ deque

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

รหัส

JAVA Code เพื่อใช้ stack โดยใช้ deque
import java.util.Deque;
import java.util.LinkedList;
class StackUsingDeque {
    // deque used to implement stack
    private static Deque<Integer> deque;

    private static void push(int x) {
        // Add the element x to the front of Deque
        deque.addFirst(x);
    }

    private static int pop() {
        // if deque is not empty remove an element from the front of deque
        if (!deque.isEmpty()) {
            return deque.removeFirst();
        }
        return -1;
    }

    private static boolean isEmpty() {
        // stack is empty if deque is empty
        return deque.isEmpty();
    }

    private static int size() {
        // size of stack is same as size of Deque
        return deque.size();
    }

    public static void main(String[] args) {
        deque = new LinkedList<>();

        // Example
        push(1);
        push(2);
        push(3);
        System.out.println(pop());
        System.out.println(isEmpty());
        System.out.println(pop());
        System.out.println(size());
    }
}
3
false
2
1
รหัส C ++ เพื่อใช้สแต็กโดยใช้ deque
#include <bits/stdc++.h>
using namespace std;

// deque used to implement stack
deque<int> dq;

void push(int x) {
    // Add the element x to the front of Deque
    dq.push_front(x);
}

int pop() {
    // if deque is not empty remove an element from the front of deque
    if (!dq.empty()) {
        int top = dq.front();
        dq.pop_front();
        return top;
    }
    return -1;
}

int size() {
    // size of stack is same as size of Deque
    return dq.size();
}

bool isEmpty() {
    // stack is empty if deque is empty
    return dq.empty();
}

int main() {
    // Example
    push(1);
    push(2);
    push(3);
    cout<<pop()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    cout<<pop()<<endl;
    cout<<size()<<endl;
    
    return 0;
}
3
false
2
1

คิว

คิวคือโครงสร้างข้อมูลเข้าก่อนออกก่อน (FIFO) ซึ่งการดำเนินการจัดคิวและการจัดคิวจะดำเนินการในด้านตรงข้ามกัน ให้เราใช้ด้านหน้าของ Deque สำหรับการดำเนินการจัดคิวและด้านหลังของ Deque สำหรับการดำเนินการจัดคิว

จัดคิว (x)

ในการจัดลำดับองค์ประกอบ x ในคิวให้เพิ่มองค์ประกอบที่ด้านหน้าของ Deque

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

Dequeue ()

ในการยกเลิกการจัดคิวองค์ประกอบจากคิวให้ลบองค์ประกอบที่อยู่ด้านหลังของ Deque และส่งคืน

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

มันว่างเปล่า()

แพทเทิร์น คิว ว่างเปล่าถ้า Deque ว่างเปล่าไม่งั้นก็ไม่ใช่ ดังนั้นคืนค่า isEmpty ของ Deque

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

ขนาด()

ขนาดของคิวจะเท่ากับขนาดของ Deque ดังนั้นให้ส่งคืนขนาดของ deque

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

รหัส

JAVA Code เพื่อใช้งานคิวโดยใช้ deque
import java.util.Deque;
import java.util.LinkedList;
class QueueUsingDeque {
    // deque used to implement queue
    private static Deque<Integer> deque;

    private static void enqueue(int x) {
        // add the element x at the front of deque
        deque.addFirst(x);
    }

    private static int dequeue() {
        // if deque is not empty remove and return the rear of deque
        if (!deque.isEmpty()) {
            return deque.removeLast();
        }
        return -1;
    }

    private static boolean isEmpty() {
        // queue is empty if deque is empty
        return deque.isEmpty();
    }

    private static int size() {
        // size of queue is same as size of deque
        return deque.size();
    }

    public static void main(String[] args) {
        deque = new LinkedList<>();

        // Example
        enqueue(1);
        enqueue(2);
        enqueue(3);
        System.out.println(dequeue());
        System.out.println(isEmpty());
        System.out.println(size());
        System.out.println(dequeue());
    }
}
1
false
2
2
รหัส C ++ เพื่อใช้งานคิวโดยใช้ deque
#include <bits/stdc++.h>
using namespace std;

// deque used to implement queue
deque<int> dq;

void enqueue(int x) {
    // add the element x at the front of deque
    dq.push_front(x);
}

int dequeue() {
    // if deque is not empty remove and return the rear of deque
    if (!dq.empty()) {
        int front = dq.back();
        dq.pop_back();
        return front;
    }
    return -1;
}

int size() {
    // size of queue is same as size of deque
    return dq.size();
}

bool isEmpty() {
    // queue is empty if deque is empty
    return dq.empty();
}

int main() {
    // Example
    enqueue(1);
    enqueue(2);
    enqueue(3);
    cout<<dequeue()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    cout<<size()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
1
false
2
2