티스토리 뷰
스택(Stack)이란?
쌓아놓은 더미라는 뜻. 데이터를 바닥에서부터 쌓아 올리는 구조.
스택에서 데이터 입/출력은 오로지 스택의 꼭대기에서만 이루어진다. 스택의 맨 아래에 있는 데이터를 꺼내려면 그 위에 있는 데이터를 모두 걷어내야 한다.
이처럼 스택은 가장 마지막에 들어간 데이터가 제일 먼저 나오는 LIFO(Last In - First Out : 후입선출) 형태를 띤다. 요소의 삽입과 삭제가 한쪽 끝에서만 이루어지는 것이 스택의 특징이다.
스택의 연산은 Push, Pop이 있다.
Push 함수는 스택에 데이터를 추가한다.
// 삽입
void push(StackType *S, element e)
{
if (is_full(S))
printf("Overflow\n");
else
{
S->top++; // top을 하나 증가시킨후
S->data[S->top] = e; // 데이터를 삽입한다
}
}
Pop 함수는 스택에서 데이터를 삭제하고, 그 데이터를 반환한다.
// 삭제
element pop(StackType *S)
{
if (is_empty(S))
{
printf("Empty\n");
return -1;
}
else
{
element e = S->data[S->top]; // 가장 상위에 있는 데이터를 e에 저장한 후
S->top--; // top을 하나 감소시킨다
return e;
}
}
Peek는 스택에서 데이터를 삭제하지 않고 들여다 보기만 하는 함수이다. pop과 마찬가지로 스택의 비어있음을 체크한다.
// 조회
element peek(StackType *S)
{
if (is_empty(S))
{
printf("Empty\n");
return -1;
}
else
{
return S->data[S->top];
}
}Push, Pop, Peek 구현하기
#include <stdio.h>
#define SIZE 100
typedef int element;
typedef struct
{
element data[SIZE];
int top;
} StackType;
// 초기화
void init(StackType *S)
{
S->top = -1;
}
// 에러 체크 함수
int is_empty(StackType *S)
{
return S->top == -1;
}
int is_full(StackType *S)
{
return S->top == SIZE - 1;
}
// 삽입
void push(StackType *S, element e)
{
if (is_full(S))
printf("Overflow\n");
else
{
S->top++;
S->data[S->top] = e;
}
}
// 삭제
element pop(StackType *S)
{
if (is_empty(S))
{
printf("Empty\n");
return -1;
}
else
{
element e = S->data[S->top];
S->top--;
return e;
}
}
// 조회
element peek(StackType *S)
{
if (is_empty(S))
{
printf("Empty\n");
return -1;
}
else
{
return S->data[S->top];
}
}
void print(StackType *S)
{
for (int i = 0; i <= S->top; i++)
{
printf("%c ", S->data[i]);
}
printf("\n");
}
int main()
{
StackType S;
init(&S);
pop(&S);
push(&S, 'a');
push(&S, 'b');
push(&S, 'c');
print(&S);
element p = pop(&S);
printf("%c\n", p);
print(&S);
}
'자료구조' 카테고리의 다른 글
| [자료구조] 스택 프레임 (Stack Frame) (0) | 2024.02.11 |
|---|