Stack & Queue

🍡 Stack

스택은 가장 마지막에 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료구조이다.

스택에 원소를 삽입할때는 그냥 마지막 위치에 올리기만 하면 되므로 O(1)이 걸리고

원소를 검색할 때는 원하는 값이 나올 때까지 마지막 원소부터 하나씩 제거해봐야 하기 때문에 최악의 경우 O(n)이 걸린다.

 

 

 

📌 Stack의 구현

Stack의 구현 방법은 두 가지가 있다.

1. Array 기반
2. Linked List 기반

Array와 Linked List 자체가 이미 하나의 자료구조이지만, 이 자료구조를 사용해서 Stack이라는 자료구조를 구현할 수 있는 것이다.

Array를 기반으로 구현한 스택과 Linked List 기반으로 구현한 스택 모두 각각의 장단점이 있고 이는 Array 자체의 장단점과 Linked List 자체의 장단점과 동일하다. (참고: Array vs Linked List)

 

 

 

📌 Stack의 활용

1. 에디터, 포토샵 등에서 실행한 기능을 취소하는 경우

2. 웹 브라우저의 앞으로가기 및 뒤로 가기 기능

3. 하노이 타워, 트리 탐색, 히스토그램 문제와 같은 알고리즘

4. 백트래킹(ex. N-Queen, 미로에서 길 찾기 등)

5. 메모리 관리(오늘날 컴퓨터는 실행 목적으로 스택을 기본 관리로 사용)

6. 문자열 반전

문자열의 첫 번째 문자는 스택의 맨 아래에 있고 문자열의 마지막 요소는 스택의 맨 위에 있다. 스택에서 pop()으로 원소를 하나씩 꺼내서 출력하면 문자열이 역순으로 표시된다. 

 

 

 

🗂 Queue

큐는 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 가진 자료구조이다.

마지막에 삽입된 데이터가 먼저 나오는 스택과 정반대의 개념이다.

실생활의 예를 들어보자면, 놀이공원에 입장하기 위해 줄을 섰을 때 맨 앞의 사람부터 차례대로 들어가는 경우를 생각해보면 될 것이다.

큐 역시 원소를 삽입할 때는 마지막 위치에 집어넣기만 하면 되므로 O(1)이 걸리고,

원소를 검색할 때는 원하는 값이 나올 때까지 첫 번째 원소부터 하나씩 제거해봐야 하기 때문에 최악의 경우 O(n)이 걸린다.

 

 

 

📌 Queue의 구현

큐의 구현 방식도 스택과 마찬가지로 두 가지가 있다.

1. Array 기반
2. Linked List 기반

 

 

 

📌 Queue의 유형

큐에는 크게 3가지 유형이 있다.

1. Circular Queue(원형 큐)

선입선출(First In First Out) 원칙에 따라 연산을 수행하고 마지막 위치를 다시 첫 번째 위치로 연결하여 원을 만드는 선형 데이터 구조이다.

 

2. Priority Queue(우선순위 큐)

우선순위 큐는 요소에 할당된 우선순위에 따라 요소가 액세스 되는 특수한 큐이다.

큐와 비슷하지만, 각 큐가 우선순위를 갖고 있어서 무조건 먼저 들어왔다고 먼저 처리되는 게 아니라 누가 더 응급한 지에 따라 처리된다.

우선순위 큐의 구현 방법은 Array 기반, Linked List 기반, 그리고 Heap 기반 이렇게 3가지가 있다.

Array의 단점이 원소를 삽입/삭제할 때 나머지 원소들을 한칸씩 이동시켜줘야 한다는 것인데, 이 자료구조를 기반으로 우선순위 큐를 구현하면 최악의 경우(우선순위가 가장 낮은 원소를 삽입하는 경우) 배열의 모든 원소의 우선순위와 내 우선순위를 하나하나 비교해서 자리를 찾아야 한다는 단점이 또 생긴다.

Linked List는 어떨까? 우선 Linked List의 경우 원소를 삽입/삭제할때 나머지 원소를 이동시켜야 하는 불편함은 발생하지 않는다.

하지만 연결 리스트 역시 원소를 삽입하는 과정에서 첫 번째 노드부터 마지막 노드까지 노드에 저장된 데이터의 우선순위와 나의 우선순위를 비교해야만 하는 상황이 발생할 수 있다.

따라서 우선순위 큐는 Array도 아닌, Linked List도 아닌, Heap이라는 자료구조를 사용해서 구현하는 것이 일반적이다.

 

 

 

⚡️ 한눈에 비교하는 Stack vs Queue

Stack	Queue
LIFO(Last In First Out)	FIFO(First In First Out)
삽입/삭제는 스택의 최상위(top)에서만 수행됨	삽입은 리스트의 제일 뒷부분(rear)에서 수행. 삭제는 리스트의 제일 처음(front)에서 수행
하나의 포인터 필요(top)	두 개의 포인터 필요(front / rear)
주로 재귀 문제 해결에 사용	주로 순차 처리 문제 해결에 사용
유형 없음	3개의 유형(원형 큐, 우선순위 큐, deque)
수직적	수평적

 

 

 

🔗 References

introduction-to-stack-data-structure-and-algorithm-tutorials

introduction-to-queue-data-structure-and-algorithm-tutorials

difference-between-stack-and-queue-data-structures

⌜윤성우의 열혈 자료구조⌟