C언어 스택 (Stack) - LIFO 자료구조
선수학습(2개)
요약
C언어 스택(Stack)의 개념과 LIFO 원리를 알아봅니다. push/pop 연산, top 포인터, 배열 기반 스택 구현을 이해하면 정보처리기사 실기 스택 문제를 쉽게 풀 수 있습니다.
스택 핵심 정리
| 개념 | 설명 | 예시 |
|---|---|---|
| 스택(Stack) | 나중에 들어온 데이터가 먼저 나가는 자료구조 | 접시 쌓기, 뒤로가기 |
| LIFO | Last In First Out (후입선출) | 마지막에 넣은 게 먼저 나옴 |
| push | 스택에 데이터 삽입 (top 위에 추가) | push(5); |
| pop | 스택에서 데이터 삭제 (top에서 꺼냄) | pop(); |
| top | 스택의 맨 위 데이터 위치 | 초기값은 -1 (비어있음) |
스택이란?
스택(Stack) 은 나중에 들어온 데이터가 먼저 나가는 자료구조입니다. 이를 LIFO(Last In First Out) 라고 합니다.
실생활에서 접시 쌓기와 같습니다. 접시를 쌓으면 맨 위에 올리고, 꺼낼 때도 맨 위에서 꺼냅니다.
스택 vs 큐 비교
| 구분 | 스택 (Stack) | 큐 (Queue) |
|---|---|---|
| 원리 | LIFO (후입선출) | FIFO (선입선출) |
| 삽입 위치 | top (위) | rear (뒤) |
| 삭제 위치 | top (위) | front (앞) |
| 예시 | 접시 쌓기, 뒤로가기 | 대기열, 프린터 작업 |
rear(뒤쪽)는 큐에서 데이터가 들어오는 위치, front(앞쪽)는 나가는 위치입니다. 큐 페이지에서 자세히 다룹니다.
배열 기반 스택 구현
스택은 배열과 top 변수 하나로 구현할 수 있습니다.
#define MAX_SIZE 10은 MAX_SIZE를 10으로 정의하는 매크로입니다. 코드에서 MAX_SIZE가 나오면 컴파일할 때 자동으로 10으로 바뀝니다.
| 변수 | 역할 | 초기값 |
|---|---|---|
stack[] | 데이터를 저장하는 배열 | 모두 0 |
top | 맨 위 데이터의 인덱스 | -1 (비어있음) |
stack[]과 top은 함수 바깥에 선언된 전역 변수입니다. C언어에서 전역 변수는 자동으로 0으로 초기화되므로, stack[]의 모든 칸이 0으로 시작합니다.
push (삽입)
push는 스택의 top을 1 증가시킨 후, 그 위치에 데이터를 저장합니다.
++top의 의미
++top은 전위 증가입니다. 먼저 top을 1 증가시키고, 증가된 값을 인덱스로 사용합니다.
| 단계 | 설명 | 예시 (top이 -1일 때) |
|---|---|---|
| 1. top 증가 | ++top 실행 | top: -1 -> 0 |
| 2. 값 저장 | stack[top] = num | stack[0] = 5 |
push 예시
| 동작 | stack[0] | stack[1] | stack[2] | top |
|---|---|---|---|---|
| 초기 | 0 | 0 | 0 | -1 |
| push(5) | 5 | 0 | 0 | 0 |
| push(2) | 5 | 2 | 0 | 1 |
| push(7) | 5 | 2 | 7 | 2 |
pop (삭제)
pop은 스택의 top 위치의 데이터를 반환하고, top을 1 감소시킵니다.
top--의 의미
top--는 후위 감소입니다. 현재 top 값을 먼저 사용한 후, top을 1 감소시킵니다.
| 단계 | 설명 | 예시 (top이 2일 때) |
|---|---|---|
| 1. 값 반환 | stack[top] 반환 | stack[2] 반환 |
| 2. top 감소 | top-- 실행 | top: 2 -> 1 |
pop 예시
| 동작 | 반환값 | stack[0] | stack[1] | stack[2] | top |
|---|---|---|---|---|---|
| 이전 | - | 5 | 2 | 7 | 2 |
| pop() | 7 | 5 | 2 | 7 | 1 |
| pop() | 2 | 5 | 2 | 7 | 0 |
isEmpty와 isFull
스택이 비어있는지, 가득 찼는지 확인하는 함수입니다.
| 함수 | 조건 | 반환값 |
|---|---|---|
isEmpty() | top == -1 | 1 (비어있음) |
isFull() | top == MAX_SIZE - 1 | 1 (가득 참) |
안전한 push/pop
실제 프로그램에서는 isEmpty()와 isFull()로 오류를 방지합니다.
실기 문제에서의 스택
실기 문제에서는 push/pop 함수의 이름이 다를 수 있습니다. 함수의 동작을 보고 push인지 pop인지 판단해야 합니다.
함수 이름이 다른 경우
| 문제의 함수명 | 실제 동작 | 판단 기준 |
|---|---|---|
into(num) | push | ++top으로 증가 후 값 저장 |
take() | pop | top--로 값 반환 후 감소 |
enqueue(num) | push | top에 데이터 추가 |
dequeue() | pop | top에서 데이터 꺼냄 |
문제 풀이 순서
- 자료구조 파악: push/pop 함수를 찾아 스택인지 확인
- 초기 상태 확인: top(또는 point)의 초기값 확인
- 표 작성: 배열과 top 상태를 단계별로 추적
- 출력 순서 기록:
printf가 나올 때마다 출력값 기록