C의 스택

스택(Stack)은 LIFO(Last In, First Out) 구조로 데이터를 저장하는 자료구조입니다. C 언어에서는 스택을 직접 구현하거나, 운영 체제에 의해 제공되는 스택을 사용할 수 있습니다. 스택은 함수 호출과 같은 작업을 처리하는 데 중요한 역할을 합니다. 이 설명에서는 스택의 기본 개념, C 언어에서의 스택 구현 방법, 그리고 스택을 사용하는 예제들을 다루겠습니다.

1. 스택의 기본 개념

스택은 두 가지 주요 작업을 지원합니다:

• Push: 스택에 데이터를 추가하는 작업
• Pop: 스택에서 데이터를 제거하고 반환하는 작업

스택의 가장 중요한 특징은 LIFO 원칙입니다. 즉, 가장 나중에 추가된 데이터가 가장 먼저 제거됩니다.

예시

• Push: A -> B -> C (C가 가장 나중에 추가됨)
• Pop: C (가장 나중에 추가된 데이터가 먼저 제거됨)

2. C 언어에서 스택 구현

C 언어에서는 스택을 배열 또는 연결 리스트를 사용하여 구현할 수 있습니다. 기본적인 스택 구현 예제를 배열을 이용하여 보여드리겠습니다.

2.1 배열을 이용한 스택 구현

스택의 구조 정의와 기본 연산

c

코드 복사

#include <stdio.h> #include <stdlib.h> #define MAX 100 // 스택의 최대 크기 정의 typedef struct { int items[MAX]; int top; } Stack; // 스택 초기화 void initialize(Stack *s) { s->top = -1; } // 스택이 비어 있는지 확인 int isEmpty(Stack *s) { return s->top == -1; } // 스택이 가득 찼는지 확인 int isFull(Stack *s) { return s->top == MAX - 1; } // 스택에 요소 추가 (Push) void push(Stack *s, int value) { if (isFull(s)) { printf("스택이 가득 찼습니다!\n"); return; } s->items[++(s->top)] = value; } // 스택에서 요소 제거 및 반환 (Pop) int pop(Stack *s) { if (isEmpty(s)) { printf("스택이 비어 있습니다!\n"); return -1; // 에러 값 반환 } return s->items[(s->top)--]; } // 스택의 맨 위 요소 확인 (Peek) int peek(Stack *s) { if (isEmpty(s)) { printf("스택이 비어 있습니다!\n"); return -1; // 에러 값 반환 } return s->items[s->top]; } // 스택의 모든 요소 출력 void printStack(Stack *s) { if (isEmpty(s)) { printf("스택이 비어 있습니다!\n"); return; } for (int i = s->top; i >= 0; i--) { printf("%d\n", s->items[i]); } } int main() { Stack stack; initialize(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30); printf("스택의 최상위 요소: %d\n", peek(&stack)); printStack(&stack); printf("Pop된 요소: %d\n", pop(&stack)); printStack(&stack); return 0; }

설명:

• initialize 함수는 스택을 초기화합니다.
• push 함수는 스택에 요소를 추가합니다.
• pop 함수는 스택에서 요소를 제거하고 반환합니다.
• peek 함수는 스택의 최상위 요소를 반환합니다.
• printStack 함수는 스택의 모든 요소를 출력합니다.

3. 스택을 이용한 알고리즘

스택은 다음과 같은 알고리즘 및 문제에서 유용하게 사용됩니다:

• 함수 호출 관리: 스택은 함수 호출 시 호출 스택(call stack)을 통해 함수의 호출 정보를 관리합니다. 함수 호출 시 로컬 변수와 복귀 주소가 스택에 저장됩니다.
• 중위 표기식에서 후위 표기식으로 변환: 수식 변환 문제에서 스택을 사용합니다.
• 괄호 짝 맞추기: 코드의 괄호가 올바르게 닫혔는지 확인하는 데 스택을 사용할 수 있습니다.
• DFS (Depth-First Search): 그래프 탐색에서 스택을 사용하여 깊이 우선 탐색을 구현합니다.

4. 동적 스택 구현 (연결 리스트 사용)

배열 기반 스택은 고정 크기를 가지지만, 연결 리스트를 사용하여 동적 크기의 스택을 구현할 수 있습니다.

연결 리스트를 이용한 스택 구현

c

코드 복사

#include <stdio.h> #include <stdlib.h> // 노드 구조 정의 typedef struct Node { int data; struct Node *next; } Node; // 스택 구조 정의 typedef struct { Node *top; } Stack; // 스택 초기화 void initialize(Stack *s) { s->top = NULL; } // 스택이 비어 있는지 확인 int isEmpty(Stack *s) { return s->top == NULL; } // 스택에 요소 추가 (Push) void push(Stack *s, int value) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = value; newNode->next = s->top; s->top = newNode; } // 스택에서 요소 제거 및 반환 (Pop) int pop(Stack *s) { if (isEmpty(s)) { printf("스택이 비어 있습니다!\n"); return -1; // 에러 값 반환 } Node *temp = s->top; int poppedValue = temp->data; s->top = temp->next; free(temp); return poppedValue; } // 스택의 맨 위 요소 확인 (Peek) int peek(Stack *s) { if (isEmpty(s)) { printf("스택이 비어 있습니다!\n"); return -1; // 에러 값 반환 } return s->top->data; } // 스택의 모든 요소 출력 void printStack(Stack *s) { if (isEmpty(s)) { printf("스택이 비어 있습니다!\n"); return; } Node *current = s->top; while (current != NULL) { printf("%d\n", current->data); current = current->next; } } int main() { Stack stack; initialize(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30); printf("스택의 최상위 요소: %d\n", peek(&stack)); printStack(&stack); printf("Pop된 요소: %d\n", pop(&stack)); printStack(&stack); return 0; }

설명:

• Node 구조체는 스택의 각 요소를 나타냅니다.
• push 함수는 연결 리스트의 머리에 새로운 노드를 추가합니다.
• pop 함수는 연결 리스트의 머리에서 노드를 제거하고 반환합니다.
• peek 함수는 연결 리스트의 머리 노드의 데이터를 반환합니다.
• printStack 함수는 스택의 모든 요소를 출력합니다.