[자료구조] 선형 자료구조
스택(Stack) 개념 및 C언어 구현
자료구조의 큰 흐름과 그중 가장 기본이 되는 스택(Stack)의 원리 및 구현 방법을 정리합니다.
1. 자료구조의 분류
- 선형 리스트: 데이터가 일렬로 나열된 구조 (리스트, 스택, 큐)
- 비선형 리스트: 데이터가 계층적 혹은 망 형태로 연결된 구조 (트리, 그래프, 힙)
- 정렬: 데이터를 특정 기준에 따라 나열하는 과정 (결과는 주로 배열 형식)
C언어에서의 배열 구현 방식
- 정적 배열: 선언 시 크기 고정, 메모리 관리가 비효율적일 수 있음.
- 동적 배열:
malloc()함수와#include <malloc.h>를 사용하여 실행 시간에 메모리 할당.
구현 원리에 따른 구분
- ArrayList: 정적 방식, 인덱스를 이용한 접근.
- LinkedList: 동적 방식, 구조체와 포인터를 사용하여 값과 주소를 연결.
list => 1. arrayList(배열 리스트)
2. linkedList(연결 리스트)
stack => 1. arrayStack
2. linkedStack
queue => 1. arrayQueue
2. linkedQueue2. 스택(Stack)의 이해
특징
- LIFO (Last In First Out): 후입선출. 가장 나중에 들어온 데이터가 가장 먼저 나감.
- 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어짐.
주요 속성 및 함수
변수
- top: 마지막으로 들어온 데이터의 인덱스를 가리키는 변수.
- maxSize: 스택이 가질 수 있는 최대 길이값.
함수
- push(): 데이터 삽입. 삽입 전
isFull()을 통해 공간 확인 필수. - pop(): 데이터 삭제 및 반환. 삭제 전
isEmpty()를 통해 데이터 존재 확인 필수. - isFull() / isEmpty(): 스택의 포화/공백 상태를 체크하는 함수.
3. C언어 구현 코드
<stackS.h> --> 헤더 파일
#pragma once
#define STACK_SIZE 10
/* define으로 정의하는 이유: 가독성과 유지보수성을 높이기 위함.
나중에 스택의 크기를 변경할 때 이 부분만 수정하면 전체 코드 대응 가능 */
typedef int element;
/* element 타입을 정의하는 이유: 가독성과 유지보수성을 높이기 위함.
나중에 데이터 타입을 변경할 때 이 부분만 수정하면 전체 코드 대응 가능 */
element stack[STACK_SIZE];
int isStackEmpty(void);
//isEmpty() 함수는 스택이 비어있는지 확인하는 함수입니다.
//스택이 비어있으면 1을 반환하고, 그렇지 않으면 0을 반환합니다.
int isStackFull(void);
//isFull() 함수는 스택이 가득 찼는지 확인하는 함수입니다.
//스택이 가득 차면 1을 반환하고, 그렇지 않으면 0을 반환합니다.
void push(element item);
//push() 함수는 스택에 요소를 추가하는 함수입니다.
//스택이 가득 차 있으면 오류 메시지를 출력하고, 그렇지 않으면 요소를 스택에 추가합니다.
element pop(void);
//pop() 함수는 스택에서 요소를 제거하는 함수입니다.
//스택이 비어 있으면 오류 메시지를 출력하고, 그렇지 않으면 스택에서 요소를 제거하고 반환합니다.
void printStack(void);
//printStack() 함수는 스택의 현재 상태를 출력하는 함수입니다.
//스택에 있는 요소들을 순서대로 출력합니다.<stackS.c> --> 소스 파일
#include <stdio.h>
#include "stackS.h"
//[책갈피]라고 생각하기
int top = -1;
//스택의 최상단 요소의 인덱스를 나타내는 변수입니다.
//초기값은 -1로 설정되어 있으며, 스택이 비어 있을 때를 나타냅니다.
int isStackEmpty(void) {
if (top == -1) return 1; //만약 비어있다면, True
else return 0;
}
int isStackFull(void) {
if (top == STACK_SIZE - 1) return 1; //인덱스는 전체크기 - 1
else return 0;
}
void push(element item) {
if (isStackFull()) { //stack이 차면 넣을 수 없음
printf("Stack is full. Cannot push %d\n", item);
return;
}
stack[++top] = item; //일단 빈칸 확보부터 하고 넣는거라 생각
/* 새 책을 꽂기 위해, 일단 책갈피를 옆 칸으로 옮겨 공간을 만든 뒤(++top)
그 자리에 책을 꽂는 것(=item) */
}
element pop(void) {
if (isStackEmpty()) { //stack이 비면 지울 수 없음
printf("Stack is empty. Cannot pop\n");
return -1;
}
return stack[top--];
/*현재 책갈피가 꽂힌 데이터를 먼저 확인(반환)하고, 그 후에 책갈피를 한칸 내리는 것*/
}
//현재 스택 확인
void printStack(void) {
if (isStackEmpty()) {
printf("Stack is empty.\n");
return;
}
//스택의 구성 요소들
printf("Stack elements: ");
for (int i = 0; i <= top; i++) {
printf("%d ", stack[i]);
}
printf("\n");
}<main.c> --> 소스 파일
#include <stdio.h>
#include "stackS.h"
int main() {
element item;
printStack(); //Stack is empty.
push(1);
printStack(); //Stack elements: 1
push(2);
printStack(); //Stack elements: 1 2
push(3);
printStack(); //Stack elements: 1 2 3
item = pop();
printf("Popped item: %d\n", item); //Popped item: 3
printStack(); //Stack elements: 1 2
item = pop();
printf("Popped item: %d\n", item); //Popped item: 2
printStack(); //Stack elements: 1
item = pop();
printf("Popped item: %d\n", item); //Popped item: 1
printStack(); //Stack is empty.
return 0;
}Tip: main 함수에서 item 변수는 pop()을 통해 반환된 값을 담는 용도로 사용됩니다. push()만 한다고 해서 item 값이 자동으로 갱신되지 않는다는 점에 유의!
추가 학습 자료
🗑️ pop()의 비밀: 데이터는 정말 사라질까?
많은 분이 pop()을 실행하면 배열 내부의 데이터가 물리적으로 지워진다고 생각하지만, 실제로는 그렇지 않습니다. 스택의 삭제는 '논리적 삭제'의 원리를 따릅니다.
1. 물리적으로는 남아있다
pop()을 실행해서 top이 2에서 1로 내려갔다고 해도, stack[2] 위치에는 이전에 들어있던 값이 그대로 남아 있습니다. 컴퓨터 메모리는 항상 무언가(쓰레기 값 혹은 이전 데이터)로 채워져 있기 때문에, 굳이 에너지를 들여 값을 지우지 않습니다.
2. 논리적으로는 삭제되었다
우리는 top이 가리키는 곳까지만 유효한 데이터로 취급하기로 약속했습니다.
-
덮어쓰기(Overwrite): 새로운
push()가 발생하면top이 다시 올라오면서 기존stack[2]자리에 새로운 값을 덮어씁니다. -
출력 제한:
printStack()함수를 확인해 보면for (int i = 0; i <= top; i++)와 같이top까지만 루프를 돌기 때문에,top보다 높은 인덱스에 남은 값은 사용자에게 노출되지 않습니다.
🔖 책갈피 비유로 이해하기
책갈피(top)를 2페이지에서 1페이지로 옮겼다고 해서, 2페이지에 적힌 글자가 지워지는 것은 아닙니다. 단지 "우리는 1페이지까지만 읽은 것으로 간주하겠다"라는 약속이며, 나중에 새 내용을 쓸 때 그 위에 덧쓰는 것과 같습니다.
🔍 관련 코드 다시 보기
// pop 함수 내부
element pop(void) {
if (isStackEmpty()) {
printf("Stack is empty.\n");
return -1;
}
// 1. 현재 top 위치의 값을 반환하고
// 2. top을 하나 내린다 (논리적 삭제)
// 실제 stack[top]의 값이 0이 되지는 않음!
return stack[top--];
}
// 출력 함수 내부
void printStack(void) {
// top까지만 출력하므로 논리적 삭제 구역은 보이지 않음
for (int i = 0; i <= top; i++) {
printf("%d ", stack[i]);
}
}✅ 요약
- 물리적 상태: 데이터가 메모리에 잔존함.
- 논리적 상태:
top변수의 조작을 통해 해당 데이터에 접근 권한을 없앰. - 장점: 매번 데이터를 지우는 연산을 생략하여 프로그램의 실행 속도가 빨라짐.
Hard Trying