8 min to read
자료구조(5) - 스택
스택의 ADT를 만들고, 구현
🔚 짧게 하는 복습
✅ 1. 정적 배열로 주어진 ADT를 구현할 수 있다.
✅ 2. 동적 배열로 주어진 ADT를 구현할 수 있다.
✅ 3. 이중 포인터를 이용하는 함수를 이해한다.
✅ 4. []연산자 없이 이중 포인터의 간접 참조를 이용해 배열을 다루는 법을 이해한다.
혹시 기억이 안 난다면, 다시 돌아가자
이번 강의는 선형 자료구조 중 하나인 스택에 대해 다루겠다.
스택이란 이름이 낯설지 않아야 한다. 우리가 메모리 구조를 배울 때, 스택 영역이라는 이야기를 했었다.
그때는 자세하게 몰랐지만, 지금 배우는 자료구조를 이용한 메모리 영역이다.
스택이란 가장 나중에 입력한 원소를 가장 먼저 참조하는 LIFO(Last In First Out)형의 자료구조이다.
위의 그림을 보면 가장 나중에 들어온 원소가, pop이라는 함수 호출 시 가장 먼저 나가는 모습을 알 수 있다.
또한, insert를 해서 가장 나중에 들어온 원소가 top 인덱스로 참조되는 자리에 있음도 알 수 있다.
스택의 가장 큰 특징은 가장 나중에 들어온 원소 말고는 관심이 없다는 점이다.
그렇기에 스택의 ADT를 만들 때는 순회 기능이 없다.
스택 ADT
역시나 ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정이 가능하다.
동적 배열을 통한 스택의 ADT 구현
스택을 구현할 때는 top이라는 인덱스를 만들어, 가장 최근에 들어온 원소를 가리키는 것이 중요하다.
top이라는 인덱스는 스택 전체의 원소 개수이며, 동시에 가장 최근 원소의 인덱스로 스택에서 가장 핵심이라고 할 수 있다.
사실 그것을 제외하면 크게 배열의 구현과 다른 것이 없다.
(오히려 더 간단하다)
#include <stdio.h>
#include <stdlib.h>
/*
자료 : 정수
기능1 삽입 : 원소를 스택에 입력한다.
기능2 수정 : 가장 나중에 입력된 원소의 값을 수정한다.
기능3 삭제 : 가장 나중에 입력된 원소를 스택에서 제거하고 그 원소를 리턴한다.
기능4 조회 : 가장 나중에 입력된 원소의 값을 조회한다.
*/
typedef int* stack; //typedef를 통한 변환
//+ empty한지 확인
int is_empty(const int top) {
if (top == 0) {
return 1; //비었으면 참
}
else {
return 0;//아니면 거짓
}
}
//기능1 삽입
int insert(stack* st, const int value, int* top) {
if (is_empty(*top)) {
*st = (stack)malloc(sizeof(int) * (*top + 1));
}//원소가 없으면 할당
else {
stack new_st = (stack)realloc(*st, sizeof(int) * (*top + 1));
*st = new_st;
}//재할당
*(*st + *top) = value;
printf("%d is pushed into stack!\n\n", value);
*top += 1;
//대입
//top 증가
return 0;
}
//기능2 수정
int update(stack st, const int value, const int top) {
if (is_empty(top)) {
printf("Stack is empty!\n\n");
return -1;
}//원소가 없으면 오류
st[top - 1] = value;
printf("Stack's top value is changed with %d\n\n", value);
return 0;
}
//기능3 제거
int pop(stack* st, int* top) {
if (is_empty(*top)) {
printf("Stack is empty!\n\n");
return -1;
}//원소가 없으면 오류
*top -= 1;// top 감소
int ret = *(*st + *top);// ret값을 미리 저장(재할당을 위해)
if (*top == 0) {
*st = NULL;
}//비었으면 NULL
else {
stack new_st = (stack)realloc(*st, sizeof(int) * (*top));
*st = new_st;
}//아니면 재할당
return ret;// pop한 원소 리턴
}
//기능4 조회
int find_top(stack st, int top) {
if (is_empty(top)) {
printf("Stack is empty!\n\n");
return -1;
}//원소가 없으면 오류
return st[top - 1];// pop한 원소 리턴
}
int main(void) {
stack st = NULL; // 동적 배열을 통한 스택 구현
int top = 0;
/*
배열 구현에서 cur_size 역할, 즉 스택에 얼마나 많은 원소가 있는지를 나타냄
또한, 가장 최근에 입력된 원소의 인덱스 값이기도 함.
*/
insert(&st, 1, &top);
insert(&st, 2, &top);
insert(&st, 3, &top);
printf("top : %d\n\n", find_top(st, top)); // 3
insert(&st, 4, &top);
insert(&st, 5, &top);
printf("top : %d\n\n", find_top(st, top)); // 5
update(st, 3, top);
printf("top : %d\n\n", find_top(st, top)); //3
printf("pop : %d\n", pop(&st, &top)); //3
printf("pop : %d\n", pop(&st, &top)); //4
printf("pop : %d\n", pop(&st, &top)); //3
printf("top : %d\n\n", find_top(st, top)); //2
printf("pop : %d\n", pop(&st, &top)); //2
printf("pop : %d\n", pop(&st, &top)); //1
pop(&st, &top);//오류, -1 반환
free(st);
}
결과창
1 is pushed into stack!
2 is pushed into stack!
3 is pushed into stack!
top : 3
4 is pushed into stack!
5 is pushed into stack!
top : 5
Stack's top value is changed with 3
top : 3
pop : 3
pop : 4
pop : 3
top : 2
pop : 2
pop : 1
Stack is empty!
활용
자료구조 강의를 다소 넘어가는 부분이지만, 꽤 필요한 이야기이므로 읽어볼 거리에 남기겠다.
📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)
✅ 1. 동적 배열로 스택과 주어진 ADT를 구현할 수 있다.
✅ 2. 스택의 활용을 안다.(읽어볼 거리 참고)
⚠️ 사실 대부분의 강의는 완전히 비었을 때 top을 0이 아니라 -1로 한다. 하지만 우리는 동적할당을 편하게 하려고 디폴트값을 0으로 했음을 전한다.
💣 과제,
-
정적배열로 구현도 해보자, 무엇이 장점이고 무엇이 단점인지 잘 생각해보자.(난이도 中)
-
LIFO는 가장 나중에 들어온 원소가 가장 먼저 나가는 구조이다. FIFO는 가장 처음 들어온 원소가 가장 먼저 나가는 구조이다. FIFO는 어떻게 구현해야 할까? (난이도 上)
🔜 더 공부해보기,
Comments