Deque를 사용하여 스택 및 대기열 구현


난이도 쉽게
자주 묻는 질문 광신자 GE 헬스 케어 MAQ 미트라 퀄컴
대기열에서 빼기 스택

문제 정책

“Deque를 사용하여 Stack 및 Queue 구현”문제는 Deque (Dubly Ended Queue)를 사용하여 Stack 및 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 데크(Dubly Ended Queue)는 양쪽 끝에서 삽입 및 삭제를 수행 할 수있는 특수한 유형의 대기열입니다. Deque의이 흥미로운 속성은 스택이나 큐를 구현하는 데 사용할 수 있습니다.
아래 이미지는 Deque를 보여줍니다.

Deque를 사용하여 스택 및 대기열 구현

스택

스택 LIFO (Last In First Out) 데이터 구조입니다. 즉, 요소가 푸시되는 동일한 쪽에서 튀어 나옵니다. Deque의 전면을 사용하여 스택에 대한 푸시 및 팝 작업을 수행하겠습니다.

푸시 (x)

요소 x를 스택에 푸시하려면 Deque 앞에 요소 x를 추가하기 만하면됩니다.

시간 복잡성 = O (1)

팝()

Pop 작업은 Push와 같은 쪽에서 발생합니다. 즉, 스택에서 요소를 팝하려면 deque의 전면에있는 요소를 삭제하고 반환합니다.

시간 복잡성 = O (1)

비었다()

Deque가 비어 있으면 스택이 비어 있고 그렇지 않으면 그렇지 않습니다. 따라서 isEmpty of Deque를 반환하십시오.

시간 복잡성 = O (1)

크기()

스택의 크기는 Deque의 크기와 동일하므로 deque의 크기를 반환합니다.

시간 복잡성 = O (1)

암호

deque를 사용하여 스택을 구현하는 JAVA 코드
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
deque를 사용하여 스택을 구현하는 C ++ 코드
#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)

비었다()

그리고, 변발 Deque가 비어 있으면 비어 있습니다. 그렇지 않으면 비어 있습니다. 따라서 isEmpty of Deque를 반환하십시오.

시간 복잡성 = O (1)

크기()

대기열의 크기는 Deque의 크기와 동일하므로 deque의 크기를 반환합니다.

시간 복잡성 = O (1)

암호

deque를 사용하여 큐를 구현하는 JAVA 코드
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를 사용하여 큐를 구현하는 C ++ 코드
#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