[자료구조] Stack이란? Stack의 특징, C언어로 구현

▶Stack이란?

---

스택은 프링글스통을 생각하면 이해하기 쉽다. 차곡차곡 쌓여져있는 맛있는 프링글스를 생각해보자.

프링글스 HOT & SPICY 맛 맛있다!!

우리는 프링글스의 위에서부터 꺼내먹는다. 

즉, 가장 나중에 들어온 프링글스부터 꺼내먹는다.

 

이것을 자료구조에서는 마지막에 추가된 항목이 가장 먼제 제거되는 Last In First Out(LIFO) 데이터 구조라고 부른다.

 

 

 

 

▶스택의 ADT

---

https://suzzeong.tistory.com/106

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• LIFO(Last In First Out) - 나중에 집어넣은 데이터가 먼저 나옴
• 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있음
• 스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서, 이전의 작업 내용을 저장해 둘 필요가 있을 때 사용함

스택의 시간 복잡도

삽입/삭제 : O(1)

검색 : O(N)

 

구현 할 함수

pop() : 스택의 마지막 데이터를 삭제 후 삭제된 데이터 반환

push() : 스택에 데이터 삽입

peek() : 스택의 마지막 데이터 반환

isFull() : 스택이 꽉 찼는지 확인

isEmpty() : 스택이 비었는지 확인

 

 

 

 

 

 

▶C로 구현

---

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
	int itmes[MAX_SIZE];
	int top; //스택의 꼭대기 원소 
} Stack;

int isFull(Stack* s) {
	if(s->top == MAX_SIZE -1) {
		return 1;
	} 
	else {
		return 0;
	}
}

int isEmpty(Stack* s) {
	if(s->top == -1) {
		return 1;
	}
	else {
		return 0;
	}
}

int pop(Stack* s) { //스택의 꼭대기 원소 삭제 후 삭제된 원소 반환 
	if(isEmpty(s) == 1) {
		printf("Stack is Empty\n");
	}
	else {
		int data = s->itmes[s->top];
		s->top --;
		return data;
	}
}

void push(Stack* s, int data){ //스택의 꼭대기에 data 삽입 
	if(isFull(s)==1) {
		printf("Stack is Full\n");
	}
	else {
		s->top ++;
		s->itmes[s->top] = data;
	}
}

int peek(Stack* s) { //스택의 꼭대기원소 반환 
	if(isEmpty(s) == 1) {
		printf("Stack is Empty\n");
	}
	else {
		int data = s->itmes[s->top];
		return data;
	}
}


int main() {
	Stack s;
	s.top = -1; //Stack 초기화
	
	push(&s, 10); 
	push(&s, 20);
	push(&s, 30);
	push(&s, 40);
	push(&s, 50);
	
	printf("현재 Top 원소 : %d\n", peek(&s));
	printf("제거 된 원소 : %d\n", pop(&s));
	printf("현재 Top 원소 : %d\n", peek(&s));
	printf("제거 된 원소 : %d\n", pop(&s));
	printf("현재 Top 원소 : %d\n", peek(&s));
	
	return 0;
}

딱히 크게 생각을 안해도 함수의 역할만 알고 코드를 짤 수 있을정도로 쉽게 구현가능하다.

 

위에서부터 차근차근 알아보자

typedef struct {
	int itmes[MAX_SIZE];
	int top; //스택의 꼭대기 원소 
} Stack;

우선 구조체 하나를 typedef해주었다.

items는 스택 역할의 선형 배열이고 top은 스택의 꼭대기 원소를 가리키는 변수이다.

 

 

int isFull(Stack* s) {
	if(s->top == MAX_SIZE -1) {
		return 1;
	} 
	else {
		return 0;
	}
}

int isEmpty(Stack* s) {
	if(s->top == -1) {
		return 1;
	}
	else {
		return 0;
	}
}

isFull과 isEmpty 함수이다.

받은 구조체 s의 top(스택의 꼭대기 원소)이 배열의 크기 -1 이라면 스택이 꽉 찬것(top이 꼭대기에 있다는 뜻)이고,

받은 구조체 s의 top이 -1이라면 스택이 비어있는것이다.

 

 

int pop(Stack* s) { //스택의 꼭대기 원소 삭제 후 삭제된 원소 반환 
	if(isEmpty(s) == 1) {
		printf("Stack is Empty\n");
	}
	else {
		int data = s->itmes[s->top];
		s->top --;
		return data;
	}
}

스택의 꼭대기 원소를 삭제한 후 삭제한 값을 반환하는 함수 pop이다.

우선 스택이 비어있으면 반환할 게 없으므로 스택이 비어있는지 isEmpty함수로 체크해준 후

비어있지 않다면 data변수에 스택 s의 꼭대기 원소의 데이터를 담아두고,

top을 한칸 내려준다. 그 후 담아뒀던 data를 반환해주면 된다.

그림으로 나타내면 이렇게 되는건데

72를 삭제해준다는게 진짜 값을 없애는게 아니라

어짜피 72자리에 push하면 push된 값이 72를 덮어버리기 때문에 top의 위치만 --해줘도 삭제가 되는것이다.

 

 

void push(Stack* s, int data){ //스택의 꼭대기에 data 삽입 
	if(isFull(s)==1) {
		printf("Stack is Full\n");
	}
	else {
		s->top ++;
		s->itmes[s->top] = data;
	}
}

스택 s에 data를 삽입해주는 함수이다.

우선 스택이 꽉 차있으면 삽입을 못하기때문에 isFull함수로 체크를 해준 후

꽉 차지 않았다면 우선 s의 top을 하나 증가시키고

전달받은 data를 스택 s에 삽입한다.

 이렇게 되는 것이다.

 

 

int peek(Stack* s) { //스택의 꼭대기원소 반환 
	if(isEmpty(s) == 1) {
		printf("Stack is Empty\n");
	}
	else {
		int data = s->itmes[s->top];
		return data;
	}
}

peek함수는 스택의 꼭대기원소의 데이터를 반환하는 함수이다.

pop에서 top을 하나 줄여주는것만 빼면 된다.

 

 

int main() {
	Stack s;
	s.top = -1; //Stack 초기화
	
	push(&s, 10); 
	push(&s, 20);
	push(&s, 30);
	push(&s, 40);
	push(&s, 50);
	
	printf("현재 Top 원소 : %d\n", peek(&s));
	printf("제거 된 원소 : %d\n", pop(&s));
	printf("현재 Top 원소 : %d\n", peek(&s));
	printf("제거 된 원소 : %d\n", pop(&s));
	printf("현재 Top 원소 : %d\n", peek(&s));
	
	return 0;
}

main함수까지 작성 후 실행해보면

이렇게 실행결과가 나오게된다.

 

 

만약 스택의 크기를 동적할당해주고 싶다면

typedef struct {
	int* items;
	int maxSize;
	int top;
} DynamicStack;

//스택 초기화
void initStack(DynamicStack* s, int initSize) {
	s->items = (int*)malloc(initSize * sizeof(int));
	s->maxSize = initSize;
	s->top = -1;
} 

//스택 해체
void freeStack(DynamicStack* s) {
	free(s->items);
	s->items = NULL;
	s->maxSize = 0;
	s->top = -1;
} 

//스택 크기 조절
void resizeStack(DynamicStack* s, int newSize) {
	s->items = (int*)realloc(s->items, newSize * sizeof(int));
	s->maxSize = newSize;
}

이렇게 함수를 짜주면 된다.