자료구조 - 스택(Stack), 큐(Queue), 덱(Deque)

스택의 개념

스택(Stack)이란 한쪽 끝에서만 자료를 추가(삽입), 삭제(제거)하는 작업이 이루어지는 자료구조다. 마지막에 삽입된 데이터가 가장 먼저 제거(LIFO, Last In First Out)되는 구조를 갖는다. 

 

 

스택의 주요 연산

• push: 스택의 맨 위에 데이터를 추가하는 연산
• pop: 스택의 맨 위에 있는 데이터를 제거하는 연산
• peek/top: 스택의 맨 위에 있는 데이터를 제거하지 않고 확인하는 연산
• isEmpty: 스택이 비어 있는지 확인하는 연산

 

스택의 장점과 단점

장점

• 자료구조 중 구현이 매우 간단한 편으로, 배열이나 연결 리스트를 통해 쉽게 구현할 수 있다.
• 함수 호출 스택, 재귀 호출, 백트래킹 등에서 매우 유용하게 사용되어 메모리 관리에 유용하다.

단점

• 스택은 LIFO 방식으로 동작하므로 중간에 있는 데이터에 접근하기 어렵다.
• 배열 기반 스택의 경우 크기가 고정되어 있어 오버플로우가 발생할 수 있다.
  • 연결 리스트 기반으로 해결할 수 있지만, 메모리 오버헤드가 발생한다.

 

스택의 사용 사례

• 순차적인 데이터를 후입선출 방식으로 처리해야 하는 경우
  
  • 후위 표기식 계산 또는 백트래킹 알고리즘에서 순서가 중요한 경우
• 재귀적인 연산이 필요한 경우
  • DFS(깊이 우선 탐색)에서 경우 탐색 시
  • 그래프나 트리에서 특정 경로로 깊이 들어가는 작업이 많을 때
• 한 쪽 끝에서만 추가, 삭제 연산이 빈번한 경우
• 매모리나 프로그램 흐름을 추적하는 경우
  • 웹 브라우저의 뒤로 가기/앞으로 가기, undo 기능 등 구현

 

---

큐의 개념

큐(Queue)란 양쪽 끝에서 각각 자료를 추가(삽입)와 삭제(제거)하는 작업이 이루어지는 자료구조다. 먼저 삽입된 데이터가 가정 먼저 제거(FIFO, First In First Out)되는 구조를 갖는다. 삽입은 한쪽 끝(뒤)에서 이루어지며, 삭제는 반대쪽 끝(앞)에서 이루어진다.

원형 큐

원형 큐(Circular Queue) 란 큐의 확장된 형태로, 배열의 처음과 끝이 연결된 원형 구조를 갖는다. 일반적인 큐와 달리, 데이터가 가득 찼을 때도 비어있는 공간을 재활용할 수 있어 배열의 크기를 효율적으로 사용할 수 있다. 삽입과 삭제는 FIFO 원칙을 따르며, 포인터가 배열의 끝에 도달하면 다시 처음으로 돌아가서 순환한다.

 

 

큐의 주요 연산

• enqueue: 큐의 뒤에 데이터를 추가하는 연산
• dequeue: 큐의 앞에 있는 데이터를 제거하는 연산
• peek/front: 큐의 앞에 있는 데이터를 제거하지 않고 확인하는 연산
• isEmpty: 큐가 비어 있는지 확인하는 연산

 

큐의 장점과 단점

장점

• 큐는 FIFO 방식으로, 먼저 입력된 데이터가 먼저 처리되어 순차적인 작업 처리에 유리하다.
• 여러 개의 생산자와 소비자가 동시에 작업을 수행하는 상황에서 유용하며, 비동기적인 데이터 처리에 적합하다.

단점

• 큐는 중간에 있는 데이터에 임의 접근이 불가능하여, 중간 데이터를 빠르게 검색하는 데에는 비효율적이다.
• 배열 기반 큐의 경우 크기가 고정되어 있어, 공간 낭비가 발생하거나 초과할 때 오버플로우가 발생할 수 있다.
  • 원형 큐로 공간 낭비 문제를 해결할 수 있지만, 구현이 복잡해질 수 있다.

 

큐의 사용 사례

• 순차적인 데이터를 먼저 입력된 순서대로 처리해야 하는 경우
  • 멀티태스킹 운영체제에서  작업 스케줄링이나 프로세스 관리에 사용
  • 네트워크 패킷 처리 또는 프린터 작업 대기열처럼 입력된 순서가 중요한 시스템에서 사용
  • BFS(너비 우선 탐색)와 같은 알고리즘에서 노드를 순차적으로 탐색할 때
• 생산자-소비자 패턴에서 생산자가 데이터를 입력하고 소비자가 데이터를 처리하는 경우

 

생산자-소비자 패턴
멀티스레딩에서 자주 사용되는 디자인 패턴으로, 생산자(Producer)와 소비자(Consumer)라는 두 역할이 특정 자원을 공유하며 데이터를 주고받는 구조를 의미한다. 생산자는 데이터를 생성하여 큐같은 자료구조에 저장하고, 소비자는 큐에서 데이터를 꺼내 처리한다. 생산자-소비자 패턴의 주요 목적은 동시성 문제를 해결하는 것으로, 특히 여러 스레드가 동시에 데이터를 다룰 때 발생하는 충돌을 방지하는 데 유용하다.

 

