[C언어][자료구조] 스택(Stack)

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

FIFO, LIFO

---

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

 

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

 

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

 

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

 

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

 

스택(Stack), 큐(Queue)

---

 

Queue는 줄서기, Stack은 책을 쌓아놓은 느낌

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

 

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

 

먼저 온 사람(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를 살펴보겠습니다.