자료구조 중에서도 가장 간단한 구조에 해당하는 Stack과 Queue에 대해 Javascript의 문법을 예시로 알아보자.
Stack
은 수십권의 책을 쌓아놓은 형태를 생각해보면 쉽게 이해할 수 있다. 우리는 그중에서 어떤 책을 읽으려할 때, 그 형태를 망가트리지 않으면서 가장 밑에서(가장 처음 쌓은 책) 혹은 중간에서 책을 꺼내는 것이 불가능하다. 무조건 젤 위에 쌓여있는 책, 즉 가장 마지막에 쌓은 책부터 꺼내 읽어야 하게 된다. Stack
은 이러한 원리를 따르는 자료구조로 무조건 Stack에 쌓인 제일 마지막에 쌓인 요소부터 동작해야 한다.
즉, Last In First Out 가장 마지막에 쌓인 요소가 먼저 나오게 되는 원리로 undo나 redo와 같은 동작을 구현할 때 사용된다.
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
도 같은 원리로 가장 먼저 쌓인 데이터를 먼저 이용한다.
즉, First In First Out을 따르는 자료 구조이다.
데이터를 넣는 것을 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
queue의 속성이 원래 storage의 개수가 줄어들어도 tail은 수가 감소하지 않는건가요??
dequeue할때 delete this.storage[this.head]로 하면서 storage에 개수가 하나 줄어드니깐 this.tail--도 같이 해줘야 하는게 아닌가 싶어서요