---

 

덱의 개념

덱(Deque, Double-Ended Queue)이란, 양쪽 끝에서 모두 자료의 추가(삽입)와 삭제(제거) 작업이 이루어질 수 있는 자료구조다. 스택과 큐의 특성을 모두 갖추고 있어, 데이터를 앞과 뒤에서 모두 삽입하고 삭제할 수 있는 유연한 구조를 제공한다. 삽입과 삭제는 양방향에서 이루어지며 LIFO 또는 FIFO 방식 모두를 지원한다.

원형 덱

원형 덱(Circular Deque)이란 덱의 확장된 형태로, 배열의 처음과 끝이 연결된 원형 구조를 갖는 자료구조다. 삽입과 삭제는 양쪽 끝에서 모두 가능하며, 원형 큐와 마찬가지로 삽입과 삭제 연산이 이루어질 때 포인터가 배열의 끝에 도달하면 다시 처음으로 순환한다. 이로 인해 메모리 공간을 보다 효율적으로 사용할 수 있으며, 덱의 특성을 유지하면서 배열의 고정된 크기 문제를 해결한다.

 

 

덱의 주요 연산

• addFirst: 덱의 앞에 데이터를 추가하는 연산.
• addLast: 덱의 뒤에 데이터를 추가하는 연산.
• removeFirst: 덱의 앞에 있는 데이터를 제거하는 연산.
• removeLast: 덱의 뒤에 있는 데이터를 제거하는 연산.
• peekFirst: 덱의 앞에 있는 데이터를 제거하지 않고 확인하는 연산.
• peekLast: 덱의 뒤에 있는 데이터를 제거하지 않고 확인하는 연산.
• isEmpty: 덱이 비어 있는지 확인하는 연산.

 

덱의 장점과 단점

장점

• 양방향에서 데이터를 처리할 수 있어, 스택과 큐의 장점을 모두 활용할 수 있다.
• FIFO 또는 LIFO 방식을 모두 지원하여, 데이터의 처리 순서를 유연하게 조정할 수 있다.

단점

• 덱은 중간에 있는 데이터를 검색하거나 접근할 때 O(n)의 시간이 소요되므로, 중간 데이터에 대한 임의 접근은 비효율적이다.
• 연결 리스트 기반 덱은 추가적인 메모리 오버헤드가 발생한다.
• 구현이 큐나 스택보다 복잡할 수 있으며, 원형 덱을 구현할 경우 추가적인 포인터 관리가 필요하다.

 

덱의 사용 사례

• 양쪽 끝에서 삽입과 삭제가 빈번한 경우
  • 양방향 큐로서 앞과 뒤에서 데이터 처리가 필요한 경우
  •  슬라이딩 윈도우 알고리즘 처럼 앞뒤로 데이터를 처리해야 하는경우
• 캐시 시스템에서 자주 사용되는 LRU(Least Recently Used) 알고리즘을 구현할 때 
• 회문 검사 등에서 앞뒤 데이터를 동시에 비교하는 경우
• BFS에서 양방향 탐색을 진행하거나 최소 비용 경로 탐색을 구현할 때

 

LRU(Least Recently Used) 알고리즘
LRU 알고리즘은 캐시 교체 알고리즘 중 하나로, 캐시에 저장할 수 있는 데이터의 양이 제한되어 있을 때, 가장 오랫동안 사용되지 않은 데이터를 먼저 제거하는 방식으로 동작한다. 캐시는 데이터를 빠르게 저장하고 읽어오는 임시 저장소인데, 용량이 한정되어 있기 때문에 모든 데이터를 계속 보관할 수 없다. LRU 알고리즘은 캐시가 가득 찼을 때 가장 최근에 사용되지 않은 데이터를 제거하고 새로운 데이터를 캐시에 저장하는 방법을 제공한다.
덱은 양쪽 끝에서 삽입과 삭제가 가능하기 때문에, LRU에서는 최근에 사용된 데이터를 앞쪽에 두고, 가장 오랫동안 사용되지 않은 데이터를 뒤쪽에 두면 쉽게 관리할 수 있다.

 

---

스택 vs 큐 vs 덱

	스택 (Stack)	큐 (Queue)	덱 (Deque)
데이터 삽입/삭제	한쪽 끝에서만 (LIFO)	삽입: 뒤, 삭제: 앞 (FIFO)	양쪽 끝 모두 가능 (LIFO/FIFO)
시간 복잡도 (삽입/삭제)	O(1)	O(1)	O(1)
데이터 접근 방식	LIFO (Last In, First Out)	FIFO (First In, First Out)	LIFO 및 FIFO 모두 지원
중간 데이터 접근	비효율적 (O(n))	비효율적 (O(n))	비효율적 (O(n))
사용 사례	재귀, 함수 호출, DFS	작업 대기열, BFS, 프로세스 스케줄링	슬라이딩 윈도우, LRU 캐시
구현 난이도	간단	간단	상대적으로 복잡
메모리 구조	배열 또는 연결 리스트	배열 또는 연결 리스트	배열 또는 연결 리스트
장점	간단한 구현, 메모리 관리 유용	공정한 처리, 순차적 데이터 관리	양쪽 끝에서 유연한 처리 가능
단점	중간 데이터 접근 비효율	중간 데이터 접근 비효율	구현 복잡성, 메모리 오버헤드