[leetCode/JS] 232. Implement Queue using Stacks

난이도 [ 😊 ] Easy

문제 설명

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

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.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

스택 2개를 이용해서 선입선출을 하는 queue를 만들기이다.
언어에 따라서 스택이라는 표준 오퍼레이션이 있지만.. js엔 없다.

 

입출력 예

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

 

Constraints

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

 

---

 

내 솔루션

• 문제를 무시하고 js에서 그냥 queue를 만들면 이렇게 된다.
• 이런걸 원한건 아니겠지..

class MyQueue {
  constructor() {
    this.queue = [];
  }
  push(n) {
    if(!n) return;
    this.queue.push(n);
  }
  pop() {
    return this.queue.shift();
  }
  peek() {
    return this.queue[0];
  }
  empty() {
    return this.queue.length === 0;
  }
}

 

• 진짜로 stack 2개를 이용한 선입선출 방식.
• push로 순서를 잘 만들면 나머진 쉽다.

class MyQueue {
  constructor() {
    this.stack = [];
    this.temp = [];
  }
  push(n) {
    while (this.stack.length > 0) { // 메인 스택 데이터를 temp 스택으로 옮김.
      this.temp.push(this.stack.pop());
    }
    this.temp.push(n); // temp의 마지막에 n을 넣음.
    while (this.temp.length > 0) { // temp를 역순으로 stack에 넣음.
      this.stack.push(this.temp.pop());
    }
  }
  pop() {
    return this.stack.pop();
  }
  peek() {
    return this.stack[this.stack.length-1];
  }
  empty() {
    return this.stack.length === 0;
  }
}
const st = new MyQueue();
st.push(1);
st.push(2);
st.push(3);

// stack : [3, 2, 1], temp: []

 

감상평

• 다른 언어에선 stack 이라는 데이터형이 존재하나보다.
• 근데 JS에선 이럴 이유가 1도 없어서 정~~말 하고 싶지 않았던 문제.