[자료구조]큐(Queue)연산 및 종류

 

 

Queue

---

 

1. Queue 연산

• enQueue(item) : Queue의 뒤쪽(rear 다음)에 원소를 삽입
• deQueue() : Queue의 앞쪽(front)에서 원소를 삭제하고 반환
• createQueue() : 공백상태의 Queue를 생성하는 연산
• isEmpty() : Queue가 공백상태인지 확인
• isFull() : Queue가 포화상태인지 확인
• Qpeek() : Queue의 앞쪽(front)에서 원소를 삭제 없이 반환

 

---

 

2. 종류

1) 선형 Queue

 

• 삽입(sudo)

  enQueue(item)     if(isFull()) then Queue_Full(); else{     rear <- rear+1;     Q[rear] <- item; } end enQueue() 

•  
• 삭제(sudo)

• deQueue()     if(isEmpty()) then Queue_Empty(); else{     front <- front +1;     return Q[front]; } end deQueue() 

• 공백상태 및 포화상태 검사(sudo)
  • 공백상태 : front = rear
  • 포화상태 : rear = n-1(n:배열의 크기, n-1:배열의 마지막 인덱스)

  isEmpty()     if(front=rear) then return true; else return false; end isEmpty()      isFull()     if(rear = n-1) then return true; else return false; end isFull() 

•  

 

• 검색(sudo)
  • 가장 앞에 있는 원소를 검색하여 반환

  Qpeek()     if(isEmpty()) then Queue_Empty(); else return Q[front+1]; end Qpeek() 

•  

 

---

 

2) 원형 Queue

 

• 공백 및 포화상태 검사
  • 공백상태 : front = rear
  • 포화상태 : 삽입할 rear의 다음 위치 = 현재 front
  • (rear + 1) mod n = front

  isEmpty() 	if(front = rear) then return true; 	else return false; end isEmpty() isFull() 	if((rear+1) mod n = front ) then return true; 	else return false; end isFull() 

•  

 

• 삽입
  • 삽입 위치 : rear = (rear+1) mod n

  enQueue(item)     if(isFull()) then Queue_Full(); else{     rear <- (rear +1)mod n;     cQ[rear] <- item; } end enQueue() 

•  

• 삭제
  • front 값을 조정하여 삭제할 자리를 준비

  deQueue()     if(isEmpty()) then Queue_empty(); else{     front <- (front+1) mod n;     return cQ[front]; } end deQueue() delete()     if(isEmpty()) then Queue_Empty(); else front <- (front+1) mod n;  end delete() 

•  

 

#define Q_SIZE 4 int queue[Q_SIZE]; int front, rear = 0;  void enQueue(int item) //삽입 {     if (isFull()) exit(1);     else {         rear = (rear+1)%Q_SIZE;         queue[rear] = item;     } }  int deQueue(int[] queue) //삭제 {     if(isEmpty()) exit(1);     else {         front = (front +1)%Q_SIZE;         return queue[front];     } } 

 

---

3) 연결 Queue

 

 

 

typedef int element;  typedef struct Node{     element data;     struct Node *next; }  typedef struct {     Node *front, *rear; }QueuePointer;  QueuePointer *LQ;  QueuePointer *createLinkedQueue(){     LQ = (QueuePointer*)malloc(sizeof(QueuePointer));     LQ -> front = NULL;     LQ -> rear = NULL;     return LQ; }  void enQueue(element item){     Node *newNode = (Node*)malloc(sizeof(Node));     newNode -> data = item;     newNode -> next = NULL;     if(LQ -> front == NULL){         LQ -> front = newNode;     }     else{         LQ -> rear -> next = newNode;         LQ -> rear = newNode;     } } element deQueue(){     Node *old = LQ -> front;     element item;     if(isEmpty(LQ)) return 0;     else {         item = old -> data;         LQ -> front = LQ ->front->next;         if(LQ -> front == NULL)             LQ -> rear = NULL;                  free(old);         return item;     } } 

 

 

---

 

3. 활용

1) 우선순위 Queue

​ 배열을 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생한다.

​ 이 때 소요되는 시간, 메모리 낭비에 대한 해결책이 바로 우선순위 Queue 혹은 Heap 자료구조 이다.

2) 버퍼

​ 데이터를 한곳에서 다른 한곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역