문제

Implement the following operations of a queue using stacks.

스택을 사용하여 다음 큐 작업을 구현하십시오.

push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.

Example :

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes :

You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.

스택의 표준 작업 만 사용해야합니다. 즉, push to top, peek/pop from top, size, is empty 작업은 유효합니다.

Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.

언어에 따라 스택이 기본적으로 지원되지 않을 수 있습니다. 스택의 표준 작업 만 사용하는 한 목록 또는 큐 (양말 큐)를 사용하여 스택을 시뮬레이션 할 수 있습니다.

You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

모든 작업이 유효하다고 가정 할 수 있습니다 (예 : 빈 대기열에서 팝 또는 엿보기 작업이 호출되지 않음).

기본 지식

스택(Stack)

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

큐(Queue)

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식

add(item): item을 리스트의 끝부분에 추가한다.
remove(): 리스트의 첫 번째 항목을 제거한다.
peek(): 큐에서 가장 위에 있는 항목을 반환한다.
isEmpty(): 큐가 비어 있을 때에 true를 반환한다.

풀이

이번 문제는 스택(Stack)과 큐(Queue)개념만 잘 알면 쉽게 해결할 수 있을 것 같습니다.

간단하게 설명드리자면 스택을 두 개 두어서 한 개의 스택에 있는 내용을 뒤집어서 다시 다른 스택에 두면 큐와 같아진다는 내용입니다.

다음과 같이 1,2,3 순서로 push한 stack1이 있습니다

                    top
stack 1 :   1   2   3 

이것을 다른 stack2에 역순으로 저장하면

                    top
stack 2 :   3   2   1

이것을 순서대로 pop() 하게 되면 1,2,3 순서로 큐와 같이 FIFO 구조가 되는 것입니다.

Answer :

class MyQueue {

    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();
    
    /** Initialize your data structure here. */
    public MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        in.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        return out.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
        return out.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return in.isEmpty()&&out.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상

← Previous Post Next Post →

LeetCode#232

Implement Queue using Stacks

문제

기본 지식

풀이