큐(Queue)란?
큐 자료구조는 대표적인 선입선출(First In First Out; FIFO)의 자료구조다. 대기열이라고도 하는데, 표 같은 것을 구매하기 위해 줄을 서는 것을 의미한다.
가정 먼저 줄을 선 사람(First In)이 가장 먼저 표를 구매하고 가장 먼저 매표소를 빠져나가는 것(First Out)이다.
큐의 연산
enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부
dequeue : 큐 맨 앞쪽의 요소를 삭제
peek : front에 위치한 데이터 읽음
front : 큐의 맨 앞의 위치(인덱스)
rear : 큐의 맨 뒤의 위치(인덱스)
isFull : 큐가 꽉 찼는지 확인. rear == n - 1 즉, rear가 마지막 인덱스이면 꽉 찬 것 (선형 큐)
isEmpty : 큐가 비어있는지 확인. front == rear 이면 큐가 비었다고 판단 (선형 큐)
큐의 종류
1. Linear Queue (선형 큐)
- 기본적인 큐의 형태
- 막대 모양의 큐로, 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸 씩 옮겨야 한다는 단점이 있다.
2. Circular Queue (원형 큐)
- 선형 큐의 문제점을 보완하고자 나왔다.
- 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 (index + 1) % 배열의 사이즈 를 이용하여 Out of Bounds Exception이 일어나지 않고 인덱스 0으로 순환되는 구조를 가진다.
3. Priority Queue (우선순위 큐)
- 우선순위 큐는 들어가는 순서에 관계없이 큐에서 dequeue될 때, 우선순위에 맞게 나간다.
- 완전 이진 트리의 구조를 이용하여 트리의 균형을 맞춤
스택(Stack) 이란?
스택은 LIFO (Last In First Out) / FILO (First In Last Out) 순서를 따른다.
- LIFO : 마지막으로 들어온 값이 처음으로 나가는 것
- FILO : 처음 들어온 값이 마지막에 나가는 것
스택의 연산
push : 스택 맨 위에 항목을 삽입
pop : 스택 가장 위의 항목 삭제
peek or top : 스택의 맨 위(top) 표시
isEmpty : 스택이 비어있는지 확인
isFull : 스택이 가득 차 있는지 확인
getSize : 스택에 있는 요소 수를 반환
스택의 구현
스택의 구현 방법에는 두 가지가 있다.
1. 배열 사용
- 장점: 구현하기 쉬움
- 단점: 크기가 동적이 아님, 런타임시 필요에 따라 늘어나거나 줄어들지 않음
2. 연결 리스트 사용
- 장점: 크기가 동적임, 런타임시 필요에 따라 크기가 확장 및 축소될 수 있음
- 단점: 포인터를 위한 추가 메모리 공간이 필요함
스택의 사용
- 재귀 알고리즘을 반복문으로 구현하게 해줌
- 실행 취소 (undo)
- Backtracking
- 웹 브라우저 뒤로가기
- 구문분석
- 후위(postfix) 표기법 연산
- 문자열의 역순 출력
참고
'CS 지식 > 자료구조' 카테고리의 다른 글
| [자료구조] 해시테이블 (0) | 2024.10.27 |
|---|---|
| [자료구조] 이진탐색트리(Binary Search Tree) (0) | 2024.09.06 |
