📕 스택은, 쌓아놓은 더미. 창고에 쌓여있는 상자 더미를 생각하면 편하다. 상자를 쌓을때는 맨 윗부분에 올려두게 되고, 상자가 필요하면 맨 윗부분에서 가져간다. 만약 중간에 있는 상자를 가져가면 전체 상자가 붕괴된다. (LIFO : Last - in - First - out)
💡컴퓨터 안에서 일어나는 수많은 함수 호출에 스택이 사용된다. 즉, 스택은 돌아가야할 주소를 기억하는데 사용된다.
스택의 연산
(1) push(s, item): 스택의 맨 위에 item 을 추가
(2) pop(s): 스택의 맨 위 item을 제거해서 반환한다.
(3) peek(s): 스택의 맨위 item을 제거하지 않고 반환한다.
스택의 구현
스택의 요소를 저장할 배열
가장 최근에 입력된 자료를 가리키는 top 변수,
만약 스택이 비어있으면 top = -1 (top이 0이 될 경우 배열 [0]에 값이 있다는 것을 의미하게 되버린다.)
만약 스택이 꽉 차있으면 top = N-1;이다. (배열은 0~부터 N-1)까지
1. 스택을 전역 변수로 구현하는 방법
<#include <stdio.h>
#include <stdlib.h>
#define N 100 //스택의 최대 크기기
typedef int element; //저장할 데이터의 자료형
element stack[N]; //데이터가 저장될 배열
int top=-1; // 스택의 최신 요소를 가리키는 변수수
int isEmpty()
{
return top == -1;
}
int isFull()
{
return top == N-1;
}
void push(element e)
{
if(isFull())
{
printf("Overflow!!\n");
return;
}
else
stack[++top] = e;
}
element pop()
{
if(isEmpty())
{
printf("Underflow!!\n");
}
else
{
return stack[top--];
}
}
element peek()
{
if(isEmpty())
{
printf("Underflow!!\n");
}
else
{
return stack[top];
}
}
int main()
{
push(1);
push(2);
push(3);
printf("%d\n",pop());
printf("%d\n",pop());
printf("%d\n",pop());
}
(2) 스택의 요소를 구조체로 하기
스택에 저장되어야 하는 값이 정수나 문자가 아니고, 더 많은 정보들 (학생의 학번, 이름, 주소 등)이 필요하면 스택에 구조체를 저장하면 된다. 구조체 안에 필요한 모든 정보를 넣는다.
#include <stdio.h>
#include <stdlib.h>
#define N 100 //스택의 최대 크기
#define M 100 //스트링의 최대 크기기
typedef struct {
int student_no;
char name[M];
char address[M];
}element;
element stack[N];
int top = -1;
int isEmpty()
{
return top == -1;
}
int isFull()
{
return top == N-1;
}
void push(element e)
{
if(isFull())
{
printf("Overflow!!\n");
return;
}
else
stack[++top] = e;
}
element pop()
{
if(isEmpty())
{
printf("Underflow!!\n");
}
else
{
return stack[top--];
}
}
element peek()
{
if(isEmpty())
{
printf("Underflow!!\n");
}
else
{
return stack[top];
}
}
int main()
{
element ie = {20190001, "hong", "seoul"};
element oe;
push(ie);
oe=pop();
printf("학번: %d\n", oe.student_no);
printf("이름: %s\n", oe.name);
printf("주소: %s\n", oe.address);
}(3) 관련된 데이터를 함수의 매개변수로 전달하는 방법
전역변수로 구현하면, 쉽지만 stack배열과 top이 전역변수로 선언되기 때문에 하나의 프로그램에서 여러 개의 스택을 동시에 사용하기가 어렵다. 따라서 top과 stack배열을 하나의 구조체로 결합시키고 이 구조체의 포인터를 함수로 전달한다.
StackType이라는 새로운 구조체 타입을 만들고 구조체에 대한 퐆인터를 각 함수의 매개변수로 전달하면 쉽게 여러개의 스택을 만드는 것이 가능해진다.
#include <stdio.h>
#include <stdlib.h>
#define N 100 //스택의 최대 크기
typedef int element;
typedef struct StackType
{
int top;
element stack[N];
}StackType;
void init(StackType* S)
{
S->top = -1;
}
int isFull(StackType* S)
{
return S->top == N-1;
}
int isEmpty(StackType* S)
{
return S->top == -1;
}
void push(StackType* S, element e)
{
if(isFull(S))
{
printf("Overflow!\n");
return;
}
else
{
S->top++;
S->stack[S->top]=e;
}
}
element pop(StackType* S)
{
if(isEmpty(S))
{
printf("Underflow!\n");
}
else
{
return S->stack[S->top--];
}
}
element peek(StackType* S)
{
if(isEmpty(S))
{
printf("Underflow!\n");
}
else
{
return S->stack[S->top];
}
}
void print(StackType* S)
{
if(isEmpty(S))
{
printf("Stack is Empty!\n");
return;
}
for(int i=0;i<=S->top;i++)
{
printf("[%d] => ", S->stack[i]);
}
printf("\b\b\b \n");
}
int main()
{
StackType S;
init(&S);
push(&S, 10); print(&S);
push(&S, 20); print(&S);
push(&S, 30); print(&S);
printf("[%d] is deleted! After: ", pop(&S)); print(&S);
printf("[%d] is deleted! After: ", pop(&S)); print(&S);
printf("[%d] is deleted! After: ", pop(&S)); print(&S);
return 0;
}💡 값 전달 방식이면 구조체의 원본이 전달되는 것이 아니라 구조체의 복사본이 함수에 전달되기 때문에 원본에 영향이 없다. 하지만 원본에 대한 포인터를 매개변수로 넘겼기 때문에 원본을 변경할 수 있다.
(4) 스택을 동적 메모리 할당으로 생성하는 방법
...
int main()
{
StackType *S;
S = (StackType *)malloc(sizeof(StackType));
init(S);
push(S, 10); print(S);
push(S, 20); print(S);
push(S, 30); print(S);
printf("[%d] is deleted! After: ", pop(S)); print(S);
printf("[%d] is deleted! After: ", pop(S)); print(S);
printf("[%d] is deleted! After: ", pop(S)); print(S);
free(S);
return 0;
}