스택이란?
스택에 10, 20, 30 순서로 숫자를 3개 넣어봅니다. (push 연산)
가장 먼저 들어간 10이 맨 아래에 있게 됩니다.
10을 즉시 꺼낼 수 없고, 30 부터 꺼내야 마지막으로 10을 얻을 수 있습니다. (pop 연산)
이처럼 '가장 먼저 들어간 요소가 가장 마지막에 나오는 구조 입니다.
그래서 FILO (First In Last Out) 라고 부릅니다.
자동메모리가 스택을 기반으로 동작하고, 대부분의 네트워크 프로토콜도 스택을 기반으로 구성되어 있습니다.
배열로 구현하는 스택
배열을 이용하면, 동적으로 스택의 길이를 조절할 수 없지만, 구현이 간단합니다.
사용자가 정한 숫자만큼의 길이를 가진 배열을 만듭니다.
그리고 최상위 노드의 위치를 알고있는 변수로 삽입과 제거 연산을 합니다.
스택의 노드
스택에 들어갈 노드입니다.
데이터 하나를 담는 노드를 구조체로 표현합니다.
노드의 위치는 배열의 인덱스로 알 수 있습니다.
typedef struct Node {
int data;
}Node;
다음은 스택 구조체입니다.
구조체 ArrayStack에 필요한 필드는 세 가지 입니다.
배열의 길이
배열
최상위 노드의 위치
노드가 최대 몇 개 들어갈 수 있는지 배열의 길이를 알아야 합니다.
그리고 노드를 저장할 '배열'이 필요하고, 최상위 노드의 위치로 삽입/제거 합니다.
typedef struct ArrayStack {
int capacity; /* 배열 용량 */
int top; /* 최상위 노드 위치 */
Node* arrayNodes; /* 노드들을 보관하는 스택배열 */
}ArrayStack;노드 배열은 포인터로 선언되어 있습니다. (포인터는 배열로 사용할 수 있습니다)
스택의 생성과 메모리해제
CreateArrayStack() 함수는 배열의 최대길이를 이용하여 스택을 생성합니다.
/* 스택 생성. 메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
printf("[ 스택 생성 CreateArrayStack ]\n");
/* 스택을 자유 저장소에 생성 */
(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
/* 용량 만큼의 노드들을 자유 저장소에 생성 */
(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);
// 필드 초기화
(*stack)->capacity = capacity;
(*stack)->top = 0;
}
FreeArrayStack() 함수는 노드와 스택을 자유 저장소에서 해제합니다.
void FreeArrayStack(ArrayStack** stack) {
printf("[ 메모리 해제 FreeArrayStack ]\n");
free((*stack)->arrayNodes);
free((*stack));
}
삽입 연산 (PUSH)
스택 구조체가 알고있는 top 위치의 노드에 데이터를 넣습니다.
배열 인덱스가 top이 됩니다.
데이터를 넣고, top위치를 갱신해줍니다.
void Push(ArrayStack* stack, int inputData) {
printf("[ 삽입연산 Push ] %d를 Push \n", inputData);
int location = stack->top;
stack->arrayNodes[location].data = inputData;
stack->top = location + 1;
}
스택이 꽉 찼을 때를 확인하는 Push 함수
스택이 꽉 찼을 때 push를 안하고 종료하는 코드를 추가해봤습니다.
capacity와 top이 같은지 확인합니다.
Push의 리턴을 bool로 바꾸고, 삽입이 불가하면 false를 리턴하도록 했습니다.
bool Push(ArrayStack* stack, int inputData) {
printf("[ 삽입연산 Push ] %d를 Push \n", inputData);
if (stack->capacity == stack->top) {
printf("[ 용량초과! ] 삽입이 불가합니다. \n");
return false;
}
int location = stack->top;
stack->arrayNodes[location].data = inputData;
stack->top = location + 1;
return true;
}
삽입/제거 연산을 확인해본 main 함수 코드입니다.
int main() {
ArrayStack* stack = NULL;
CreateArrayStack(&stack, 10);
// 12번 Push
for (int i = 10; i <= 120; i+=10) {
if (!Push(stack, i)) {
break;
}
}
// 5번 Pop
for (int i = 0; i < 5; i++) {
printf("%3d를 제거합니다.\n", Pop(stack));
}
return 0;
}
배열 최대 길이가 10인데, Push 연산을 12번 했을 경우 콘솔 화면 입니다.
10번 넣고, 11번 넣으려고 할때 용량이 초과되서 for 문을 break 합니다.
이어서 제거 연산을 5번 수행합니다.
스택용량이 Full 인지 확인하는 함수로 분리하면 더 좋을 것 같습니다.
제거 연산 (POP)
삽입과는 달리, top 값을 1 감소하면 됩니다.
그리고 top 위치에 있던 data를 호출자에게 반환합니다.
int Pop(ArrayStack* stack) {
printf("[ 제거연산 Pop ]\n");
int location = --(stack->top);
return stack->arrayNodes[location].data;
}
POP 연산 시, 배열의 인덱스를 주의해야 합니다.
왜냐하면 top이 1이라면, 노드가 위치하는 실제 인덱스는 0이기 때문입니다.
스택이 비었는지 확인 : Pop 전에 확인
/* 스택이 비었는지 확인 : 제거 전에 확인 */
int isEmpty(ArrayStack* stack) {
// true 1 반환. false 0 반환
return (0 == stack->top);
}
전체 코드
배열길이는 10을 주고 10부터 100까지 10개의 숫자를 PUSH 합니다.
12번의 POP을 시도하지만 10번까지만 하고 종료되는 코드입니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
int data;
}Node;
typedef struct ArrayStack {
int capacity; /* 배열 용량 */
int top; /* 최상위 노드 위치 */
Node* arrayNodes; /* 노드들을 보관하는 스택배열 */
}ArrayStack;
/* 스택 생성. 메모리 할당 */
void CreateArrayStack(ArrayStack** stack, int capacity) {
printf("[ 스택 생성 CreateArrayStack ]\n");
/* 스택을 자유 저장소에 생성 */
(*stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
/* 용량 만큼의 노드들을 자유 저장소에 생성 */
(*stack)->arrayNodes = (Node*)malloc(sizeof(Node) * capacity);
// 필드 초기화
(*stack)->capacity = capacity;
(*stack)->top = 0;
}
/* 메모리 해제 */
void FreeArrayStack(ArrayStack** stack) {
printf("[ 메모리 해제 FreeArrayStack ]\n");
free((*stack)->arrayNodes);
free((*stack));
}
/* 삽입 Push 연산 */
void Push(ArrayStack* stack, int inputData) {
printf("[ 삽입연산 Push ] %d를 Push \n", inputData);
int location = stack->top;
stack->arrayNodes[location].data = inputData;
stack->top = location + 1;
}
/* 스택이 비었는지 확인 : 제거 전에 확인 */
int isEmpty(ArrayStack* stack) {
// true 1 반환. false 0 반환
return (0 == stack->top);
}
/* 제거 Pop 연산 */
int Pop(ArrayStack* stack) {
printf("[ 제거연산 Pop ]\n");
int location = --(stack->top);
return stack->arrayNodes[location].data;
}
int main() {
ArrayStack* stack = NULL;
CreateArrayStack(&stack, 10);
// 10개 Push
for (int i = 10; i <= 100; i+=10) {
Push(stack, i);
}
// 12번을 pop 해본다
for (int i = 0; i < 12; i++) {
if (isEmpty(stack)) {
printf("스택이 비었습니다. \n");
break;
}
else {
printf("%3d를 제거합니다.\n", Pop(stack));
}
}
return 0;
}
콘솔 결과 입니다.
다음 포스팅에서는 링크드 리스트로 구현하는 스택을 다루겠습니다.
'알고리즘 > 알고리즘 C' 카테고리의 다른 글
| 순환 큐 (0) | 2020.03.09 |
|---|---|
| 링크드 리스트로 구현하는 스택 (0) | 2020.02.19 |
| 환형 링크드 리스트 (0) | 2020.02.17 |
| 더블 링크드 리스트 (0) | 2020.02.14 |
| 링크드 리스트 (c로 구현한 추가 탐색 순회 삭제) (0) | 2020.02.12 |
