자료구조 중 스택과 큐를 다루어 보겠습니다.
우선 스택부터 설명해 볼게요.
블록을 아래에서 부터 위로 쌓아 올리는 구조를 가지고 있습니다. 가장 마지막에 삽입한 데이터를 가장 먼저 사용하게 됩니다.
이러한 자료구조의 특성을 LIFO(Last-in, First-out)라고 합니다.
(1) 삽입 (Push) : Push는 스택의 구조상 최상 위에 데이터가 저장 됩니다.
(2) 삭제 (Pop) : Push와 반대로 데이터를 삭제하는 것을 Pop이라 합니다. Pop도 Push와 마찬가지로 최상위 데이터 위치에서 삭제가 됩니다.
(3) 읽기 (Peek) : 마지막 위치(top)에 해당하는 데이터를 읽습니다. 이 때, top의 변화는 없습니다.
class Stack {
constructor() {
this.arr = [];
}
push(item) {
this.arr.push(item);
}
pop() {
return this.arr.pop();
}
peek() {
return this.arr[this.arr.length - 1];
}
}
const stack = new Stack();
삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가집니다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.
큐는 스택보다 일상에서 더 이해하기 쉬운 개념인데요. 가장 앞에 줄을 선 사람이 먼저 서비스를 받게 되는 것이라 생각하면 이해하기 쉽습니다.
이러한 자료구조의 특성을 FIFO(First-in, First-out)라고 합니다.
(1) Enqueue : 큐 맨 뒤에 데이터 추가
(2) Dequeue : 큐 맨 앞쪽의 데이터 삭제
class Queue {
constructor() {
this.arr = [];
}
enqueue(item) {
this.arr.push(item);
}
dequeue() {
return this.arr.shift();
}
}
const queue = new Queue();
참고
https://helloworldjavascript.net/pages/282-data-structures.html