[Data Structure] Stack, Queue - in JS

나연·2020년 5월 1일
2

Programming Foundation

목록 보기
2/7
post-thumbnail

자료구조 중에서도 가장 간단한 구조에 해당하는 Stack과 Queue에 대해 Javascript의 문법을 예시로 알아보자.

🧱Stack

Stack은 수십권의 책을 쌓아놓은 형태를 생각해보면 쉽게 이해할 수 있다. 우리는 그중에서 어떤 책을 읽으려할 때, 그 형태를 망가트리지 않으면서 가장 밑에서(가장 처음 쌓은 책) 혹은 중간에서 책을 꺼내는 것이 불가능하다. 무조건 젤 위에 쌓여있는 책, 즉 가장 마지막에 쌓은 책부터 꺼내 읽어야 하게 된다. Stack은 이러한 원리를 따르는 자료구조로 무조건 Stack에 쌓인 제일 마지막에 쌓인 요소부터 동작해야 한다.

즉, Last In First Out 가장 마지막에 쌓인 요소가 먼저 나오게 되는 원리로 undo나 redo와 같은 동작을 구현할 때 사용된다.

method

Stack의 메서드는 push, pop, peek 이 있다. JS의 array로 생각해봤을 때, push는 순서대로 데이터를 넣어주고 pop은 제일 마지막 데이터를 꺼내고 제거 peek은 stack에 쌓인 데이터 의 제일 마지막 데이터를 보여주기'만'하는 동작이다.

밑의 예시를 통해 자바스크립트의 array 개념으로 이해해보자.

const stack = []

//push
stack.push('dog')
stack.push('cat')
stack.push('bear')
stack // ['dog','cat','bear']

//pop -젤 마지막 요소를 꺼냄
stack.pop() //'bear'
stack // ['dog','cat']

//peek -stack에 쌓인 제일 마지막 요소를 보여주기만
stack[stack.length-1] //'cat'

밑의 예시를 통해 Object 개념으로 이해해보자.

//STACK 

class Stack {
  constructor() {
    this.storage = {}
    this.size = 0
  }
  push(element) {
    this.size++ 
    this.storage[this.size] = element 
  }

  pop() {
    let removed = this.storage[this.size]
    delete this.storage[this.size]
    this.size--
    return removed
  }

  peek() {
    return this.storage[this.size]
  }
}

const stack = new Stack()
stack.push('dog')
stack.push('cat')
stack.push('bear')
//Stack { storage : { '1' : 'dog', '2' : 'cat', '3' : 'bear' }, size : 3 }

stack.pop() //'bear'
stack // Stack { storage : { '1' : 'dog', '2' : 'cat'  }, size : 2 }

stack.peek() //'cat'

⏳Queue

Queue는 영화관에서 매표소에 줄 서있는 모습을 생각해보면 쉽게 이해할 수 있다. 가장 먼저 줄을 선 사람이 먼저 표를 구매할 수 있다. Queue도 같은 원리로 가장 먼저 쌓인 데이터를 먼저 이용한다.

즉, First In First Out을 따르는 자료 구조이다.

method

데이터를 넣는 것을 enqueue 라고 하며 앞에서부터 데이터를 꺼내는 과정을 dequeue라고 한다.

밑의 JS의 array 예시를 통해 이해해보자.

const queue = [] 

//enqueue - 순서대로 넣고 
queue.push('seahorse')
queue.push('dolphin')
queue.push('whale shark')
queue // ['seahorse','dolphin','whale shark']

//dequeue - 첫번째부터 꺼냄
queue.shift() //'seahorse'
queue // ['dolphin','whale']

밑의 JS의 Object 예시를 통해 이해해보자.

//QUEUE

class Queue {
  constructor() {
    this.storage = {}
    this.head= 0
    this.tail = 0
  }
  enqueue(element) { 
    this.storage[this.tail] = element 
    this.tail++
  }

  dequeue() {
    let removed = this.storage[this.head]
    delete this.storage[this.head]
    this.head++
    return removed
  }
}

const queue = new Queue()

queue.enqueue('seahorse')
queue.enqueue('dolphin')
queue.enqueue('whale shark')
queue // Queue { storage: { '0' : 'seahorse' , '1' : 'dolphin', '2' : 'whale shark' }, head: 0, tail: 3 }

queue.dequeue() //'seahorse'
queue // Queue { storage: { '1' : 'dolphin', '2' : 'whale shark' }, head: 1, tail: 3 }

참고 출처
Youtube | 채널명: beiatrix

profile
아름다운 상상을 실현하는 개발자입니다🌈🤍

1개의 댓글

comment-user-thumbnail
2021년 8월 26일

queue의 속성이 원래 storage의 개수가 줄어들어도 tail은 수가 감소하지 않는건가요??
dequeue할때 delete this.storage[this.head]로 하면서 storage에 개수가 하나 줄어드니깐 this.tail--도 같이 해줘야 하는게 아닌가 싶어서요

답글 달기