C언어 스택 큐 - Ceon-eo seutaeg kyu

※ 이 글은 C언어 기준으로 작성하였습니다.

FIFO, LIFO

스택과 큐에 대해 알아보기 전에 FIFO와 LIFO에 대해 알아봅시다.

FIFO(First In, First Out, 선입선출)란 먼저 입력된 원소가 우선적으로 출력되는 기법입니다.

대표적인 예시로 Queue가 있습니다.

반대로 LIFO(Last In, First Out, 후입선출)은 가장 최근에 입력된 원소가 우선적으로 출력되는 기법입니다.

대표적인 예시로 Stack이 있습니다.

스택(Stack), 큐(Queue)

큐는 줄서기를 하는 것과 같습니다.

왼쪽에 줄을 선 사람들이 있습니다. 저들이 새치기를 하지 않는 이상

먼저 온 사람(First In)부터 게이트를 통과(First Out)하게 됩니다.

사람들을 원소로 바꾸게 되면 큐가 됩니다.

스택은 책쌓기와 같습니다. 전 팝콘에 비유하기도 합니다.

오른쪽에 책이 쌓여있습니다. 쌓을 때, 맨 밑 책이 먼저 놓여졌지만,

치울 때는 맨 위 책부터 옮겨집니다.

여러분이 팝콘을 먹을 때, 팝콘의 맨 윗부분(Last In)부터 먹게(First Out) 됩니다.

책과 팝콘을 원소로 바꾸게 되면 스택이 됩니다.

Code

#include <stdio.h>
#include <stdlib.h> //exit 함수 사용 

#define MAX_STACK_SIZE 5 //스택의 크기 설정
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1; //stack이 비어있을 때, -1을 반환하도록 함

//stack이 비어있는지 확인합니다.  
int is_empty()
{
	return (top == -1);
}

//stack이 꽉 찼느지 확인합니다.  
int is_full()
{
	return (top == MAX_STACK_SIZE-1); 
}

//stack에 입력값을 삽입합니다. 
void push(element item)
{
	if (is_full()) //포화 상태 확인 
	{
		fprintf(stderr, "stack full error\n");
		return;
	}
	else stack[++top] = item;
}

//stack에서 값을 꺼냅니다. 
element pop()
{
	if (is_empty()) //공백 상태 확인
	{
		fprintf(stderr, "stack empty error\n");
		exit(1); 
	}
	else return stack[top--];
}

//stack에서 peek 값을 출력합니다.
element peek()
{
	if (is_empty())
	{
		fprintf(stderr, "stack empty error\n");
		exit(1);
	}
	else return stack[top];
}

int main()
{
	push(10);
	push(5);
	push(9);
	push(12);
	push(6);
	
	printf("peek : %d\n", peek()); //6 출력 
	printf("pop : %d\n", pop()); //6 출력 
	printf("peek : %d\n", peek()); //12 출력 
}

MAX_STACK_SIZE : 배열의 최대 크기를 선언합니다.

typedef int element : element라는 자료형을 선언합니다. 

top : 가장 최근에 들어온 원소의 위치를 표시하는 변수입니다. 

배열이 비어있을 때, -1 값을 가집니다.

int is_empty()
{
	return (top == -1);
}

is_empty : 배열이 공백상태인지 확인합니다.

int is_full()
{
	return (top == MAX_STACK_SIZE-1); 
}

is_full : 배열이 포화상태인지 확인합니다.

배열은 0부터 시작하니 포화상태라면 MAX_STACK_SIZE - 1 값을 가져야합니다.

void push(element item)
{
	if (is_full()) //포화 상태 확인 
	{
		fprintf(stderr, "stack full error\n");
		return;
	}
	else stack[++top] = item;
}

push : 배열에 입력값을 삽입합니다.

is_full함수를 사용하여 포화상태라면 값이 입력되지 않도록 합니다.

top에 1을 더해줍니다.

element pop()
{
	if (is_empty()) //공백 상태 확인
	{
		fprintf(stderr, "stack empty error\n");
		exit(1); 
	}
	else return stack[top--];
}

pop : top이 가르키는 값을 꺼냅니다.

is_empty함수를 사용하여 공백상태라면 값이 출력되지 않도록 합니다.

top에 1을 빼줍니다.

element peek()
{
	if (is_empty())
	{
		fprintf(stderr, "stack empty error\n");
		exit(1);
	}
	else return stack[top];
}

peek : top이 가르키는 값을 출력합니다.

is_empty함수를 사용하여 공백상태라면 값이 출력되지 않도록 합니다.

top은 건드리지 않습니다.

pop과 peek의 차이

stack이 책을 쌓아놓은 것과 같다고 했습니다.

여기서 pop은 맨 위의 책을 치우는 것입니다.

그럼 그 밑에 있는 책이 맨 위로 올라오겠죠?

반면에 peek는 맨 위의 책의 제목만 확인하는 것입니다.

그 책은 여전히 맨 위에 있으니 변동이 없습니다.

Code with string

#include <stdio.h>
#include <stdlib.h> //exit 사용 

#define MAX_STACK_SIZE 5 //스택의 크기 설정
typedef char * element;
element stack[MAX_STACK_SIZE];
int top = -1; //stack이 비어있을 때, -1을 반환하도록 함

