ES6 자료구조 스택(Stack)만들어보기, 스택 2개로 큐(Queue) 만드는 방법

ES6 Stack 만들기

스택(Stack)은 리스트구조에서 한쪽 방향에서만 입력, 출력이 되는 구조다.

LIFO(Last in First Out)으로 가장 나중에 넣은 자료가 가장 처음 나오는 자료 구조로 프로그래밍중에 종종 사용된다.

자료구조에 대한 이해는 어느정도 되어있다고 가정하고 javascript에서 구현을 해본다.

class Stack{
  constructor(){
    this.top = -1;
    this.dataStore = [];
  }
  push(element){
    this.top++;
    this.dataStore[this.top] = element;
  }
  pop(){
    if(this.top>-1){
      let val = this.dataStore[this.top];
      this.top--;
      return val;
    }
    return null;
  }
  peek(){
    return this.dataStore[this.top];
  }
  get length(){
    return this.top+1;
  }
  clear(){
    this.top = 0;
    this.dataStore = [];
  }
}
const stack = new Stack();
stack.push("jeong");
stack.push("pro");
stack.push("blog");
console.log(stack.peek());//blog , top = 2;
console.log(stack.pop());//blog , top = 1;
console.log(stack.pop());//pro , top = 0;
console.log(stack.pop());//jeong , top = -1;
console.log(stack.pop());//null, top = -1;

스택의 top을 -1로 초기화하는 방법도 있고 0으로 초기화하는 방법도 있고 다양하다. 여기서는 -1로 초기화하는 코드를 작성했다.

test코드를 설명하면 peek()은 스택에서 자료를 꺼내지않고 top이 가리키는 값을 보여주기 때문에 top이 변경되지 않는다.

pop()은 자료를 꺼내고 top을 -1하기 때문에 입력과 반대순서로 출력이 된다. 그리고 스택이 비어있는데도 꺼내려고 pop()을 하면 null처리를 하였기 때문에 null이 출력된다.

---

Stack을 이용해서 팩토리얼(factorial) 만들어보기

Stack을 이용하는 프로그래밍은 다양하다.

그 중에 팩토리얼(factorial)을 재귀함수를 이용하는 방법이 있지만 스택을 이용해서 만드는 방법을 해본다.

const fact = (n) => {
  //스택에 값 모두 넣기
  const stack = new Stack();
  while(n>1){
    stack.push(n);
    n--;
  }
  let value = 1;
  //팩토리얼 계산
  while(stack.length > 0){
    value *= stack.pop();
  }
  return value;
}
console.log(fact(5));//120

function factorial(n){
  if(n === 1){
    return 1;
  }
  return n * factorial(n-1);
}
console.log(factorial(5));//120

[재귀함수로 구현]

---

스택 두개로 큐(Queue)구현하기

class Stack{
  constructor(){
    this.top = -1;
    this.dataStore = [];
  }
  push(element){
    this.top++;
    this.dataStore[this.top] = element;
  }
  pop(){
    if(this.top>-1){
      let val = this.dataStore[this.top];
      this.top--;
      return val;
    }
    return null;
  }
  peek(){
    return this.dataStore[this.top];
  }
  get length(){
    return this.top+1;
  }
  clear(){
    this.top = 0;
    this.dataStore = [];
  }
}
class Queue{
  constructor(){
      this.stack1 = new Stack();
      this.stack2 = new Stack();
      this.size = 0;
    }
  push(element){
    this.stack1.push(element);
  }
  pop(){
    if(this.stack2.length === 0){
      while(this.stack1.length > 0){
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop();
    //stack1, stack2 둘다 비어있으면 null리턴
  }
  get size(){
    return this.stack1.length + this.stack2.length;
  }
}
const q = new Queue();
q.push(1);
q.push(2);
q.push(3);
q.push(4);
console.log(q.pop());//1
console.log(q.pop());//2
q.push(5);
q.push(6);
console.log(q.pop());//3
console.log(q.pop());//4
console.log(q.pop());//5
console.log(q.pop());//6

스택(Stack)을 두개를 사용해서 큐를 구현했다.

사실 큐는 enqueue(), dequeue()로 메서드명을 지정해야 더 명확한데 구현하다보니 스택의 push(), pop()을 따라갔다.....

큐(Queue)는 선입선출(FIFO:First in First out)구조를 갖는 자료구조다.

큐에 입력할 때는 하나의 스택(stack1)에 넣고 출력할 때는 다른 스택에 pop()을 통해서 원래 순서대로 넣어주는 방법으로 큐의 선입선출을 만족시키는 방법이다.

---

참고 도서 : DataStructures & Algorithms with javascript