06. 큐

큐 개요

• Queue는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료구조
• PUSH(데이터 삽입), POP(데이터 삭제) 등의 연산

큐의 연산 과정 (배열)

큐의 구현 (배열)

#include <stdio.h>
#define SIZE 10000
#define INF 99999999

// 큐 선언
int queue[SIZE];
int front = 0;
int rear = 0;

// 큐 삽입 함수
void push(int data) {
	if (rear >= SIZE) {
		printf("Queue overflow\n");
		return;
	}
	queue[rear++] = data;
}

// 큐 추출 함수
int pop() {
	if (front == rear) {
		printf("Queue underflow\n");
		return -INF;
	}
	return queue[front++];
}

// 큐 전체 출력 함수
void show() {
	printf("=== 큐 입구 ===\n");
	for (int i = front; i < rear; i++) {
		printf("%d\n", queue[i]);
	}
	printf("=== 큐 출구 ===\n");
}

int main(void) {
	push(7);
	push(5);
	push(4);
	pop();
	push(6);
	pop();
	show();
	system("pause");
	return 0;
}

큐의 연산 과정 - 삽입 (연결 리스트)

큐의 연산 과정 - 추출 (연결 리스트)

큐의 구현 (연결 리스트)

#include <stdio.h>
#include <stdlib.h>
#define INF 99999999

// 큐 선언
typedef struct {
	int data;
	struct Node* next;
} Node;

typedef struct {
	Node* front;
	Node* rear;
	int count;
} Queue;

// 큐 삽입 함수
void push(Queue* queue, int data) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = NULL;
	if (queue->count == 0) {
		queue->front = node;
	}
	else {
		queue->rear->next = node;
	}
	queue->rear = node;
	queue->count++;
}

// 큐 추출 함수
int pop(Queue* queue) {
	if (queue->count == 0) {
		printf("Queue underflow\n");
		return -INF;
	}
	Node* node = queue->front;
	int data = node->data;
	queue->front = node->next;
	free(node);
	queue->count--;
	return data;
}

// 큐 전체 출력 함수
void show(Queue* queue) {
	Node* cur = queue->front;
	printf("=== 큐 입구 ===\n");
	while (cur != NULL) {
		printf("%d\n", cur->data);
		cur = cur->next;
	}
	printf("=== 큐 출구 ===\n");
}

int main(void) {
	Queue queue;
	queue.front = queue.rear = NULL;
	queue.count = 0;
	push(&queue, 7);
	push(&queue, 5);
	push(&queue, 4);
	pop(&queue);
	push(&queue, 6);
	pop(&queue);
	show(&queue);
	system("pause");
	return 0;
}