티스토리 뷰
[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다.
* 큐(Queue)
- 리스트의 한쪽 끝에서는 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어짐
- 삽입된 순서대로 삭제되는 선입선출(FIFO, First-In-First-Out) 구조
[큐의 구조]
- Front : 저장된 원소 중에서 첫번째 원소
- Rear : 저장된 원소 중에서 마지막 원소
* 큐의 연산
- enqueue() - 큐에 끝(rear)에 항목을 추가
- dequeue() - 큐에 맨 앞(front)에 항목을 제거
- peek() - 큐에 맨 앞(front)에 있는 항목을 반환
- isfull() - 큐가 가득 찼는지 확인
- isempty() - 큐가 비어 있는지 확인
* 큐 구현 방법
1) 순차 자료구조방식을 이용한 큐의 구현
- 선형 큐 : 1차원 배열을 사용하여 순차 자료구조방식으로 구현
(참고) 선형 큐 문제 : 인덱스를 감소하지는 않고 증가만 하면서 사용하는 방식이기에 실제로 앞부분에는 데이터가 없을 때에도 비어있는 공간을 활용할 수 없거나, 활용하기 위해서는 저장된 원소를 배열의 앞부분으로 이동시켜서 위치를 조정해줘야 하기 때문에 비효율적임
- 원형 큐 : 선형 큐에서의 문제를 해결하기 위해 사용하며, 1차원 배열을 사용하는데 논리적으로 배열의 처음과 끝이 연결되어 있는 큐
front가 rear을 쫓아가는 형태 → front == rear 이면 공백상태
(참고) 순차 자료구조방식을 이용하여 구현한 큐의 문제
(1) 사용 크기가 제한되어 있어서 큐의 길이를 마음대로 변경할 수 없음
(2) 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리 낭비됨
2) 연결 자료구조방식을 이용한 큐의 구현
- 연결 큐 : 순차 자료구조방식을 이용하여 구현한 큐의 문제를 극복하기 위해 크기에 제한이 없으며, 원소는 데이터 필드와 링크 필드를 가진 노드로 구성됨
(참고) 연결 큐
1) 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫번째 노드를 가리키는 참조변수 front와 마지막 노드를 가리키는 참조변수 rear를 사용함
2) 연결 큐의 초기 상태(공백 큐)는 front와 rear를 NULL로 설정하여 표현함
- 덱(Deque, Double-ended Queue) : 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로, 스택의 성질과 큐의 성질을 모두 가짐
[덱의 구조]
'개인공부 > 자료구조|알고리즘' 카테고리의 다른 글
| [자료구조] 그래프(Graph) (0) | 2023.11.22 |
|---|---|
| [자료구조] 트리(Tree) (0) | 2023.11.20 |
| [자료구조] 스택(Stack) (0) | 2023.11.20 |
| [자료구조] 연결 리스트(Linked List) (0) | 2023.11.20 |
| [자료구조] 리스트(List) (0) | 2023.11.20 |