자료구조 : 스택(Stack)

Stack(스택) 자료구조

 

구현언어 : C/C++

사용한 IDE : 비주얼 스튜디오

 

스택은 먼저들어온 데이터가 가장 나중에 나가는 형태의 자료구조입니다.

반대로 말하면 가장 나중에 들어온 데이터가 가장 처음으로 나가게 됩니다.

이러한 자료구조를 LIFO(Last in first out)라고도 말합니다.

 

 

스택 형태 상상해보기

 

 

 

스택은 한쪽이 막혀있는 통의 형태입니다. 통속에 무언가를 넣었을 때 한쪽이 막혀있기 때문에, 처음에 넣은 것을 빼려면 위에 쌓여 있는 다른 것들을 다 빼야 합니다. 아래는 예시 그림입니다.

예를 들어서 위의 그림처럼 한쪽이 막혀있는 통에 숫자가 적혀있는 네모를 1->2->3 순서대로 넣었을 때,

통속에 있는 상자를 다시 빼려면 3->2->1 순으로 나오게 됩니다.

용어 설명

 

 

스택의 ADT를 정의해 보겠습니다.

(ADT : 구체적인 구현에 대해서는 설명하지 않고, 어떤 기능인지 나열하는 것, 일종의 동작에 대한 설명서)

 

<기능>

Pop(팝) : 스택에서 데이터를 하나 꺼낸다.

Push(푸쉬) : 스택에 데이터를 집어 넣는다.

Empty : 스택이 비어있는지 확인한다.

Peek(픽) 또는 Top(탑) : 스택에서 제일 위에 있는 데이터를 확인한다. Pop처럼 데이터를 꺼내지는 않고,

                               확인만 한다.

 

위의 4가지가 스택의 기본적인 동작들이고, 그 외의 것들은 개발자가 필요하다면 정의를 합니다.

저는 추가적으로 stack의 size를 알 수 있는 기능을 추가 했습니다.

 

Size : 스택의 현재 데이터의 수를 반환

 

구현

 

여기서는 C/C++로 구현을 할 예정입니다.

스택의 개념만 잘 알고 있다면, 다른 언어로도 충분히 구현이 가능합니다.스택은 크게 배열 또는 연결리스트를 이용해서 스택을 구현할 수 있습니다.여기서는 동적할당을 할 수 있는 연결리스트를 이용해서 스택을 구현하겠습니다.

 

우선은 데이터의 단위인 노드와 스택을 정의합니다.스택에는 스택의 앞부분을 가리킬 head와 데이터의 수를 세는 변수를  아래와 같이 선언합니다.

 

//연결리스트로 stack 구현

typedef struct _node
{
	int data;
	struct _node* next=NULL;
}Node;

typedef struct _stack
{
	Node* head = NULL;
	int numOfData = 0; //stack에 존재하는 data의 수 표시

}Stack;

 

기본적으로 필요한 도구들을 만들었고, 이제는 스택의 기능들을 구현하겠습니다.

 

<Push>

//push 함수
void push(Stack* pstack, int data)
{
	if (pstack->head == NULL) //stack이 비어있는 경우
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->next = NULL;
		pstack->head = newNode;
		pstack->head->data = data;
		(pstack->numOfData)++;
	}
	else //stack이 비어있지 않는 경우에 head부분에 새로운 노드 추가
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->next = NULL;
		newNode->data = data;
		newNode->next = pstack->head;
		pstack->head = newNode;
		(pstack->numOfData)++;
	}
}

 

<Pop>

//pop연산
int pop(Stack* pstack)
{
	Node* removeNode;
	int removeData;

	//stack이  비어있는 경우 -1을 반환
	if (pstack->head == NULL) return -1;

	removeNode = pstack->head; //삭제할 노드 
	removeData = pstack->head->data; //삭제할 노드의 데이터
	pstack->head = pstack->head->next; //삭제할 노드의 그 다음 노드를 head가 가리킴.

	free(removeNode); //할당해제
	(pstack->numOfData)--; //data의 개수 하나 감소
	return removeData; 
}

 

<empty>

int empty(Stack* pstack)
{
	if (pstack->head == NULL) return 1; //비어있다면 1 반환
	else return 0; //비어있지 않다면 0 반환
}

 

