자료구조 스택(Stack) 기초 개념정리

스택(Stack)

스택이란 선형자료구조의 일종으로서 후입선출 방식의 자료구조이다. (LIFO: Last - In, First - Out) 간단하게 생각하면 한쪽만 뚫려있는 통을 생각하면 된다. 이 통에 무언가를 넣고 뺄때 먼저 들어간건이 나중에 나오게 될 것이다. 

스택은 배열 또는 연결리스트를 사용하여 구현이 가능하다. (배열과 연결리스트 모두 선형 자료구조)

---

스택의 ADT

StackInit: 스택의 초기화역활로서, 제일먼저 호출해야한다.

IsEmpty: 스택이 비어있는지 확인하는 역활이다.

Push: 스택에 데이터를 저장하는 역활이다. 매개 변수로 받은 데이터를 저장한다.

Pop: 마지막에 저장된 요소를 삭제 및 반환한다.

Peek: 마지막에 저장된요소를 반환하지만 삭제는 하지않는다. 

 

연결리스트로 구현한 스택 예시

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1		//TRUE는1로 선언
#define FALSE 0		//FALSE는0으로 선언

typedef int Data;		

typedef struct _node		//노드를 정의
{
	Data data;
	struct _node *next;
}Node;

typedef struct _listStack	//스택을 정의
{
	Node* head;
}ListStack;

typedef ListStack Stack;

void StackInit(Stack* pstack)		//스택초기화 함수
{
	pstack->head = NULL;
}

int IsEmpty(Stack* pstack)		//스택이 비어있는지 확인하는 함수
{
	if (pstack->head == NULL)
		return TRUE;
	else
		return FALSE;
}

void Push(Stack* pstack, Data data)		//스택에 데이터를 삽입하는 함수
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;		//매개변수로 받은 데이터를 새로운 노드에 삽입
	newNode->next = pstack->head;

	pstack->head = newNode;		//포인터변수 head가 새로운 노드를 가리킨다.
}

Data Pop(Stack* pstack)		//스택의 데이터를 제거 및 반환한다.
{
	Data rdata;		
	Node* rnode;

	if (IsEmpty(pstack))		//데이터를 제거하기전 스택이 비어있는지 확인해야한다.
	{
		printf("스택이 비어있습니다.");
		exit(1);
	}
	
	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;
	free(rnode);

	return rdata;
}

Data Peek(Stack* pstack)		//스택의 마지막 저장요소 반환 (제거X)
{
	if (IsEmpty(pstack))
	{
		printf("스택이 비었습니다.");
		exit(1);
	}
	return pstack->head->data;

}

int main()		//메인
{
	Stack stack;
	StackInit(&stack);		//스택초기화

	Push(&stack, 1);		//데이터 push
	Push(&stack, 2);
	Push(&stack, 3);
	Push(&stack, 4);
	Push(&stack, 5);

	while (!IsEmpty(&stack))		//모든 데이터 반환 및 제거
	{
		printf("%d ", Pop(&stack));
	}

	return 0;
}