.Zzumbong

[leetCode/JS] 232. Implement Queue using Stacks 본문

coding test/leetCode

[leetCode/JS] 232. Implement Queue using Stacks

쭘봉 2022. 12. 16. 11:23

난이도 [ 😊 ] 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도 없어서 정~~말 하고 싶지 않았던 문제.
Comments