📕 큐(Queue)
- 먼저 들어온 데이터가 먼저 나가는 자료구조
- 선입선출(FIFO: First-In First-Out)
큐 ADT
객체: 0개 이상의 요소들로 구성된 선형 리스트
연산:- create(MAX_SIZE) ::= 최대 크기가 MAX_SIZE인 공백 큐 생성 - init(q) ::= 큐를 초기화 한다 - is_empty(q) ::= if(size == 0) return TRUE else return FALSE - is_full(q) ::= if(size == MAX_SIZE) return TRUE else return FALSE - enqueue(q, item) ::= if(is_full(q)) 큐 포화 에러 else q의 끝에 item 추가 - dequeue(q) ::= if(is_empty(q)) 큐 공백 에러 else q의 맨 앞에 있는 item 제거 및 반환 - peek(q)::= if(is_empty(q)) 큐 공백 에러 else q의 맨 앞에 있는 item 읽어와 반환
📒 선형큐
배열을 선형으로 사용하여 큐를 구현
- 삽입을 계속하기 위해서는 요소들을 이동시켜야 한다.
- 초기화 시에 front=rear=-1로 초기화 한다.
typedef int element;
typedef sturct{
int front;
int rear;
element data[MAX_QUEUESIZE];
} QueueType
void init_queue(QueueType* q){
q->rear =-1;
q->front=-1;
}
...선형 큐의 삽입 삭제 예시
선형큐는 data를 삽입하고 삭제하는 과정을 반복하다보면 배열의 앞부분을 사용하지 않기때문에 주로 원형큐를 구현하여 사용한다.
📗 원형큐
1) 원형큐의 구조
큐의 전단과 후단을 관리하기 위한 2개의 변수 필요
- front: 첫번째 요소 하나 앞의 Index
- rear: 마지막 요소의 Index
- 초기화 시에 front=rear=0으로 초기화 한다.
2) 동작 및 공백/포화 상태
🍳 원형큐의 동작
🍳 원형큐의 공백/포화 상태
공백 상태: front == rear (인덱스가 같은 경우)
포화 상태: (rear+1)%MAX_SIZE == front
공백과 포화를 구별하기 위해 큐의 하나의 공간은 항상 비워둠
🚫 에러 상태
아래 상태는 front == rear인데 포화 상태이다.
즉, 하나의 공백없이 삽입 삭제를 진행할 경우 이처럼 오류가 발생할 수 있다.
하지만, 요소의 개수를 세는 변수를 따로 지정한다면 하나의 공백을 만들지 않아도 된다!
📘 덱(Deque)
추후 추가 예정
