JavaScript 자료구조 - Stack (스택)

ryu·2020년 3월 26일
0

Stack

Stack 주요 연산

  • S.top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다.
  • S.pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
  • S.push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다.
  • S.empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다.

JavaScript로 Stack 구현하기 (ES6)

  • 큐와 마찬기지로 Array 를 사용하여 Stack 을 구현할 수 있습니다.
  • Array의 push() , pop() 메소드를 사용합니다. ✨
class Stack {
  constructor() {
    this.store = [];
  }
  
  push(item) {
    this.store.push(item);
  }
  
  pop() {
    return this.store.pop();
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.pop();   // 2

Queue 2개로 Stack 구현하기

  1. Main Queue 와 Sub Queue 두개를 둔다.
  2. Main Queue 가 비었을 때는 item 을 바로 enqueue 하고,
    그렇지 않을 때는 Main Queue 의 요소들을 Sub Queue 로 모두 옮겨서 비운 다음에 item 을 enqueue 한다. 이후 Sub 에 있는 요소들을 다시 Main 으로 옮긴다.
class Queue {
  constructor() {
    this.store = [];
  }
  
  enqueue(item) {
    this.store.push(item);
  }
  
  dequeue() {
    return this.store.shift();
  }
  
  empty() {
    return (this.store.length === 0);
  }
}

class Stack {
  constructor() {
    this.main = new Queue();
    this.sub = new Queue();
  }
  
  push(item) {
    if(this.main.empty()) {
      this.main.enqueue(item);
    } else {
      while(!this.main.empty()) {
        this.sub.enqueue(this.main.dequeue());
      }
      this.main.enqueue(item);
      while(!this.sub.empty()) {
        this.main.enqueue(this.sub.dequeue());
      }
    }
  }
  
  pop() {
    this.main.dequeue();
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();
console.log(stack.main.store);   // [2, 1]

Stack 2개로 Queue 구현하기

  1. 데이터를 쌓을 스택 InStack, 데이터를 추출할 스택 OutStack 을 만듭니다.
  2. enqueue 액션이 발생하면, InStack 에 데이터를 쌓습니다.
  3. dequeue 액션이 발생하면, OutStack 에 있는 요소를 반환합니다.
    이때, OutStack 이 비어 있다면, InStack 의 요소들을 OutStack 으로 모두 옮긴 다음, OutStack 에서 하나를 추출해서 반환합니다.
class Stack {
  constructor() {
    this.store = [];
  }
  
  push(item) {
    this.store.push(item);
  }
  
  pop() {
    return this.store.pop();
  }
}

class Queue {
  constructor() {
    this.inStack = new Stack();
    this.outStack = new Stack();
  }
  
  enqueue(item) {
    this.inStack.push(item);
  }
  
  dequeue() {
    if (this.outStack.store.length === 0) {
      while(this.inStack.store.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

queue.dequeue();   // 1  
profile
안녕하세요! 되는대로 열심히 사는 개발자입니다 🙋🏻‍♀️🍪Software Engineer @Kakao, AI Platform Team 🤖#TypeScript #React #Vue #Python #CloudNative

0개의 댓글