개발자가 되기 전 다양한 알바와 다양한 일들을 해봤는데 그 중 우체국 배송 보조 알바를 했던 경험이 떠오른다.
아침에는 도착한 우편물을 지역에 맞게 분류하는 작업을 하고 해당 물품을 트럭에 싣는 작업을 하고,
오후에는 계약된 업체를 방문해서 우편물을 받아오고, 받아온 우편물을 다시 우체국에 두는 작업을 했다.
이 때부터 난 온몸으로 스택과 큐에 대해서 경험하고 있었던게 아닐까?
이번에는 자료구조 중 선형 자료구조의 스택과 큐에 대해서 알아보자.
스택 (Stack)
스택은 마치 상하차처럼 바닥부터 데이터를 쌓아가고, 데이터를 꺼낼 때는 위에서부터 꺼내는
후입선출 (LIFO, Last In, First Out) 방식으로 데이터를 처리하는 자료구조다.
스택의 데이터 삽입과 삭제 모두 한쪽 끝에서 이루어지는 방식인데, 이 곳을 top이라고 한다.
데이터를 중간에 삽입하는 것은 불가능하고,
특정 데이터를 찾기 위해서는 하나씩 꺼내야 하기 때문에 시간 복잡도는 O(n)이다.
이러한 특징을 갖고 있는 스택으로 구현할 수 있는 기능은
대표적으로 웹 브라우저의 뒤로가기 기능 / 실행 취소 등의 기능이 있다.
const stack = [];
stack.push(1);
stack.push(2);
console.log(stack); // [ 1 , 2 ]
stack.pop();
console.log(stack); // [ 1 ]스택을 배열로 구현하면 다음과 같이 구현할 수 있겠다.
push를 통해 값을 쌓아가고, pop을 이용해 가장 뒤에 있는 데이터를 뽑아내는 형태로 구현할 수 있다.
위에서 데이터를 중간에 삽입하는 것은 불가능하다고 했는데,
사실 배열은 인덱스 값을 이용해서 중간에 데이터를 삽입할 수 있다.
자료구조는 데이터를 관리하는 '방법'이기 때문에,
배열이라는 형식을 이용해 스택 방법을 활용하는 거라고 보면 될 것 같다.
큐 (Queue)
큐는 컨베이어벨트 처럼 먼저 들어온 데이터를 먼저 처리하는
선입선출 (FIFO, First In First Out) 방식으로 데이터를 처리하는 자료구조다.
큐의 데이터 삽입과 삭제는 다른 방향에서 이루어지는데 삽입은 꼬리(tail)에서 삭제는 머리(head)에서 이루어진다.
스택과 마찬가지로 중간에 데이터를 삽입할 수 없고,
특정 데이터를 찾기 위해서는 앞에서 하나씩 꺼내야 하기 때문에 시간 복잡도는 O(n)이다.
이러한 특징을 갖고 있는 큐로 구현할 수 있는 기능은
대표적으로 우선순위 예약, 프로세스 관리 등이 있다.
const queue = [];
queue.push(1);
queue.push(2);
console.log(queue); // [ 1 , 2 ]
queue.shift();
console.log(queue); // [ 2 ]큐를 배열로 구현하면 다음과 같이 구현할 수 있겟다.
push를 통해 데이터를 삽입하고, shift를 이용해 가장 앞에 있는 데이터를 뽑아내는 형태로 구현할 수 있다.
여기서 주의해야 할 점은 스택이나 큐 모두 데이터의 삽입과 삭제는 O(1)의 시간복잡도를 갖는데
shift의 경우, 가장 앞에 데이터를 제거한 뒤 배열의 데이터를 한칸씩 당기기 때문에 O(n)의 시간 복잡도를 갖는다.
그래서 데이터가 적을때는 상관없지만 다량의 데이터가 있을 때는 적합하지 않다.
포스팅 작성에 참고한 감사한 글들
'CS > Data Structures' 카테고리의 다른 글
| 자료구조 : 데이터를 관리하는 여러가지 방법 (1) | 2024.11.12 |
|---|