* 스택, 큐, 덱이란?
- 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료구조입니다.
- 여기서 선형구조란? 데이터를 저장하기 위한 기본적인 형태로 데이터가 '일렬로 나열'되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미합니다.
- (배열/리스트와 유사하게) 값을 저장(insert 또는 set)하는 연산과 저장된 값을 꺼내는(remove 또는 get) 연산이 제공된다. 그러나 매우 제한적인 규칙(LIFO, FIFO)등을 따릅니다.
1. 스택
스택(Stack)은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.
조금 더 설명하자면, 위의 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있습니다.
간단한 예시로는 책상에 책을 쌓아두는 것과 포개 둔 일회용 종이컵을 하나하나 꺼내서 사용하는 것으로 예시를 들 수 있습니다.
또한 스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있습니다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능합니다.
즉, 스택의 맨 위 요소, top 에만 접근이 가능하기 때문에 top 이 아닌 위치의 데이터에 대한 접근, 삽입, 삭제는 모두 불가능합니다.
그리고 스택에서는 삽입 연산을 push, 삭제 연산을 pop이라고 하며, 이러한 스택의 구조를 후입 선출의 구조라고 하며, 줄여서 LIFO(Last In First Out)라고 부릅니다. 스택이 비어있을 때 stack.pop을 시도하면 stack underflow가 발생하며 스택의 크기가 비어있을 때 stack.push 를 시도하면 stack overflow가 발생합니다.
1) 시간복잡도
- top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.
2) 장단점
- top 을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다
- top 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능하다. 탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.
2. 큐
큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로, FIFO(First In First Out)의 구조를 가지고 있습니다.
일반적으로 카페에서 먼저 와서 주문한 손님이 음료를 먼저 받고 나가는 것을 예시로 들면 좋을 것 같네요.
삭제 연산이 수행되는 곳을 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)로, FIFO 구조를 위해서 스택과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있습니다.
큐는 리어(rear)에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며, 프론트(Front)에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부릅니다.
1) 큐 용어
- Enqueue: 데이터 삽입
- Dequeue (JS의 shift): 데이터 삭제
- Front: Dequeue시 삭제되는 데이터 (가장 먼저 저장된 데이터)를 가르킵니다.
- Rear: 추가될 새로운 요소의 위치를 가르킵니다.
3. 덱
덱은 큐 2개를 겹쳐 놓은 것과 같기 때문에 Double ended Queue라고 부르며 Deque이라는 명칭은 이를 축약형으로 부르는 것입니다. 이 자료구조는 이름처럼 양쪽에서 데이터의 입, 출력이 모두 가능한 자료구조입니다.
JS에서는 배열의 내장메소드로 모두 구현되어있으며 스택, 큐와 마찬가지로 front와 rear라는 포인터가 있으며 이들은 각각 가장 앞, 뒤에 있는 데이터를 가르킵니다.
다만, 스택과 큐의 Rear는 다음 요소가 삽입 될 위치를 가르키는 반면 덱의 Rear는 마지막 요소를 가르키고 있게 됩니다.
스택, 큐와 같이 데이터의 삽입과 삭제에 O(1)의 시간복잡도를 가집니다.
참조
[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!
📌 스택(Stack)이란 무엇일까? 스택(Stack)은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다. 조금 더 설명하자면, 위의 사진과 같이 데이터가 순서대로 쌓이며 가장 마지
jud00.tistory.com
