[Data Structure] 큐(Queue)

큐(Queue)

• 입구와 출구가 따로 있는 통로 형태
• A collection of elements that are inserted and removed according to the first-in first-out(FIFO) Principle.
  • 가장 먼저 추가된 요소가 가장 먼저 제거됩니다.
  • 모든 삽입(insertion)은 큐의 뒷부분(rear)에서 이루어집니다.
  • 모든 제거(deletion)은 큐의 앞부분(front)에서 이루어집니다.

https://ko.wikipedia.org/wiki/큐_%28자료_구조%29

 

• 용어(Terminology):
  • Front: The front of queue, where deletions take place or the position of the first item.
  • Rear: The rear of queue, where insertions take place or the next of the last item.
  • EnQueue: Insert an item at the rear.
  • DeQueue: Delete the item at the front.
• 작동(Operations):
  • InitQueue: Make queue empty.
  • IsFull: Check whether queue is full. If queue is the circular queue, check whether front is 0 and rear is MAX_SIZE -1.
  • IsEmpty: Check whether queue is empty.
  • Peek: Read the item at the front.
  • EnQueue: Insert an item at the rear.
  • DeQueue: Remove an item at the front.

https://techdifferences.com/difference-between-linear-queue-and-circular-queue.html

 

Linear Queue의 경우 우리가 빈 공간을 충분히 가지고 있다면 더 이상 요소를 추가할 수 없고, 이미 사용했다가 비운 부분들을 재활용할 수 없습니다. Linear Queue의 마지막 부분을 처음 부분과 연결하여 Circular Queue를 만듦으로써 이를 해결할 수 있습니다.

#define MAX_QUEUE 100

typedef enum {false, true} bool;
typedef int Data;

typedef struct{
	int front, rear;
    Data items[MAX_QUEUE];
}Queue;


void InitQueue(Queue *pqueue);
bool IsFull(Queue *pqueue);
bool IsEmpty(Queue *pqueue);
Data Peek(Queue *pqueue);
void EnQueue(Queue *pqueue, Data item);
void DeQueue(Queue *pqueue);

void InitQueue(Queue *pqueue){
	pqueue->front = pqueue->rear = 0;
}

bool IsFull(Queue *pqueue){
	return pqueue->front == (pqueue->rear+1) % MAX_QUEUE;
}

bool IsEmpty(Queue *pqueue){
	return pqueue->front == pqueue->rear;
}

Data Peek(Queue *pqueue){
	if(IsEmpty(pqueue))
    	exit(1);
    return pqueue->items[pqueue->front];
}

void Enqueue(Queue *pqueue, Data item){
	if(Isfull(pqueue))
    	exit(1);
    pqueue->items[pqueue->rear] = item;
    pqueue->rear = (pqueue->rear+1) % MAX_QUEUE;
}

void DeQueue(Queue *pqueue){
	if(IsEmpty(pqueue))
    	exit(1);
    pqueue->front = (pqueue->front+1) % MAX_QUEUE;
}

 

Deque

• 끝과 앞에 둘 다 넣고 뺄 수 있는 Queue
• Double-ended queue that generalizes a queue
  • Enqueue for both front and rear
  • Dequeue for both front and rear
• Operations:
  • InitDeque: make deque empty.
  • IsFull: check whether deque is full.
  • IsEmpty: check whether deque is empty.
  • AddFront: Insert an item at the front.
  • AddRear: Insert an item at the rear.
  • RemoveFront: Delete an item at the front.
  • RemoveRear: Delete an item at the rear.
  • PeekFront: Read the item at the front.
  • PeekRear: Read the item at the rear.

#define MAX_QUEUE 100

typedef enum {false, true} bool;
typedef int Data;

typedef struct{
	int front, rear;
    Data items[MAX_QUEUE];
}Queue;


void InitQueue(Queue *pqueue);
bool IsFull(Queue *pqueue);
bool IsEmpty(Queue *pqueue);
Data PeekFront(Queue *pqueue);
Data PeekRear(Queue *pqueue);
void AddFront(Queue *pqueue, Data item);
void AddRear(Queue *pqueue, Data item);
void RemoveFront(Queue *pqueue);
void RemoveRear(Queue *pqueue);

void InitQueue(Queue *pqueue){
	pqueue->front = pqueue->rear = 0;
}

bool IsFull(Queue *pqueue){
	return pqueue->front == (pqueue->rear+1) % MAX_QUEUE;
}

bool IsEmpty(Queue *pqueue){
	return pqueue->front == pqueue->rear;
}

Data PeekFront(Queue *pqueue){
	if(IsEmpty(pqueue))
    	exit(1);
    return pqueue->items[pqueue->front];
}

Data PeekRear(Queue *pqueue){
	if(IsEmpty(pqueue))
    	exit(1);
    return pqueue->items[pqueue->rear];
}

void AddFront(Queue *pqueue, Data item){
	if(Isfull(pqueue))
    	exit(1);
    pqueue->items[pqueue->front] = item;
    pqueue->front = (pqueue->front+1) % MAX_QUEUE;
}

void AddRear(Queue *pqueue, Data item){
	if(Isfull(pqueue))
    	exit(1);
    pqueue->items[pqueue->rear] = item;
    pqueue->rear = (pqueue->rear+1) % MAX_QUEUE;
}

void RemoveFront(Queue *pqueue){
	if(IsEmpty(pqueue))
    	exit(1);
    pqueue->front = (pqueue->front+1) % MAX_QUEUE;
}

void RemoveRear(Queue *pqueue){
	if(IsEmpty(pqueue))
    	exit(1);
    pqueue->rear = (pqueue->rear+1) % MAX_QUEUE;
}