스택
스택
- 스택(stack)은 한쪽으로 들어가서 한쪽으로 나오는 자료 구조(Data Structure)
- 이러한 특성 때문에 수식 계산 등의 알고리즘에서 다방면으로 활용됨
push : 스택에 데이터를 넣음
pop : 스택에서 데이터를 빼냄
push(7) - push(5) - push(4) - pop() - push(6) - pop()
7 5
스택의 구현
- 스택(stack)은 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어짐
- 가장 기본적인 형태의 자료구조로 구현 난이도는 낮은 편
배열을 이용한 스택 구현
* 스택의 선언
#define SIZE 10000 // 전체 스택의 크기
#define INF 99999999
int size[SIZE];
int top = -1; // 스택의 최 상단을 의미 하는 변수 top
* 스택 삽입 함수
- 오버플로우 : 데이터가 넘친다, 데이터가 들어갈 수 없을 만큼 스택이 가득 찼다
void push(int data) {
if (top == SIZE - 1) { // 만약 top이 size -1이라면(9999라면)
printf("스택 오버플로우 발생. \n");
return;
}
stack[++top] = data;
}
* 스택 추출 함수
int pop() {
if (top == -1) { // top이 -1이라면
printf("스택 언더플로우 발생. \n");
return -INF;
}
return stack[top--];
}
* 스택 전체 출력 함수
void show() {
printf("--- 스택의 최상단 ---\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
printf("--- 스택의 최하단 ---\n");
}
* 완성된 스택 사용하기
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000 // 전체 스택의 크기
#define INF 99999999
int stack[SIZE];
int top = -1; // 스택의 최 상단을 의미 하는 변수 top
void push(int data) {
if (top == SIZE - 1) { // 만약 top이 size -1이라면(9999라면)
printf("스택 오버플로우 발생. \n");
return;
}
stack[++top] = data;
}
int pop() {
if (top == -1) { // top이 -1이라면
printf("스택 언더플로우 발생. \n");
return -INF;
}
return stack[top--];
}
void show() {
printf("--- 스택의 최상단 ---\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
printf("--- 스택의 최하단 ---\n"); // 가장 먼저 들어온 값
}
int main(void) {
push(7); // 가장 먼저 들어온 값
push(5);
push(4);
pop();
push(6);
pop();
show();
system("pause");
return 0;
}
연결 리스트를 이용한 스택 구현
* 스택의 선언
#define INF 99999999
typedef struct {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
} Stack;
배열을 이용한 스택 구현
- 스택 삽입 과정
1. data next(Top) > data next(일반 노드) > data next(일반 노드) > null
2. data next(Top) > data next(일반 노드) > data next(일반 노드) > null
data next(삽입할 노드)
3. data next(일반 노드) > data next(일반 노드) > data next(일반 노드) > null
data next(Top)
* 스택 삽입 함수
void push(Stack *stack, int data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = stack->top;
stack->top = node;
}
- 스택 추출 과정
1. next(Top, 삭제할 노드) > data next(일반 노드) > data next(일반 노드) > null
2. next(삭제할 노드) > data next(Top, 일반 노드) > data next(일반 노드) > null
3. data next(Top, 일반 노드) > data next(일반 노드) > null
* 스택 추출 함수
void pop(Stack *stack) {
if (stack->top == NULL) {
printf("스택 언더플로우 발생.\n");
return -INF;
}
Node *node = stack->top;
int data = node->data;
stack->top = node->next;
free(node);
return data;
}
* 스택 전체 출력 함수
void show(Stack *stack) {
Node *cur = stack->top;
printf("--- 스택의 최상단 ---\n");
while (cur != NULL) {
printf("%d\n", cur->data);
cur = cur->next;
}
printf("--- 스택의 최하단 ---\n");
}
* 완성된 스택 사용하기
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
typedef struct {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
} Stack;
void push(Stack *stack, int data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->next = stack->top;
stack->top = node;
}
void pop(Stack *stack) {
if (stack->top == NULL) {
printf("스택 언더플로우 발생.\n");
return -INF;
}
Node *node = stack->top;
int data = node->data;
stack->top = node->next;
free(node);
return data;
}
void show(Stack *stack) {
Node *cur = stack->top;
printf("--- 스택의 최상단 ---\n");
while (cur != NULL) {
printf("%d\n", cur->data);
cur = cur->next;
}
printf("--- 스택의 최하단 ---\n");
}
int main(void) {
Stack stack;
stack.top = NULL;
show(&stack);
push(&stack, 7);
push(&stack, 5);
push(&stack, 4);
pop(&stack);
push(&stack, 6);
pop(&stack);
show(&stack);
system("pause");
return 0;
}
- 스택은 배열 혹은 연결 리스트를 이용해서 구현할 수 있음