[자료구조] 선형 자료구조 2탄 : 스택, 큐, 원형 큐, 덱

---

1. 스택 (Stack)

 

데이터가 들어오면서 TOP은 들어온 데이터를 가리킨다.

TOP이 가리키는 데이터가 나가면서 TOP은 밑에 있는 데이터를 가리킨다.

 

📌 스택의 특징 

📝 스택은 가장 최근에 들어온 것이 가장 먼저 나가는 후입선출(LIFO) 자료구조이다.
스택의 입출력은 맨 위에서만 일어나고, 중간에서는 삭제를 할 수 없다. 
데이터가 들어오는 과정을 push, 나가는 과정이 pop이라고 일반적으로 정의한다. 
가장 최근에 들어온 자료는 TOP라 한다. 

스택이 비어있을 때 POP을 하면, 스택 언더 플로우 발생하고,
반대로 꽉 차있을 때 PUSH을 하면 스택 오버 플로우가 발생한다. 

 

📌 스택의 활용 

애플리케이션 뒤로가기, ctrl+Z
후위 표기법 계산
재귀적 알고리즘
JAVA에서 지역변수, 리턴값 등을 저장하는 메모리 구조
괄호 검사 알고리즘
미로 탐색 프로그램 등

 

 

2. 큐 (Queue)

 

📌 큐의 특징 

📝 큐는 TOP에서만 데이터의 삽입, 삭제가 이루어지는 스택과는 다르게
Rear(뒤) 부분에서 삽입이루어진다.
Front(앞) 부분에서 삭제가 이루어지는 선입선출 (FIFO) 자료 구조이다.
JAVA를 예를 들면, 삽입을 offer() 혹은 add()로 표현하고, 삭제는 poll()을 사용한다. 

스택과 마찬가지로 큐가 비어있을 때 삭제나 탐색을 하면 큐 언더플로우가 발생하고,
큐가 꽉 차있을 때 삽입을 하면 큐 오버플로우가 발생한다. 
오버플로우를 방지하기 위해 나온 것이 원형 큐 (Circular Queue) 이다. 

 

📌 큐의 활용 

CPU 스케쥴링 : 간단한 형태의 선입선출 처리 스케쥴링 정책
버퍼를 사용하는 것들 : 프린터 출력 등 
교통 관리 시스템 같은 일반적인 대기열을 사용하는 상황
BFS : 너비우선탐색

 

📌 원형 큐 (Circular Queue)

 

 

도서, 파이썬 알고리즘 인터뷰 p.260, 나무위키

📝 마지막 위치와 시작 위치가 연결되는 원형쿠조를 띠는 큐이다. 선입선출 구조를 지닌다는 점에서 동일하며, 
포화인 큐에서 삽입을 하면 오버플로우가 발생하는 선형 큐를 보완한 자료구조이다. 
enqueue : 값 삽입 (rear 포인터가 앞으로 이동)
dequeue : 값 삭제 (front 포인터가 앞으로 이동)
공백 상황 : front 포인터와 rear 포인터가 같은 값인 인덱스 0을 가리킬 때.
포화 상황 : front 포인터의 값과 rear 포인터의 값의 차가 1일때. 

📝 front 포인터 혹은 rear 포인터와 큐의 사이즈를 나머지연산을 이용하여
인덱스를 계속 순환하도록 하여 오버플로우가 발생하지 않도록 함.
enqueue(20) -> rear = ((rear+1) % 5(size) = 2) 에 삽입. 
dequeue() -> front = ((front+1) % 5 = 1) 

 

3. 덱(Deque)

📌 덱의 특징

📝 덱은 앞, 뒤 양쪽에서 데이터의 삽입, 삭제가 가능한 자료구조이다. 이러한 특징으로 스택보다는 큐 형태로 사용이 가능하다. 
구현이 어려운 것이 특징이나,  원하는 요소에 바로 스택, 큐보다 빠르게 접근이 가능하다는 이점이 있다.

 

4. 시간 복잡도

	삽입	삭제	읽기, 탐색
스택	O(1)	O(1)	O(n)
큐	O(1)	O(1)	O(n)
덱	O(1)	O(1)	O(n)