<Top>

//stack의 제일 위에 있는 data 반환
int top(Stack* pstack)
{	
	if (pstack->head == NULL) return -1; //반환할 data가 없다면 -1 리턴
	else return pstack->head->data;
}

 

<Size>

//stack의 size 반환
int size(Stack* pstack)
{
	return pstack->numOfData;
}

 

구현한 스택을 테스트

 

위에서 구현한 스택을 main함수에서 테스트 해봅시다.

 

<main>

int main()
{
	Stack stack;
	stack.head = NULL; //stack의 head를 NULL로 초기화
	
	push(&stack, 1); //1을 push
	push(&stack, 2); //2를 push
	push(&stack, 3); //3을 push

	
	printf("%d \n",pop(&stack));  //3이 나옴 
	printf("%d \n",pop(&stack));  //2가 나옴
	printf("%d \n",pop(&stack));  //1이 나옴


	//혹시나 모를 메모리 누수를 막기 위해서 확실하게 할당 해제
	while (!(stack.head == NULL))
	{
		Node* remove = NULL;
		remove = stack.head;
		stack.head = stack.head->next;
		free(remove);
	}
	return 0;
}

 

실행결과는 아래와 같습니다.

 

 

 

1->2->3 순서대로 스택에 숫자를 넣었기 때문에, pop을 해보면 넣은 순서와 반대인 3->2->1이 출력이 되는 것을

확인할 수 있습니다.

 

 

<전체코드>

 

#include<stdlib.h>
#include<cstring>
#include<iostream>

using namespace std;

//연결리스트로 stack 구현

typedef struct _node
{
	int data;
	struct _node* next = NULL;
}Node;

typedef struct _stack
{
	Node* head = NULL;
	int numOfData = 0; //stack에 존재하는 data의 수 표시

}Stack;

//push 함수
void push(Stack* pstack, int data)
{
	if (pstack->head == NULL) //stack이 비어있는 경우
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->next = NULL;
		pstack->head = newNode;
		pstack->head->data = data;
		(pstack->numOfData)++;
	}
	else //stack이 비어있지 않는 경우에 head부분에 새로운 노드 추가
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->next = NULL;
		newNode->data = data;
		newNode->next = pstack->head;
		pstack->head = newNode;
		(pstack->numOfData)++;
	}
}

//pop연산
int pop(Stack* pstack)
{
	Node* removeNode;
	int removeData;

	//stack이  비어있는 경우 -1을 반환
	if (pstack->head == NULL) return -1;

	removeNode = pstack->head; //삭제할 노드 
	removeData = pstack->head->data; //삭제할 노드의 데이터
	pstack->head = pstack->head->next; //삭제할 노드의 그 다음 노드를 head가 가리킴.

	free(removeNode); //할당해제
	(pstack->numOfData)--; //data의 개수 하나 감소
	return removeData;
}

//stack의 size 반환
int size(Stack* pstack)
{
	return pstack->numOfData;
}


//stack이 비어있는지 유무 확인
int empty(Stack* pstack)
{
	if (pstack->head == NULL) return 1; //비어있다면 1 반환
	else return 0; //비어있지 않다면 0 반환
}

//stack의 제일 위에 있는 data 반환
int top(Stack* pstack)
{
	if (pstack->head == NULL) return -1; //반환할 data가 없다면 -1 리턴
	else return pstack->head->data;
}

int main()
{
	Stack stack;
	stack.head = NULL; //stack의 head를 NULL로 초기화
	
	push(&stack, 1); //1을 push
	push(&stack, 2); //2를 push
	push(&stack, 3); //3을 push

	
	printf("%d \n",pop(&stack));  //3이 나옴 
	printf("%d \n",pop(&stack));  //2가 나옴
	printf("%d \n",pop(&stack));  //1이 나옴


	//혹시나 모를 메모리 누수를 막기 위해서 확실하게 할당 해제
	while (!(stack.head == NULL))
	{
		Node* remove = NULL;
		remove = stack.head;
		stack.head = stack.head->next;
		free(remove);
	}
	return 0;
}

 

 

 

위의 코드는 아래 깃 허브 링크에 올려 두었습니다.

github.com/Ewlrma/data_structure/tree/main/Stack

Ewlrma/data_structure