Впровадити стек і чергу за допомогою Deque


Рівень складності Легко
Часто запитують у Фанатики GE Healthcare MAQ Мінтра компанія Qualcomm
Зняти чергу Чергу Стек

Постановка проблеми

Проблема “Впровадження стека та черги за допомогою Deque” передбачає написання алгоритму реалізації стека та черги за допомогою Deque (подвійно закінчена черга).

Приклад (стек)

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 можна використовувати для реалізації або стека, або черги з нього.
На зображенні нижче зображено Deque,

Впровадити стек і чергу за допомогою Deque

Стек

Стек є структурою даних Last In First Out (LIFO), тобто елементи вискакують з тієї самої сторони, куди їх штовхають. Давайте використаємо передню частину Deque для виконання натискання та поп-операції для стека.

Натискання (x)

Щоб підсунути елемент x до стека, просто додайте елемент x спереду Deque.

Складність часу = O (1)

Поп ()

Поп-операція відбувається на тій же стороні, що і Push, тобто, щоб вискочити елемент зі стека, видалити елемент, присутній на передній панелі deque, і повернути його.

Складність часу = O (1)

пусто()

Якщо Deque порожній, стек порожній, інакше це не так. Тож поверніть isEmpty of Deque.

Складність часу = O (1)

розмір ()

Розмір стека такий же, як розмір Deque, тому поверніть розмір deque.

Складність часу = O (1)

код

Код JAVA для реалізації стека з використанням 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)

Зняти чергу ()

Щоб зняти елемент із черги, видаліть елемент із задньої сторони Deque і поверніть його.

Складність часу = O (1)

пусто()

повне г, повне г,, показали, від, номер, XNUMX чергу є порожнім, якщо Deque порожній, інакше ні. Тож поверніть isEmpty of Deque.

Складність часу = O (1)

розмір ()

Розмір черги такий же, як розмір Deque, тому поверніть розмір deque.

Складність часу = O (1)

код

Код JAVA для реалізації черги за допомогою 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
Код С ++ для реалізації черги з використанням 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