[c언어/자료구조] 스택과 순차 큐의 특징, 원형 큐의 특징(삽입 삭제시 빅오 표기법) ,일상에서 큐의 사용

순차 Queue

초

1. 선입선출 FIFO

2.지정된 첫번째 원소 마지막 원소를 Front, rear를 통해 지목할 수 있습니다.

-> 데이터가 들어올 경우 rear를 증가시킨 후,그 자리에 데이터가 들어갑니다.

=> 가장 최근에 들어간 데이터가 가장 마지막에 삭제됩니다.

3. 지정된 front, rear위치를 통해서만 삽입(rear)과 삭제(front)가 이루어집니다.

4. 큐에있는 첫 번째 원소의 이전자리는 front가 해당됩니다.(front==-1시작이므로,)

초기상태 : front==rear==-1 

공백상태: front==rear

포화상태 : rear= n-1( n =마지막index) 

삽입연산시 ++rear;

삭제 연산시 ++front;

	삽입연산	해당위치	삭제연산	해당위치
Stack	push	top	pop	top
Queue	enQueue	rear	deQueue	front

데이터의 삽입과 삭제, 모든 연산처리가 한 곳top에서만 이루어지는 Stack의 단점을 보완한 것이

바로 순차Queue입니다.

하지만 

순차Queue에도 몇가지의 단점이 있습니다.

 

 

○ 순차Q의 단점

1. 원소 이동작업이 상당히 복잡합니다 => 효율성 down

2. 원소 삭제 시 ++front되므로 이전 공간을 활용하지 못합니다.

 

"빈 공간"을 활용하지 못한다는 점입니다.

이를 보완한 것이 원형Queue, 데크입니다.

---

원형Queue

원형 큐란 큐의 MaxIndex를 기준으로 (++rear)mod MaxIndex ==0일 경우 다시 큐의 첫 index인 0에 값을 저장하는 방식입니다.  mod연산자를 사용하기 때문에 마지막인덱스에 값을 저장후 또 값을 저장하게 된다면 mod연산자를 사용해

front부분이 포화상태, 공백상태인지 아닌지를 파악한 후 값을 저장하는 형식입니다.

"                                                     

나머지 연산자 mod란?

ex) 4 mod 3 ==  4 % 3

즉  4를 3으로 나눈 나머지 1 값이 되는 것입니다.

ex2) 4 mod 4 == 4%4 = 0

                                                                  "

초기상태 : front == rear ==0;

공백상태, 포화상태 : front==rear

※ 원형 큐는 front가 있는 자리 하나를 비워두어야 한다. ( 공백상태와 포화상태를 쉽게 구분하기 위해)

-> if(rear+1 mod n == front)

인 경우 포화상태! -> 데이터 저장 불가.

 

다음 코드는 원형 큐에서 주로 사용되는 함수들입니다. //간단한 코드리뷰를 달았습니다.

enQueue (삽입) ,deQueue(삭제), 상황에따라서 deQueue했을때의 원소가 무엇인지 peek(삭제원소), 

printQ(원형 큐에 저장된 모든 원소 출력)

이있습니다.

#include <stdio.h>
#include <stdlib.h>
#define cQ_SIZE 4

typedef char element;
typedef struct {
	element queue[cQ_SIZE];
	int front, rear;
}QueueType;

QueueType *createQueue() {
	QueueType *cQ;
	cQ = (QueueType *)malloc(sizeof(QueueType));
	cQ->front = cQ->rear = 0;
	return cQ;
}

int isEmpty(QueueType *cQ) {
	if (cQ->front == cQ->rear) { // front==rear일 경우 공백상태이므로
		printf("\n Circular Queue is empty!");
		return 1; //1을 반환합니다.
	}
	else return 0;
}
int isFull(QueueType *cQ) { //원형Queue는 공백상태와 포화상태를 쉽게 구분하기 위해 front의 자리를 항상 비워둡니다.
	if (((cQ->rear + 1) % cQ_SIZE) == cQ->front) //만약 추가할 데이터가 front의 자리라면?
	{
		printf("\n Circular Queue is full!");
		return 1;
	}
	else return 0;
}

void enQueue(QueueType*cQ, element item) {
	if (isFull(cQ))
		return; //포화상태 or 공백상태가 아닌지 검사후
	else { //rear가 큐의 max Index일 경우 mod연산자를 수행하여 rear값을 1증가시킨후
		cQ->rear = (cQ->rear + 1) % cQ_SIZE;
		cQ->queue[cQ->rear] = item; //원형큐에 item을저장합니다.
	}
}
element deQeueu(QueueType *cQ) {
	if (isEmpty(cQ))
		exit(1);
	else {
		cQ->front = (cQ->front + 1) % cQ_SIZE;
		return cQ->queue[cQ->front];
	}
}
element peek(QueueType *cQ) {
	if (isEmpty(cQ))
		exit(1);
	else
		return cQ->queue[cQ->front + 1] % cQ_SIZE; //+1을 하는 이유는 front 한 자리는 비워두어야 하기 때문입니다.
}
void printQ(QueueType* cQ) {
	int i, first, last;
	first = (cQ->front + 1) % cQ_SIZE;
	last = (cQ->rear + 1) % cQ_SIZE;
	printf("\n Circluar Queue : [");
	i = first;
	while (i != last) {
		printf("%3c", cQ->queue[i]);
		i = (i + 1) % cQ_SIZE;
	}
	printf("]\n");
}

원형Queue의 특징

1. 논리적인 순차Q의 '빈 공간' 이라는 포화상태의 문제를 보완했습니다.

2. 순차Q의 특징(front, rear)을 이어받아 선입선출FIFO의 구조입니다.

3. 배열을 사용하고, 1개의 원소 삽입시 1개의 rear값 증가 형태로 선형 자료구조에 속합니다.

4. 원소,  자료의 삽입과 삭제는 모두 O(1)시간에 수행됩니다. ( front , rear를 통해 바로 데이터를 삭제, 추가할 수 있기 때문입니다.)

5. 운영체제의 작업 스케줄링에 적합합니다.

 

연결리스트를 통한 원형 Q의 구현에도 front는 첫번째원소, rear는 마지막원소를 가리키고 있을 경우가 가장 효율적인 구조에 해당됩니다.

 

일상에서 사용되는 큐의 예

 100명 한정!!! 아이폰 1+1 행사 당일 apple store에 들어가기 위해 줄 서있는 사람들