스택(Stack)과 큐(Queue), 순환 큐(Circular Queue)

스택(Stack)

스택(Stack)은 LIFO(Last In First Out)을 표현하는 대표적인 선형 자료구조 이다. 나중에 입력한 값이 먼저 출력되는 구조이다. 

그래서 일반적인 스택은 top이라는 하나의 공간을 통해 입출력이 일어난다. 배열을 통해서 많이 표현하는데 아래와 같이 표현할 수 있다.

출처 https://www.programiz.com/dsa/stack

위와 같이 top이라는 하나의 공간을 통해 값을 입력, 출력한다.

• 삽입은 top이 가르키는 공간의 다음 공간으로 이동하여 삽입한다.
• 삭제는 top이 가르키는 공간의 자료를 꺼낸뒤 top은 이전 공간으로 이동한다.
• top이 -1일 경우 STACK은 비어있는 상태이다.
• top이 배열의 마지막 공간을 가르키고 있을 경우 STACK은 가득찬 상태이다.

---

스택(Stack) 구현

#include <stdio.h>

#define MAX_SIZE 10

int stack[MAX_SIZE];
int top = 0;

// 삽입
void push(int v) {
	// 삽입 불가
	if (top > MAX_SIZE) {
		printf("(ERROR) STACK FULL\n");
	}
	// 삽입 가능
	else {
		stack[top++] = v;
		printf("STACK PUSH : %d\n", v);
	}
}

// 삭제
int pop() {
	// 삭제 불가
	if (top <= 0) {
		printf("(ERROR) STACK EMPTY\n");
	}
	// 삭제 가능
	else {
		printf("STACK POP : %d\n", stack[--top]);
	}
}

// 스택 출력
void stack_print() {
	printf("현재 STACK : ");
	for (int i = 0; i < top; i++) {
		printf("%d ", stack[i]);
	}
	printf("\n");
}

void main() {

	// 콘솔 핸들링
	int menu = 0;
	int value = 0;

	// 메인 로직
	while (menu <= 3) {
		stack_print();
		printf("\n메뉴\n1.삽입(PUSH)\n2.삭제(POP)\n3.종료(EXIT)\n\n");

		scanf_s("%d", &menu);

		switch (menu) {
			// 삽입
		case 1:
			printf("PUSH 값 입력: ");
			scanf_s("%d", &value);
			push(value);
			break;

			// 삭제
		case 2:
			printf("POP 수행");
			pop();
			break;

			// 종료
		case 3:
			menu = 4;
			break;
		}
	}

}

---

큐(Queue), 순환 큐(Circular Queue)

큐(Queue)는 FIFO(First In First Out)의 입출력을 표현하는 대표적인 선형자료 구조이다. 먼저 입력한 값이 먼저 출력되는 구조이다.

그래서 일반적인 선형 큐는 출력을 담당하는 Front와 입력을 담당하는 Rear, 이 두가지 공간으로 입출력이 일어난다.

 

출처 https://chanhuiseok.github.io/posts/algo-26/

표현하자면 위와 같다. 그런데 이러한 선형 큐는 입출력을 반복하다보면 Front도 뒤로가고 Rear도 뒤로가서 결국 아래처럼 공간을 하나밖에 사용하지 못하게 된다. 즉, 사이즈 5의 배열 중 1 개의 공간밖에 사용하지 못하여 메모리 낭비가 일어난다. 이러한 부분을 보완하고자, 환형 큐의 개념이 등장하였다.

출처 https://chanhuiseok.github.io/posts/algo-26/

 

환형 큐는 이 Front와 Rear를 원형으로 돌린다.

아래와 같이 인덱스를 원형으로 돌려서 7 -> 0 으로 가도록 %연산을 통해 가르킨다.

 

삽입과 삭제의 과정을 표현하면 위와 같다.

 

• 삽입은 Rear가 가르키는 다음 공간으로 이동하여 값을 넣는다.
• 삭제는 Front가 가르키는 다음 공간으로 이동하여 값을 제한다.
• 비어있을 경우는 두 포인터가 같은 공간을 가르킬 경우이다.
• 모두 차있을 경우는 Rear의 다음 공간이 Front일 경우이다.

 

단, 단순히 위의 로직으로 구현했을 때 비어있을 경우와 모두 차있을 경우 모두 Front와 Rear가 같은 공간을 가르켜 구분이 가지 않는다. 이를 위해, 한 공간을 비워두고 표현한다.

---

순환 큐 구현

#include <stdio.h>

#define MAX_SIZE 11

int queue[MAX_SIZE];
int rear = 0;
int front = 0;

// 삽입
void push(int v) {
	// 삽입 불가
	if ((rear+1)% MAX_SIZE == front ) {
		printf("(ERROR) QUEUE FULL\n");
	}
	// 삽입 가능
	else {
		rear = (rear + 1) % MAX_SIZE;
		queue[rear] = v;
		printf("QUEUE PUSH : %d\n", v);
	}
}

// 삭제
int pop() {
	// 삭제 불가
	if (front == rear) {
		printf("(ERROR) QUEUE EMPTY\n");
	}
	// 삭제 가능
	else {
		front = (front + 1) % MAX_SIZE;
		printf("QUEUE POP : %d\n", queue[front]);
	}
}

// 순환큐 출력
void queue_print() {
	printf("현재 QUEUE : ");
	for (int i = front+1 ; i <= rear ; i++) {
		printf("%d ", queue[i]);
	}
	printf("\n");
}

void main() {

	// 콘솔 핸들링
	int menu = 0;
	int value = 0;

	// 메인 로직
	while (menu <= 3) {
		queue_print();
		printf("\n메뉴\n1.삽입(PUSH)\n2.삭제(POP)\n3.종료(EXIT)\n\n");

		scanf_s("%d", &menu);

		switch (menu) {
			// 삽입
		case 1:
			printf("PUSH 값 입력: ");
			scanf_s("%d", &value);
			push(value);
			break;

			// 삭제
		case 2:
			printf("POP 수행");
			pop();
			break;

			// 종료
		case 3:
			menu = 4;
			break;
		}
	}

}