[자료구조] 큐(Queue), 원형 큐, 회문 판정

큐(Queue) : FIFO (First-in-First-Out)

삽입(rear)과 삭제(front)가 다른 장소에서 이루어지는 순서 리스트

 

배열 큐 구현

- 큐 구조 정의

#define Max_Queue_Size 10 // 최대 큐크기
typedef int element;
element queue[Max_Queue_Size];
int rear = -1;
int front = -1;

- 큐의 구현 방식

1) 선형 큐 : 단순 선형 배열로 구현한 큐로 포화 상태(Full)일 경우 배열을 조정해야 한다.

2) 원형 큐 : 선형 큐의 해결방법으로 큐의 시작과 끝이 마치 원으로 연결된 것 같이 사용한다.

   - 원형 큐는 rear과 front를 최초 0에서부터 시작한다.

   - rear = (rear+1) mod MAX_QUEUE_SIZE
   - front = (front+1) mod MAX_QUEUE_SIZE

 

- 공백 상태

int is_empty()
{
	return (front == rear);
}

- 포화 상태

int is_full()
{
	return (front == (rear + 1) % Max_Queue_Size);
}

- 삽입

void enqueue(element item)
{
	if (is_full())	{
		printf("Queue full\n");
		return;
	}
	else {
		rear = (rear + 1) % Max_Queue_Size;
		queue[rear] = item;
	}
}

- 삭제

element dequeue()
{
	if (is_empty())	{
		printf("Queue empty\n");
		return;
	}
	else {
		front = (front + 1) % Max_Queue_Size;
		return queue[front];
	}
}

 

---

응용

회문 판정 (스택&큐 사용)

주어진 입력 문자열이 거꾸로 읽어도 똑같은지 판별하는 문제이다.

(ex) aabbaa : 회문O

        aabbbb : 회문X

입력 받은 문자열을 Stack과 Queue에 한 문자씩 모두 push, euqueue 해준다.
그리고 'Stack에서 pop한 값'과 'Queue에서 dequeue한 값'을 비교하여 서로 다르다면 회문이 아니고,
모든 문자열을 비교하여 Stack과 Queue가 비었을 때까지 서로 같다면 회문이라고 판정한다.

void main()
{
	char temp[MAX_SIZE];

	printf("입력 : ");
	scanf("%s", temp);

	for (int i = 0;i < strlen(temp);i++)
	{
		push(temp[i]);
		enqueue(temp[i]);
	}

	char p1, p2;
	while (true)
	{
		p1 = dequeue();
		p2 = pop();
		if ((p1 == 0) && (p2 == 0))
		{
			printf("회문입니다.\n");
			return;
		}
		else if (p1 != p2)
		{
			printf("회문이 아닙니다.\n");
			return;
		}
	}
}​

전체 소스코드

#include<stdio.h>
#include<string.h>

#define MAX_SIZE 100
typedef char element;
element queue[MAX_SIZE];
int rear = -1;
int front = -1;

element stack[MAX_SIZE];
int top = -1;


void push(char word)
{
	if (top == MAX_SIZE - 1)
	{
		return;
	}
	else
	{
		stack[++top] = word;
	}
}

char pop()
{
	if (top == -1)
		return 0;
	else
		return stack[top--];
}


void enqueue(char word)
{
	if (front == (rear + 1) % MAX_SIZE)
	{
		return;
	}
	else
	{
		rear = (rear + 1) % MAX_SIZE;
		queue[rear] = word;
	}
}

char dequeue()
{
	if (front == rear)
		return 0;
	else
		front = (front + 1) % MAX_SIZE;
		return queue[front];
}


void main()
{
	char temp[MAX_SIZE];

	printf("입력 : ");
	scanf("%s", temp);

	for (int i = 0;i < strlen(temp);i++)
	{
		push(temp[i]);
		enqueue(temp[i]);
	}

	char p1, p2;
	while (true)
	{
		p1 = dequeue();
		p2 = pop();
		if ((p1 == 0) && (p2 == 0))
		{
			printf("회문입니다.\n");
			return;
		}
		else if (p1 != p2)
		{
			printf("회문이 아닙니다.\n");
			return;
		}
	}
}