stack, queue
자료구조 스택(stack) 큐(queue)
스택
스택은 기본적으로 LIFO(last in first out,후입선출)구조 이다. 스택에서는 마지막으로 추가된 요소가 제일 먼저 제거된다.
배열에서 push 메서드와 pop 메서드를 사용하여 스택 자료구조 만들 수 있다. 별도의 클래스로 스택 자료구조를 만들 수도 있다.
class Stack{
constructor(){
this._arr = [];
}
push(item){
this._arr.push(item);
}
pop(){
return this._arr.pop();
}
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); //3
스택 시간복잡도 Big O
- Insertion O(1)
- Deletion O(1)
- Search O(n)
큐
큐는 스택과 매우 유사하다. 하지만 순서가 다르다. 큐는 FIFO(first in first out, 선입선출) 구조다. queue라는말에 걸맞게 줄서기를 생각하면 편하다.
unshift와 pop 메서드 push shift 메서드 조합을 사용하는것이 큐의 작동방식과 같다 하지만 unshift는 성능이 좋지 못하다.
class Queue{
constructor(){
this.arr = [];
}
enqueue(item){
this.arr.push(item);
}
dequeue(){
return arr.shift();
}
}
const queue = new Queue();
stack.enqueue(1);
stack.enqueue(2);
stack.enqueue(3);
stack.dequeue() ; //1큐 시간복잡도 Big O
- Insertion O(1)
- Deletion O(1)
- Search O(n)
출처: https://helloworldjavascript.net/pages/282-data-structures.html
https://velog.io/@jangws/15.-%EC%8A%A4%ED%83%9Dstack-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-JS