//stack이 비어있는지 확인합니다.  
int is_empty()
{
	return (top == -1);
}

//stack이 꽉 찼느지 확인합니다.  
int is_full()
{
	return (top == MAX_STACK_SIZE-1); 
}

//stack에 입력값을 삽입합니다. 
void push(element item)
{
	if (is_full()) //포화 상태 확인 
	{
		fprintf(stderr, "stack full error\n");
		return;
	}
	else stack[++top] = item;
}

//stack에서 값을 꺼냅니다. 
element pop()
{
	if (is_empty()) //공백 상태 확인
	{
		fprintf(stderr, "stack empty error\n");
		exit(1); 
	}
	else return stack[top--];
}

//stack에서 peek 값을 출력합니다.
element peek()
{
	if (is_empty())
	{
		fprintf(stderr, "stack empty error\n");
		exit(1);
	}
	else return stack[top];
}

int main()
{
	push("김하나");
	push("이둘");
	push("박서이");
	push("한너이");
	push("조다섯");
	
	printf("peek : %s\n", peek()); //6 출력 
	printf("pop : %s\n", pop()); //6 출력 
	printf("peek : %s\n", peek()); //12 출력 
}

이외에도 구조체를 사용하여 다양한 stack을 구현할 수 있습니다.

다음 글에서는 queue의 code를 살펴보겠습니다.

큐(Queue) 란?

큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 

스택은 아래 부분이 막히고 윗 부분이 뚫린 통과 같았다면, 큐는 양 쪽이 뚫린 통과 같다. 스택이 가장 윗부분에서 데이터를 넣고 꺼냈다면, 큐는 front 에서 Dequeue(데이터를 꺼냄) 연산이 진행되고, rear 부분에서 Enqueue(데이터를 넣음) 연산이 진행된다.

c언어 구현

큐는 배열 혹은 연결리스트로 구현할 수 있다. 배열로 구현할 시에는 여러가지 문제점이 발생할 수 있다. 여기서는 연결리스트를 이용해 큐를 구현해보도록 한다. 

1. 노드 정의, 큐 초기화

가장 먼저 노드를 정의하고, Queue 구조체를 정의한다. 큐를 초기화 하는 initQueue() 함수를 이용해 front와  rear를 Null로 초기화하고, 큐 안의 노드 개수를 나타내는 count를 0으로 초기화한다.

2. isEmpty() 함수

큐에서 데이터를 뽑아낼 때 큐가 비어있다면 오류가 발생할 수 있다. 따라서 큐가 비어있는지 확인하는 함수인 isEmpty()가 필요하다.

큐가 비어있는지 확인하는 함수는 두 가지 방법을 사용할 수 있다. 첫 번째는 queue->front == NULL &&          queue->rear==NULL 이라면 큐가 비어있는 상태이다. front와 rear가 초기 상태(빈 상태), 즉 NULL 일 때는 큐가 비어있을 때뿐이기 때문이다. 두 번째는 큐 안의 노드 개수가 0이라면 큐가 빈 상태인것이다. 여기서는 두 번째 방식을 사용했다.

3. 큐의 데이터 삽입, enqueue() 함수

큐의 데이터 삽입은 rear 부분, 즉 큐의 맨 뒤에서 발생한다. 가장 먼저 새로운 노드를 만들어 data를 할당하고, 이후 큐에 집어넣는다.

코드를 보고 이해가 가지 않는다면 다음 그림을 보자.

큐가 비어있을 때 데이터를 삽입하면, front와 rear가 동일하게 newNode를 가리키게 된다. 

큐가 비어있지 않을 때 데이터를 삽입하면 front는 가장 앞의 노드를 가리키고 rear는 가장 뒤의 노드 즉, 방금 삽입한 노드를 가리키게 된다. 이는 다음과 같은 과정을 거쳐서 이루어진다.

1. newNode 생성

2. rear의 next 가 newNode를 가리키도록 설정

3. rear가 newNode를 가리키도록 설정

next 포인터가 enqueue 되는 방향과 반대로 설정되는게 어색할 수도 있으나, 이는 dequeue 연산을 위해서다. dequeue 연산에서 자세히 보도록 하자.

4. 큐의 데이터 반환, dequeue() 함수

큐에서 데이터 반환은 큐의 맨 앞 front 에서 발생한다. 

큐가 비어 있을 경우에는 데이터 반환을 할 수 없으므로 오류 메시지를 출력한다. 큐가 비어 있지 않다면 맨 앞의 노드의 데이터를 반환하고, 해당 노드를 free 시켜준다. 이후 큐의 노드 개수를 1 감소 시킨다.

큐가 비어있지 않을 경우 데이터를 반환하는 과정을 그림으로 자세히 알아보자.

가장 먼저 ptr이 큐의 front를 가리키도록 한다. 이 때 반환할 데이터를 따로 저장한다. (여기서는 로컬 변수 int data)

이후 front 가 ptr->next를 가리키도록 한다. 이를 위해서 enqueue 과정에서 next 포인터를 역방향으로 설정한 것이다.

이후 ptr을 free(메모리 해제)시켜주고, 큐의 노드 개수를 1감소시킨다. 마지막으로 따로 저장한 data를 반환하면 dequeue 과정이 완료된다.

전체 소스코드

실행결과