Intro.
스택Stack과 큐Queue는 자료구조의 일종으로, 데이터가 쌓이는 방식 혹은 구조를 뜻한다.
처리하는 데이터가 다수일 때, 어떤 순서로 쌓고 어떤 순서로 처리할 것인가를 규정한 방식이라고 생각하면 될 것 같다. 스택이 마지막에 쌓인 데이터를 먼저 처리하는 방식이라면, 큐는 먼저 쌓인 데이터를 먼저 처리한다는 차이가 있다.
1. Stack
스택이란?
stack은 채우다, 쌓다라는 뜻이다. 흔히 스택을 접시를 쌓는 것에 비유하곤 한다. 접시를 한 장씩 겹쳐 쌓은 후 한 장씩 꺼낸다고 할 때 가장 아래(가장 먼저 쌓은) 접시를 바로 꺼내지는 못할 것이다.(아마도 와장창..!)
이처럼 스택은 가장 먼저 들어온 데이터가 가장 아래에 놓이고, 가장 나중에 들어온 데이터가 가장 위쪽에 놓인 후 가장 위 쪽 데이터(가장 나중에 들어온 데이터)부터 처리하는 방식이다. 이를 후입선출(LIFO : Last In First Out)이라고 한다.
스택에서 데이터를 넣는 것은 push, 데이터를 꺼내는 것을 pop이라 하며, push과 pop이 이루어지는 위치를 top이라 한다.
스택의 Big O(시간복잡도)
스택의 추가와 삭제는 모두 O(1)이 걸린다.
반면 데이터를 가져올 때에는 O(n)이 걸린다. 빅오 표기법은 최악의 경우의 수를 말하기 때문에, 스택에서의 최악의 경우는 가장 먼저 들어온 데이터를 꺼내야하는 경우이다. 즉, 이후 데이터를 모두 꺼내야만 첫 데이터를 가져올 수 있기 때문에 시간복잡도는 O(n)라 할 수 있다.
스택 구현을 위한 의사코드
class Stack {
constructor() {
this.storage = {}; // 빈 객체에 numeric key(인덱스)로 스택을 구현한다.
this.top = 0; // top은 가장 마지막에 쌓여있는 데이터의 인덱스를 뜻한다.
}
size() {
// this.storage의 객체의 키를 모은 배열의 길이를 구한다.
// 혹은 this.storage의 마지막 인덱스를 구해 1을 더해준다.
}
push(element) {
// this.storage에 들어있는 마지막 인덱스 뒤에 새로운 인덱스(마지막 인덱스+1)를 추가한 후 element를 할당한다.
// 참고 : 새로운 인덱스는 현재의 this.top과 같다.
// this.top에 추가한 인덱스를 반영한다.
}
pop() {
// 삭제 전 마지막 인덱스의 element를 새로운 변수에 저장한다.
// this.storage에서 마지막 인덱스를 삭제한다.
// this.top에 삭제한 인덱스를 반영한다.
// 저장한 마지막 인덱스의 element를 리턴한다.
}
}2. Queue
큐란?
Queue는 프랑스어로 '기다리며 늘어선 줄, 장사진'이라는 뜻을 가진다고 한다. 아이스크림 가게에 줄을 선 손님들을 생각하면 이해하기 쉬운데, 가장 먼저 온 손님 순서대로 아이스크림을 받을 수 있다.(만약 그 반대라면 폭동이 일어날...) 이렇게 큐란 가장 먼저 들어온 데이터를 가장 먼저 처리하는 방식을 뜻하며, 이를 선입선출(FIFO : First In First Out)이라고 한다.
큐에서 데이터를 넣는 것은 enqueue, 데이터를 꺼내는 것을 dequeue라 하며, 큐에 있는 첫 데이터(가장 먼저 들어온 데이터)를 front, 마지막 데이터(가장 나중에 들어온 데이터)를 rear라 한다.
큐의 Big O(시간복잡도)
큐의 시간 복잡도는 스택과 동일히다. 추가와 삭제는 모두 O(1)이 걸리며 데이터를 가져올 때에는 O(n)이 걸린다. 큐에서의 최악의 경우는 가장 나중에 들어온 데이터를 꺼내야하는 경우이다. 즉, 이전 데이터를 모두 꺼내야만 첫 데이터를 가져올 수 있기 때문에 시간복잡도는 O(n)라고 할 수 있다.
큐 구현을 위한 의사코드
class Queue {
constructor() {
this.storage = {}; // 빈 객체에 numeric key(인덱스)로 스택을 구현한다.
this.front = 0; // front는 가장 먼저 들어온 데이터의 인덱스를 뜻한다.
this.rear = 0; // rear는 가장 나중에 들어온 데이터의 인덱스를 뜻한다.
}
size() {
// this.storage의 객체의 키를 모은 배열의 길이를 구한다.
// 혹은 this.storage의 마지막 인덱스를 구해 1을 더해준다.
}
enqueue(element) {
// this.storage에 들어있는 마지막 인덱스 뒤에 새로운 인덱스(마지막 인덱스+1)를 추가한 후 element를 할당한다.
// 참고 : 새로운 인덱스는 현재의 this.rear과 같다.
// this.rear에 추가한 인덱스를 반영한다.
}
dequeue() {
// 삭제 전 front 인덱스의 element를 새로운 변수에 저장한다.
// this.storage에서 front 인덱스를 삭제한다.
// front에 삭제한 인덱스를 반영한다.
// 저장한 front 인덱스의 element를 리턴한다.
}
}
// 다만 이 코드의 경우 dequeue 실행 후 남아있는 데이터의 index가 변하지 않기 때문에
// 첫 index가 0이 아니다.
// 이 문제를 해결하려면 dequeue 실행시마다 모든 데이터의 index를 하나씩 앞으로 당겨주는 작업이 필요하다.
// 하지만 이 경우 메모리를 소모하고 비효율적이다.