큐를 사용하여 스택 구현

난이도 쉽게
자주 묻는 질문 페이팔
디자인 스택조회수 41

다음 기능을 구현하십시오. 스택 표준 작업을 사용하는 데이터 구조 변발,

  1. push (x) –> 요소 x를 스택으로 푸시
  2. pop () –> 스택 맨 위에있는 요소를 제거합니다.
  3. top () –> 스택 맨 위에있는 요소를 반환합니다.
  4. empty () –> 스택이 비어 있는지 여부를 반환합니다.

입력:
stack.push (1);
stack.push (2);
stack.top (); // 2를 반환합니다.
stack.pop (); // 2를 반환합니다.
stack.empty (); // false 반환
출력:
2
2
그릇된

큐를 사용하여 스택을 구현하는 알고리즘

2 개의 큐 (예 : q1 및 q2)를 사용하여 스택을 구현할 수 있습니다.

푸시 (x)

q1의 끝에서 x를 누르고 최상위 변수에서 스택의 맨 위에 유지합니다.
의사 코드

void push(int x) {
    q1.add(x);
    top = x;
}

시간 복잡성 = O (1)

상단()

스택의 맨 위는 항상 맨 위 변수에 유지되므로 맨 위를 반환하면됩니다.
의사 코드

int top() {
    return top;
}

시간 복잡성 = O (1)

빈()

큐 q1이 비어 있으면 스택이 비어 있습니다.
의사 코드

boolean empty() {
    return q1.isEmpty();
}

시간 복잡성 = O (1)

팝()

큐 q1의 뒤쪽에는 스택의 맨 위가 포함되어 있으므로 q1의 크기를 n으로 둡니다.

  1. 큐 q1의 (n – 1) 요소를 큐 q2로 이동합니다.
  2. 또한 전송중인 현재 변수로 스택의 맨 위를 유지하십시오.
  3. 이제 q1에는 스택의 맨 위에있는 요소가 하나만 포함됩니다.
  4. 이 요소를 제거하고 일부 변수 (예 : ele)에 저장하십시오.
  5. 모든 요소를 ​​큐 q2에서 큐 q1로 이동합니다.
  6. ele를 반환합니다.

시간 복잡성 = O (N) 
여기서 n은 큐의 요소 수입니다.

예를 들어,
q1 = 3-> 5-> 7-> 1-> 2
q2 = 널

요소를 튀어 나오십시오.

  1. q1에서 q1로 이전 (n – 2)
    q1 = 2 및 q2 = 3-> 5-> 7-> 1
  2. q1에서 요소를 제거하고 저장하십시오.
    q1 = null 및 q2 = 3-> 5-> 7-> 1 및 ele = 2
  3. 모든 요소를 ​​q2에서 q1로 이동합니다.
    q1 = 3-> 5-> 7-> 1 및 q2 = null
  4. ele를 반환합니다.

자세한 내용은 아래 이미지를 참조하십시오.

큐를 사용하여 스택 구현

의사 코드

int pop() {
    int n = q1.size();
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.remove();
        q2.add(curr);
        top = curr;
    }
    int ele = q1.remove();
    n = q2.size();
    for (int i = 0; i < n; i++) {
        q1.add(q2.remove());
    }
    return ele;
}

시간 복잡성 = O (N)

큐를 사용하여 스택을 구현하기위한 JAVA 코드

import java.util.Queue; 
import java.util.LinkedList;
public class StackUsingQueues {
    // Two queues to implement stack
    private static Queue<Integer> q1 = new LinkedList<>();
    private static Queue<Integer> q2 = new LinkedList<>();
    // Stores the top element of stack
    private static int top;

    private static void push(int x) {
        // Add element at rear of q1
        q1.add(x);
        // update top as current element
        top = x;
    }

    private static int top() {
        // Top stores the top of stack
        return top;
    }

    private static int pop() {
        int n = q1.size();
        // Shift (n - 1) elements from q1 to q2 and update top as curr
        // element transferred
        for (int i = 0; i < n - 1; i++) {
            int curr = q1.remove();
            q2.add(curr);
            top = curr;
        }
        // q1 contains only 1 element which is top of stack
        // store the element in ele and remove it from q1
        int ele = q1.remove();
        n = q2.size();
        // Again transfer back the elements from q2 to q1
        for (int i = 0; i < n; i++) {
            q1.add(q2.remove());
        }
        // return ele, this is the top of stack
        return ele;
    }
    
    private static boolean empty() {
        // If q1 is empty then stack is empty
        return q1.isEmpty();
    }
    
    public static void main(String[] args) {
        // Example
        push(1);
        push(2);
        System.out.println(top());
        System.out.println(pop());
        System.out.println(empty());
    }
}

큐를 사용하여 스택을 구현하기위한 C ++ 코드

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

// Two queues to implement stack
queue<int> q1;
queue<int> q2;
// Stores the top element of stack
int Top;

void push(int x) {
    // Add element at rear of q1
    q1.push(x);
    // update top as current element
    Top = x;
}

int top() {
    // Top stores the top of stack
    return Top;
}

bool empty() {
    // If q1 is empty then stack is empty
    return q1.empty();
}

int pop() {
    int n = q1.size();
    // Shift (n - 1) elements from q1 to q2 and update top as curr
    // element transferred
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.front();
        q1.pop();
        q2.push(curr);
        Top = curr;
    }
    // q1 contains only 1 element which is top of stack
    // store the element in ele and remove it from q1
    int ele = q1.front();
    q1.pop();
    n = q2.size();
    // Again transfer back the elements from q2 to q1
    for (int i = 0; i < n; i++) {
        q1.push(q2.front());
        q2.pop();
    }
    // return ele, this is the top of stack
    return ele;
}

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

레퍼런스 1    참조 2

Translate »