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의 뒷면을 사용하겠습니다.

참조
k보다 작거나 같은 모든 요소를 ​​결합하는 데 필요한 최소 스왑

대기열에 넣기 (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