스택은 후입선출(LIFO, Last In First Out) 구조의 자료구조로, 들어간 순서의 역순으로 요소가 나옵니다.
스택 자료구조의 ADT
스택의 ADT(Abstract Data Type) 정의는 다음과 같습니다:
void StackInit(Stack * pstack);
// 스택의 초기화
// 스택 생성 후 제일 먼저 호출되어야 합니다.
int SIsEmpty(Stack * pstack);
// 스택이 비어 있는 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환합니다.
void SPush(Stack * pstack, Data data);
// 스택에 데이터를 저장합니다. 매개변수 data로 전달된 값을 저장합니다.
Data SPop(Stack * pstack);
// 마지막에 저장된 요소를 삭제하고 삭제된 데이터를 반환합니다.
// 이 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 합니다.
Data SPeek(Stack * pstack);
// 마지막에 저장된 요소를 반환하되 삭제하지는 않습니다.
// 이 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 합니다.ADT의 정의는 위와 같고 헤더파일을 디자인 하기전에
스택은 배열과 연결 리스트 기반의 두 가지 방식으로 구현할 수 있다.
스택의 배열 기반 구현
배열 기반의 스택은 정해진 크기의 배열을 사용하여 스택을 구현하는 방식입니다. 주요 연산으로
-
스택에 데이터를 추가하는
push -
데이터를 제거하는
pop -
최상단 데이터를 확인하는
peek -
스택이 비어 있는지 확인하는
isEmpty -
스택이 가득 찼는지 확인하는
isFull
C언어로 스택의 배열 기반 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 스택의 최대 크기 정의
typedef struct {
int data[MAX_SIZE]; // 데이터를 저장할 배열
int top; // 스택의 최상단을 가리키는 인덱스
} Stack;
// 스택 초기화 함수
void initStack(Stack* stack) {
stack->top = -1; // 스택이 비어있음을 의미하는 초기 값
}
// 스택이 비어있는지 확인하는 함수
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// 스택이 가득 찼는지 확인하는 함수
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
// 스택에 데이터를 추가하는 함수
void push(Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack is full!\n");
return;
}
stack->data[++(stack->top)] = value;
}
// 스택에서 데이터를 제거하고 반환하는 함수
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return -1; // underflow 상태를 처리하기 위한 값 반환
}
return stack->data[(stack->top)--];
}
// 스택의 최상단 데이터를 확인하는 함수
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return -1;
}
return stack->data[stack->top];
}
// 스택의 모든 데이터를 출력하는 함수 (디버깅용)
void printStack(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
printf("Stack elements: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\n");
}
int main() {
Stack stack;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printStack(&stack);
printf("Top element is %d\n", peek(&stack));
printf("Popped element is %d\n", pop(&stack));
printStack(&stack);
return 0;
}주요 특징 및 고려 사항
-
고정 크기 : 이 구현에서는 스택의 크기가 고정되어 있으며, MAX_SIZE를 초과하는 데이터를 추가할 수 없습니다.
-
오버플로우 및 언더플로우 : 스택이 가득 찼을 때 추가 데이터를 넣으려 하면 오버플로우가 발생하며, 비어 있는 스택에서 데이터를 꺼내려 하면 언더플로우가 발생합니다. 이 코드에서는 이를 간단히 처리하고 있습니다.
-
유연성 : 배열을 사용한 스택 구현은 간단하고 빠르지만, 크기가 고정되어 있어 동적 크기가 필요한 경우에는 연결 리스트 기반의 스택 구현이 더 적합할 수 있습니다.
스택의 연결 리스트 기반 구현
연결 리스트 기반의 스택은 고정된 크기의 배열 대신 동적 메모리를 사용하여 스택을 구현하는 방식입니다. 이 방식은 메모리를 유연하게 사용할 수 있으며, 배열 기반 스택의 크기 제한 문제를 해결합니다.
C언어로 스택의 연결리스트 기반 구현
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int data; // 노드의 데이터
struct _node* next; // 다음 노드를 가리키는 포인터
} Node;
typedef struct {
Node* top; // 스택의 최상단 노드를 가리키는 포인터
} Stack;
// 스택 초기화 함수
void initStack(Stack* stack) {
stack->top = NULL; // 스택이 비어있음을 나타냄
}
// 스택이 비어있는지 확인하는 함수
int isEmpty(Stack* stack) {
return stack->top == NULL;
}
// 스택에 데이터를 추가하는 함수
void push(Stack* stack, int value) {
Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
if (newNode == NULL) { // 메모리 할당 실패 시 처리
printf("Memory allocation failed!\n");
exit(1); // 프로그램 종료
}
newNode->data = value;
newNode->next = stack->top; // 새 노드가 이전의 최상단 노드를 가리키도록 설정
stack->top = newNode; // 스택의 최상단을 새 노드로 업데이트
}
// 스택에서 데이터를 제거하고 반환하는 함수
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty! Cannot pop.\n");
exit(1); // 프로그램 종료
}
Node* temp = stack->top; // 최상단 노드를 임시로 저장
int value = temp->data; // 최상단 노드의 데이터를 저장
stack->top = stack->top->next; // 스택의 최상단을 다음 노드로 이동
free(temp); // 기존의 최상단 노드 메모리 해제
return value;
}
// 스택의 최상단 데이터를 확인하는 함수
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty! Cannot peek.\n");
exit(1); // 프로그램 종료
}
return stack->top->data; // 최상단 노드의 데이터를 반환
}
// 스택의 모든 데이터를 출력하는 함수 (디버깅용)
void printStack(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
Node* current = stack->top;
printf("Stack elements: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
Stack stack;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
printStack(&stack);
printf("Top element is %d\n", peek(&stack));
printf("Popped element is %d\n", pop(&stack));
printStack(&stack);
return 0;
}주요 특징 및 고려 사항
-
동적 크기 : 연결 리스트 기반의 스택은 동적 메모리 할당을 사용하므로, 메모리가 허용하는 한 크기의 제한 없이 데이터를 저장할 수 있습니다.
-
메모리 관리 : 각 노드가 데이터를 저장하기 위해 메모리를 동적으로 할당받고, 스택에서 제거될 때 메모리를 해제합니다. 메모리 관리에 유의해야 하며, 메모리 누수(leak)가 발생하지 않도록 주의해야 합니다.
-
오버플로우 및 언더플로우 처리 : 연결 리스트 기반의 스택은 배열 기반 구현과 달리 오버플로우가 발생하지 않습니다. 하지만 언더플로우(스택이 비어 있을 때 pop이나 peek 연산을 시도하는 경우)는 여전히 발생할 수 있습니다. 이 경우 오류 메시지를 출력하고 프로그램을 종료하도록 구현하여 예외 상황을 적절히 처리합니다.
