Queue와 Stack은 ADT (Abstract Data Type) 이다.

Queue

(FIFO) First In First Out

'줄' 과 원리가 같다. 버스를 타기 위해 줄을 서면 맨 앞사람이 먼저 버스에 타고, 새로 온 사람은 줄 맨 뒤에 서야한다. 가장 먼저 들어온 데이터가 가장 먼저 나가고 (Dequeue), 새로 들어온 데이터는 맨 뒤에 추가(Enqueue)된다. 양 끝 (rear/front)에서 삽입(Enqueue), 삭제(Dequeue)가 이루어진다.

Circular Queue

삽입과 삭제가 같은장소에서 일어나는 Stack과 달리 Queue는 맨 앞과 맨 뒤에서 삽입 삭제가 일어난다. 포화상태의 Stack이 있다고 가정해보자. 새로운 요소를 추가하기 위해 기존에 있는 요소를 Pop(삭제)하고, 새로운 요소를 Push(삽입)하면 된다. (가장 최근에 추가된 기존요소가 삭제되고 그 자리에 새로운 요소가 삽입된다) 포화상태의 Queue가 있다고 생각해보자. 앞서와 마찬가지로 새로운 요소를 삽입하기 위해 기존의 요소를 삭제(Dequeue)하고 새로운 요소를 삽입(Enqueue)한다. 여기서 문제가 발생한다. Queue에서 삭제(Dequeue)는 Queue의 맨 앞(가장 먼저 들어온 요소)에서, 삽입(Enqueue)은 Queue의 맨 뒤 (가장 나중에 들어온 요소 뒤)에서 이루어진다. 새로운 요소를 삽입하기 위해 포화된 Queue에서 기존의 요소를 삭제하였지만, Queue의 특성상 새로운 노드는 맨 마지막 노드뒤에 삽입되기 때문에 요소가 삽입될 자리가 없다. 즉 Overflow 가 발생한다. 이런 문제를 해결하기 위해 제안된것이 원형 큐(Circular Queue)이다. 큐의 맨 앞과 맨 뒤를 이어 동그랗게 만들어준다. 아까와 같은 상황에서 비어있는 큐의 맨앞이 마치 큐의 맨 뒤의 다음인것처럼 생각하는 것이다.

Stack

(LIFO) Last In First Out

웹 브라우저에서 뒤로가기를 떠올리면 이해하기가 쉽다. 뒤로가기 버튼을 누르면 맨 처음 방문했던 사이트가 아닌 바로 전에 방문했던 사이트로 돌아간다. 한 쪽 끝(Top)에서 삽입(Push)과 삭제(Pop)가 이루어진다.

Stack 응용

Stack이 적용된 예로는 Recursive function (재귀함수)가 있다. 재귀함수는 함수 내에서 자기 자신을 호출하는 함수를 말하며, 호출할 때마다 Stack에 쌓인다. Factorial 계산기를 이용해 재귀함수를 알아보자.

#include <stdio.h>

int factorial(int n) { 
	
	if (n == 0) {
		return 1;
		//결과를 아는 0!이 될때까지 
		//0 ! = 1
	}
	else
	{
		return n * factorial(n - 1);
	}
}

void main() {
	printf("Factorial calculator\nInsert n :");

	int n;
	scanf_s("%d", &n);
	int result = factorial(n);

	printf("%d! = %d", n, result);
}