스택의 구현과 사용
스택(Stack)이란 ?
-
데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다.
-
가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.
-
스택에 데이터를 넣는 작업을 푸시(Push), 꺼내는 작업을 팝(Pop)이라고 한다.
-
푸시, 팝을 하는 위치를 꼭대기(Top)라 하고 가장 밑바닥 부분을 바닥(Bottom)이라고 한다.
위 사진과 같이 테이블에 겹겹이 쌓은 접시처럼 데이터를 넣는 작업도 꺼내는 작업도 위쪽부터 수행한다.
이전에 함수 포인터에 대해 설명하며 스택 프레임을 설명한적이 있었는데 이와 같이 함수를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다.
void x(){}
void y(){}
void z(){
x();
y();
}
void main(){
z();
}위와 같은 구조의 함수에서 일어나는 일을 간단하게 나타하자면 이렇게 된다.
1. main 함수를 푸시
2. z 함수를 푸시
3. x 함수를 푸시 -> 팝
4. y 함수를 푸시 -> 팝
5. z 함수 팝
6. main 함수 팝이처럼 후입 선출로 데이터를 넣고 꺼내는 식 즉 스택을 사용해 함수가 실행된다.
스택 구조 덕분에 x 함수가 종료되기 전에 main 함수로 돌아가는 일은 없다.
스택 구현하기
IntStack.h 헤더 만들기
#ifndef와 #endif
개발자는 컴파일 단계에서 중복 헤더를 방지하도록 설계해야한다.
그 방법 중 하나로 ifndef와 endif를 사용한다
ifndef는 "If not defined"의 약자로 "~을 정의(define)하지 않았다면" 이라는 뜻이다.
즉 __IntStack를 #define 문장으로 정의하지 않았다면 #endif 문장 앞 내용들을 포함시키라는 뜻이다.
IntStack.h 헤더 구현
#ifndef ___IntStack
#define ___IntStack
typedef struct{
int max; //스택의 용량
int ptr; //스택 포인터
int *stk; //스택의 첫 요소에 대한 포인터
}IntStack;
int Initialize(IntStack *s, int max); //스택 초기화
int Push(IntStack *s, int x); //푸시
int Pop(IntStack *s, int *x); //팝
int Peek(IntStack *s, int *x); //꼭대기 엿보기
void Clear(IntStack *s); //비우기
int Capacity(const IntStack *s); //최대 용량
int Size(const IntStack *s); //개수
int IsEmpty(const IntStack *s); //비어 있는지 체크
int IsFull(const IntStack *s); //찼는지 체크
int Search(const IntStack *s, int x); // 검색
void Print(const IntStack *s); //모든 데이터 출력
void Terminate(IntStack *s); //스택 종료
#endif스택의 첫 요소에 대한 포인터 stk
스택으로 푸시된 데이터를 저장할 용도의 배열을 가리키는 포인터이다.
배열의 메모리 공간 할당은 Initialize 함수로 생성된다.
스택의 최대 용량 max
스택의 최대용량을 나타내고, 배열 stk의 요소 개수와 같다.
스택 포인터 ptr
스택에 쌓여 있는 데이터의 개수를 나타내는 값을 스택 포인터라고 한다.
스택이 비어있으면 0, 가득 차 있으면 max이다.
함수 구현하기
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
int Initialize(IntStack *s, int max){
s->ptr = 0;
if((s->stk = calloc(max, sizeof(int))) == NULL){
s->max = 0;
return -1; //배열 생성 실패
}
s->max = max;
return 0;
}
int Push(IntStack *s, int x){
if(s->ptr >= s->max) return -1; //스택이 가득 찬 경우
s->stk[s->ptr++] = x;
return 0;
}
int Pop(IntStack *s, int *x){
if(s->ptr <= 0) return -1; //스택이 비어있는 경우
*x = s->stk[--s->ptr];
return 0;
}
int Peek(IntStack *s, int *x){
if(s->ptr <= 0) return -1;
*x = s->stk[s->ptr - 1];
return 0;
}
void Clear(IntStack *s){
s->ptr = 0;
}
int Capacity(const IntStack *s){
return s->max;
}
int Size(const IntStack *s){
return s->ptr;
}
int IsEmpty(const IntStack *s){
return s->ptr <= 0; //참이면 1 반환 아닐 시 0 반환
}
int IsFull(const IntStack *s){
return s->ptr >= s->max;
}
int Search(const IntStack *s, int x){
for(int i = s->ptr-1; i >= 0; i--){
if(s->stk[i] == x) return i;
return -1;
}
}
void Print(const IntStack *s){
int i;
for(int i = s->ptr-1; i >= 0; i--){
printf("%d\n", s->ptr[i]);
}
}
void Terminate(IntStack *s){
if(s->stk != NULL) free(s->stk); //배열을 삭제
s->max = s->ptr = 0;
}s->ptr == s->max 또는 !=와 같은 방법으로 스택이 찼는지 비었는지 확인할 수도 있다.
하지만 이 코드에서는 오류 등으로 ptr값이 0보다 작아지거나 max보다 커져버리는 경우를 방지하고자 부등호를 사용해 스택을 확인한다.
Clear 함수에서 배열의 요소들을 삭제하지 않는 이유는 스택의 푸시와 팝이 ptr 값을 바탕으로 실행되기 때문이다.
Search 함수는 선형 검색을 이용해 꼭대기부터 검색한다. 검색을 꼭대기부터 실행하는 이유는 먼저 팝되는 데이터를 찾기 위해서이다.
스택을 사용하는 메인 함수 구현
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
int Initialize(IntStack *s, int max){
s->ptr = 0;
if((s->stk = calloc(max, sizeof(int))) == NULL){
s->max = 0;
return -1; //배열 생성 실패
}
s->max = max;
return 0;
}
int Push(IntStack *s, int x){
if(s->ptr >= s->max) return -1; //스택이 가득 찬 경우
s->stk[s->ptr++] = x;
return 0;
}
int Pop(IntStack *s, int *x){
if(s->ptr <= 0) return -1; //스택이 비어있는 경우
*x = s->stk[--s->ptr];
return 0;
}
int Peek(IntStack *s, int *x){
if(s->ptr <= 0) return -1;
*x = s->stk[s->ptr - 1];
return 0;
}
void Clear(IntStack *s){
s->ptr = 0;
}
int Capacity(const IntStack *s){
return s->max;
}
int Size(const IntStack *s){
return s->ptr;
}
int IsEmpty(const IntStack *s){
return s->ptr <= 0; //참이면 1 반환 아닐 시 0 반환
}
int IsFull(const IntStack *s){
return s->ptr >= s->max;
}
int Search(const IntStack *s, int x){
for(int i = s->ptr-1; i >= 0; i--){
if(s->stk[i] == x) return i;
return -1;
}
}
void Print(const IntStack *s){
int i;
for(int i = s->ptr-1; i >= 0; i--){
printf("%d\n", s->stk[i]);
}
}
void Terminate(IntStack *s){
if(s->stk != NULL) free(s->stk); //배열을 삭제
s->max = s->ptr = 0;
}
void main(){
IntStack s;
int value;
printf("생성할 배열의 크기 : ");
scanf("%d", &value);
if(Initialize(&s, value) == -1){
puts("스택 생성 실패");
}
while(1){
int menu, x; //사용자 선택 수 저장하는 menu와 입력값이나 출력값 저장하는 x
printf("\n현재 데이터 수 : %d / %d \n", Size(&s), Capacity(&s));
printf("(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : ");
scanf("%d", &menu);
if(menu == 0) break;
switch(menu){
case 1:
printf("데이터 : ");
scanf("%d", &x);
if(Push(&s, x) == -1) puts("푸시 실패");
break;
case 2:
if(Pop(&s, &x) == -1) puts("팝 실패");
else printf("팝 데이터는 %d\n", x);
break;
case 3:
if(Peek(&s, &x) == -1) puts("피크 실패");
else printf("피크 데이터는 %d\n", x);
case 4:
Print(&s);
break;
}
}
Terminate(&s);
}
--------------------------------------
실행 결과
생성할 배열의 크기 : 100
현재 데이터 수 : 0 / 100
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 1
데이터 : 1
현재 데이터 수 : 1 / 100
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 1
데이터 : 2
현재 데이터 수 : 2 / 100
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 1
데이터 : 3
현재 데이터 수 : 3 / 100
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 1
데이터 : 4
현재 데이터 수 : 4 / 100
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 4
4
3
2
1
현재 데이터 수 : 4 / 100
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 2
팝 데이터는 0
현재 데이터 수 : 3 / 100
(1)푸시 (2)팝 (3)피크 (4)출력 (0)종료 : 4
3
2
1이 코드를 짜면서 하나의 배열을 공유하여 양쪽에서 스택을 쌓는 코드도 구현해보고 싶어 시도해봤다.
하나의 배열을 공유하는 2개의 스택 구현
#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"
int Initialize(IntStack *s, int max){
s->ptr = 0;
s->ptrb = max-1; //뒤에서 쌓는 스택의 스택 포인터를 끝으로 지정
if((s->stk = calloc(max, sizeof(int))) == NULL){
s->max = 0;
return -1; //배열 생성 실패
}
s->max = max;
return 0;
}
int Push(IntStack *s, int x){
if(s->ptr >= s->ptrb) return -1; //스택이 가득 찬 경우
s->stk[s->ptr++] = x;
return 0;
}
int Push_Back(IntStack *s, int x){
if(s->ptrb <= s->ptr) return -1; //스택이 가득 찬 경우
s->stk[s->ptrb--] = x;
return 0;
}
int Pop(IntStack *s, int *x){
if(s->ptr <= 0) return -1; //스택이 비어있는 경우
*x = s->stk[--s->ptr];
return 0;
}
int Pop_Back(IntStack *s, int *x){
if(s->ptrb >= s->max-1) return -1; //스택이 비어있는 경우
*x = s->stk[++s->ptrb]; //뒤로 이동
return 0;
}
int Peek(IntStack *s, int *x){
if(s->ptr <= 0) return -1;
*x = s->stk[s->ptr - 1];
return 0;
}
int Peek_Back(IntStack *s, int *x){
if(s->ptrb >= s->max-1) return -1; //max를 절반으로 놓았으니 다시 늘려서 반영
*x = s->stk[s->ptrb + 1];
return 0;
}
int Size(const IntStack *s){
return s->ptr;
}
int Size_Back(const IntStack *s){
return s->max-s->ptrb-1;
}
int Capacity(const IntStack *s){
return s->max;
}
void Print(const IntStack *s){
int i;
for(int i = s->ptr-1; i >= 0; i--){
printf("%d\n", s->stk[i]);
}
}
void Print_Back(const IntStack *s){
int i;
for(int i = s->ptrb+1; i <= s->max-1; i++){
printf("%d\n", s->stk[i]);
}
}
void Print_Stack(const IntStack *s){
int i;
for(int i = s->max-1; i >= 0; i--){
printf("%d\n", s->stk[i]);
}
}
void Terminate(IntStack *s){
if(s->stk != NULL) free(s->stk); //배열을 삭제
s->max = s->ptr = s->ptrb = 0;
}
void main(){
IntStack s;
int value;
printf("생성할 배열의 크기 : ");
scanf("%d", &value);
if(Initialize(&s, value) == -1){
puts("스택 생성 실패");
}
while(1){
int menustack, menu, x; //사용자 선택 수 저장하는 menu와 입력값이나 출력값 저장하는 x
printf("\n현재 데이터 수 / 스택1 : %d / 스택 2: %d / 전체용량 : %d \n", Size(&s), Size_Back(&s), Capacity(&s));
printf("(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : ");
scanf("%d", &menustack);
if(menustack == 0) break;
switch(menustack){
case 1:
printf("(1)푸시 (2)팝 (3)피크 (4)출력 : ");
scanf("%d", &menu);
switch(menu){
case 1:
printf("데이터 : ");
scanf("%d", &x);
if(Push(&s, x) == -1) puts("푸시 실패");
break;
case 2:
if(Pop(&s, &x) == -1) puts("팝 실패");
else printf("팝 데이터는 %d\n", x);
break;
case 3:
if(Peek(&s, &x) == -1) puts("피크 실패");
else printf("피크 데이터는 %d\n", x);
break;
case 4:
Print(&s);
break;
}
break;
case 2:
printf("(1)푸시 (2)팝 (3)피크 (4)출력 : ");
scanf("%d", &menu);
switch(menu){
case 1:
printf("데이터 : ");
scanf("%d", &x);
if(Push_Back(&s, x) == -1) puts("푸시 실패");
break;
case 2:
if(Pop_Back(&s, &x) == -1) puts("팝 실패");
else printf("팝 데이터는 %d\n", x);
break;
case 3:
if(Peek_Back(&s, &x) == -1) puts("피크 실패");
else printf("피크 데이터는 %d\n", x);
break;
case 4:
Print_Back(&s);
break;
}
break;
case 3:
Print_Stack(&s);
break;
}
}
Terminate(&s);
}
-------------------------------------
실행 결과
생성할 배열의 크기 : 10
현재 데이터 수 / 스택1 : 0 / 스택 2: 0 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 1
(1)푸시 (2)팝 (3)피크 (4)출력 : 1
데이터 : 1
현재 데이터 수 / 스택1 : 1 / 스택 2: 0 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 1
(1)푸시 (2)팝 (3)피크 (4)출력 : 1
데이터 : 2
현재 데이터 수 / 스택1 : 2 / 스택 2: 0 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 1
(1)푸시 (2)팝 (3)피크 (4)출력 : 1
데이터 : 3
현재 데이터 수 / 스택1 : 3 / 스택 2: 0 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 2
(1)푸시 (2)팝 (3)피크 (4)출력 : 1
데이터 : 1
현재 데이터 수 / 스택1 : 3 / 스택 2: 1 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 2
(1)푸시 (2)팝 (3)피크 (4)출력 : 1
데이터 : 2
현재 데이터 수 / 스택1 : 3 / 스택 2: 2 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 2
(1)푸시 (2)팝 (3)피크 (4)출력 : 1
데이터 : 3
현재 데이터 수 / 스택1 : 3 / 스택 2: 3 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 3
1
2
3
0
0
0
0
3
2
1
현재 데이터 수 / 스택1 : 3 / 스택 2: 3 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 2
(1)푸시 (2)팝 (3)피크 (4)출력 : 2
팝 데이터는 3
현재 데이터 수 / 스택1 : 3 / 스택 2: 2 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 3
1
2
3
0
0
0
0
3
2
1
현재 데이터 수 / 스택1 : 3 / 스택 2: 2 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 2
(1)푸시 (2)팝 (3)피크 (4)출력 : 1
데이터 : 5
현재 데이터 수 / 스택1 : 3 / 스택 2: 3 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 3
1
2
5
0
0
0
0
3
2
1
현재 데이터 수 / 스택1 : 3 / 스택 2: 3 / 전체용량 : 10
(1)스택1 (2)스택2 (3)전체 스택 출력 (0)종료 : 한 배열의 위 아래로 한 스택은 아래에서 위로 한 스택은 위에서 아래로 쌓을 수 있도록하는 코드를 짜보았다.
이 코드를 짜면서 스택에 대한 이해도가 좀 높아진 것 같다.
만들면서 헷갈리기도하고 오류도 자꾸 떠서 어려웠다.
처음엔 max를 2로 나눠 max를 기준으로 움직이게 하려했는데 그러하자 자꾸 max값으로 인한 충돌이 생기고 이상하게 구현된 함수 하나로 전혀 관련없는 push 함수조차 잘 작동하지 않기도 했다. 이 원리가 궁금해 chat gpt에게 물어본 결과 아래와 같이 답하였다.
서로 공유하는 배열에서의 작업은 서로 간섭하지 않도록 조심해야 합니다. 이로 인해 발생하는 문제가 Push 함수에서 푸시 실패로 나타난 것이었습니다.
한번 꼬이니 정말 머리가 복잡해지고 코드 짜기가 어려웠다. 그래서 max를 기준으로 움직이는 틀에서 벗어나 ptr와 ptrb를 비교하는 조건문을 사용함으로써 오류에서 벗어날 수 있었다.
오류는 끝도 없고 언젠가 개발자로 일하며 느낄 스트레스를 느낀 것 같다.
자료구조 코드를 짤땐 무작정 키보드를 치기보단 생각만 한 내용들을 구조도를 그려보고 어떤식으로 코드를 짜야겠다고 생각한 뒤 키보드에 손을 대기 시작해야겠다.
생각보다 내 머리가 좋은편이 아니라는걸 깨달은 날이다. 더 열심히 해야겠다.
