[자료구조] ep6-1) 큐(Queue)

ㅇ큐 ADT: 임의의 개체들을 저장하며, 선입선출(First-In First-Out, FIFO) 순서를 따른다

삽입(enqueue)은 큐의 뒤(rear), 삭제(dequeue)는 큐의 앞(front)이라 불리는 위치에서 수행

FIFO

 

 

- 직접 응용: 대기열, 관료적 체제, 공유자원에 대한 접근(e.g. 프린터), 멀티프로그래밍

- 간접 응용: 알고리즘 구현, 자료구조 구현

 

 

 

 

 

큐도 마찬가지로 배열과 리스트 2가지 방법으로 구현할 수 있다

연결리스트로에 기초한 큐는 배열로의 구현에 비해 동적 메모리 할당으로 크기에 유연하며, 메모리가 효율적이다

※ 배열에 기초한 큐는 ep6-2) 원형 큐를 보도록 하자

https://claremont.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ep6-2-%EC%9B%90%ED%98%95-%ED%81%90Circular-Queue

[자료구조] ep6-2) 원형 큐(Circular Queue)

 

 

 

단일연결리스트에 기초한 큐

 

삽입과 삭제가 특정위치에서만 수행되므로, 역방향링크는 불필요하다

 

 

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국)