[DataStructures] Stack스택

이 글은 학교 강의(이상호 교수님의 '자료구조')를 듣고 복습과 정리차 작성한 글입니다. 

 

스택(stack ADT스택 추상자료형)이란?

 

후입선출(LIFO: Last-In-First-Out) - 가장 최근에 들어온 데이터가 가장 먼저 제거되는 형태

나는 '책이 쌓여진 형태'를 바탕으로 암기하였을 때 받아들이기 쉬웠다.

이걸 굳이 왜 쓰는가? 교수님의 말에 따르면, 가장 최근에 들어온 데이터는 가장 따끈따끈한 정보를 가지는 데이터로 많이 쓰이기에 스택의 형태를 가지는 경우가 필요하다고 하셨다. 이러한 용도 외에도 스택의 형태 덕분에 괄호검사, 수식 계산, 미로 탐색할 때 알고리즘으로도 자주 사용된다.

출처 : https://dev.to/rinsama77/data-structure-stack-and-queue-4ecd

스택에 쓰이는 함수

 

create(s) ::= 스택 s를 생성한다.

is_empty(s) ::= 스택 s가 비어있는지

is_full(s) ::= 스택 s가 찼는지 확인하기

push(s,e) ::= 스택 s에 원소 e를 삽입한다

pop(s) ::= 스택 s의 원소를 뺀다.(물론 가장 최근에 들어온 데이터)

peek(s) ::= 스택 s의 원소의 값을 뺀다.(물론 이것도 가장 최근에 들어온 데이터를 말한다.) 

 

스택 ADT는 배열과 연결리스트를 통하여 구현할 수 있다.

 

1. 배열을 이용한 stack

 

일단 stack 자체의 구조를 살펴보면,

 

typedef int element;	//stack에 들어가는 원소 하나하나의 형태를 말한다.
//stack을 정의하기 위해서는 stack을 담는 배열과 찼는지의 여부를 확인해주는 변수(top)이 필요하다.
typedef struct{	
	element stack[MAX_LIST_SIZE];	//element형을 가지는 원소로 이루어진 stack이라는 배열 생성
    	int top;
}StackType;

 

이렇게 stack 자체가 stack 이라는 list와 top이라는 변수로 이루어져 있다.

그럼 배열을 이용하여 여러가지 함수들을 구현해보자. stack 자체를 넘겨줄 때 포인터를 이용하여 넘겨준다.

 

//스택 초기화 함수
void init(StackType *s){
	s -> top = -1;
}

int is_empty(StackType *s){
	return (s->top == -1);
}

int is_full(StackType *s){	//포화면 true(1)을 반환
	return (s->top == s-> (MAX_LIST_SIZE-1));
}

void push(StackType *s, element item){
	if(is_full(s)){	//다 차있는지 여부 확인한 후에 삽입해야 함.
		printf("스택 포화 에러");
        exit(1);
    }else{
    	++(s->top);
    	s->stack[top] = item;
    }
}

element pop(StackType *s){
	//비어있는지 여부 확인한 후에 빼내야 함.
    if(is_empty(s)){
    	printf("스택이 비어있습니다.");
        exit(1);
    }else{
    	return s->stack[(s->top)--];
    }
}

element peek(StackType *s){
	if(is_empty(s)){
        printf("스택이 비어있습니다.");
        exit(1);
    }else{
    	return s->stack[s->top];
    }
}

2. 연결리스트를 이용한 'Linked Stack연결 스택'

 

배열에 비해 비교해볼 점은 배열은 MAX_LIST_SIZE를 정해서 개수의 한계가 있지만 연결리스트는 끊임없이 만들어낼 수 있어 용이하다. 하지만 삽입이나 삭제 만들어낼 때 시간이 걸려서 조금 불편한 점이 있다. 자세히 말하자면, 삽입을 할 때 연결리스트이기에 메모리 할당이 하나하나 들어간다는 점이 배열과 크게 다르다.

 

연결 스택의 구조를 살펴보면, Stack Node 하나를 생성하게 됩니다. stack의 맨 앞부분의 포인터를 가리키는 것도 하나 더 생성하게 됩니다.

 

typedef int element;

typedef struct{	//Node 하나를 정의
	element data;
   	StackType *link;
}StackNode;

//연결리스트가 만들어지기 위해 필요한 포인터 top
//포인터 LinkedStackType *s로는 오직 top하나만 접속할 수 있다.
typedef struct{	
	StackNode *top;
}LinkedStackType;

 

push와 pop을 중점적으로 살펴본다면,

 

void push(LinkedStackType *s, element item){	//item 만이 들어오게 되는 상황
	//들여보내기 위해 메모리를 할당하는 과정이 필요하다.
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    if(temp == NULL){
    	printf("메모리 할당 에러");
        exit(1);
    }else{	//포인터를 생성하였으니 item과 top에 연결해야 한다.
    	temp -> data = item;
        temp ->link = s ->top;
        s ->top = temp;
    }
}

element pop(LinkedStackType *s){
	if(is_empty(s)){
    	printf("스택이 비어있습니다.");
        exit(1);
    }else{
    	StackNode *temp = s->top;
        int item = temp ->data;
        s->top = s->top->link;
        free(temp);
        return item;
    }
}

 

긴 글 읽어주셔서 감사합니다!

이 글이 유익하셨다면 밑 버튼을 눌러서 후원하실 수 있습니다:)

Buy me a Milkshake