큐(Queue) 2

선형 큐(Linear Queue)

자바로 나타낸 선형큐이다.

예전 게시글 참조.

2024.07.23 - [Algorithm] - 큐 (queue)

큐 (queue)

class QueueType {
	int MAX_QUEUE_SIZE = 5;
	int front;
	int rear;
	int data[] = new int[MAX_QUEUE_SIZE];

	public void error(String message) {
		System.out.printf("%s", message);
		System.exit(1);
	}

	public void init_queue(QueueType q) {
		q.rear = -1;
		q.front = -1;
	}

	public void queue_print(QueueType q) {
		for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
			if (i <= q.front || i > q.rear)
				System.out.printf("\t|\t");
			else
				System.out.printf("%d\t|\t", q.data[i]);
		}
		System.out.println();
	}

	public boolean is_full(QueueType q) {
		if (q.rear == MAX_QUEUE_SIZE - 1) {
			return true;
		} else
			return false;
	}

	public boolean is_empty(QueueType q) {
		if (q.front == q.rear) {
			return true;
		} else
			return false;
	}

	public void enqueue(QueueType q, int item) {
		if (is_full(q)) {
			error("큐과 포화상태입니다.");
			return;
		} else
			q.data[++(q.rear)] = item;
	}

	public int dequeue(QueueType q) {
		if (is_empty(q)) {
			error("큐가 공백상태입니다.");
			return -1;
		} else {
			int item;
			item = q.data[++(q.front)];
			return item;
		}
	}
}

public class Queue {
	public static void main(String[] args) {
		int item = 0;

		QueueType q = new QueueType();
		q.init_queue(q);

		q.enqueue(q, 10);
		q.queue_print(q);
		q.enqueue(q, 20);
		q.queue_print(q);
		q.enqueue(q, 30);
		q.queue_print(q);

		item = q.dequeue(q);
		q.queue_print(q);
		item = q.dequeue(q);
		q.queue_print(q);
		item = q.dequeue(q);
		q.queue_print(q);

	}
}

이를 바탕으로 여러가지 선형큐를 활용한 알고리즘 문제를 해결할 수 있다. class QueueType 에 public 메소드를 추가.

10/10,20/10,20,30/ enqueue /20,30/30 dequeue

---

원형 큐(Circular Queue)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 7
typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front;
	int rear;
}QueueType;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}
void init_queue(QueueType* q) {
	q->front = 0;
	q->rear = 0;
}
int is_empty(QueueType* q) {
	return (q->front == q->rear);
}
int is_full(QueueType* q) {
	return (q->front == ((q->rear + 1) % MAX_QUEUE_SIZE));
}
void queue_print(QueueType* q) {
	printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % MAX_QUEUE_SIZE;
			printf("%d	|	", q->data[i]);
			if (i == q->rear) {
				break;
			}
		} while (i != q->front);
	}
	printf("\n");
}
void enqueue(QueueType* q, element item) {
	if (is_full(q)) {
		error("큐가 포화 상태입니다.");
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("큐가 공백 상태입니다.");
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}
element peek(QueueType* q) {
	if (is_empty(q)) {
		error("큐가 공백 상태입니다.");
	}
	return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}

int main()
{
	QueueType queue;
	int element;

	init_queue(&queue);
	printf("--데이터 추가 단계--\n");
	while (!is_full(&queue))
	{
		printf("정수를 입력하시오: ");
		scanf("%d", &element);
		queue_print(&queue);
		enqueue(&queue, element);
		queue_print(&queue);
	}
	printf("큐는 포화 상태입니다.\n\n");

	printf("--데이터 삭제 단계--\n");
	while (!is_empty(&queue)) 
	{
		element = dequeue(&queue);
		printf("꺼내진 정수: %d \n", element);
		queue_print(&queue);
	}
	printf("큐는 공백 상태입니다.\n");
	return 0;
}

q->front = (q->front + 1) % MAX_QUEUE_SIZE;

q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;

위와 같은 방식으로 순환을 나타낸다.

원형큐의 성질

• 원형 큐에서는 큐 하나씩은 항상 비워둔다.
• 초기단계에서의 front,rear는 모두 0이다.
• front는 첫번째 요소 하나 앞을, rear는 마지막 요소를 가리킨다.
• enqueue시 rear가 하나 먼저 증가된 후 그 공간에 삽입된다.
• dequeue시 front가 하나 먼저 증가된 후 그 공간에 있는 것을 삭제한다.
• MAX_QUEUE_SIZE-1이 마지막 큐의 공간인데 이를 넘어서면 rear=(rear+1)%MAX_QUEUE_SIZE로 순환한다.       (MAX_QUEUE_SIZE가 7인경우 예시 : 0,1,2,3,4,5,6,0) 

 

MAX_QUEUE_SIZE=7인 경우