Gaon12: 시작

2024-10-14T02:26:28Z

시작

새 문서

== 개요 ==
스택(Stack)은 컴퓨터 과학에서 널리 사용되는 추상 자료형으로, 데이터를 저장하고 관리하는 자료 구조이다. 스택의 가장 큰 특징은 '후입선출'(LIFO: Last In First Out) 원칙을 따른다는 점이다. 이는 나중에 들어온 데이터가 가장 먼저 나가는 구조를 의미한다.

== LIFO vs FIFO ==
데이터 구조를 이해하는 데 있어 LIFO와 FIFO의 개념은 매우 중요합니다.

=== LIFO (Last In First Out) ===
* LIFO는 '''"나중에 들어온 것이 먼저 나간다"'''는 원칙이다.
* 스택(Stack)이 대표적인 LIFO 구조다.
* 실생활의 예: 접시 쌓기, 웹 브라우저의 뒤로 가기 버튼

=== FIFO (First In First Out) ===
자세한 내용은 [[큐(프로그래밍)]] 문서를 참고하세요!

* FIFO는 '''"먼저 들어온 것이 먼저 나간다"'''는 원칙이다.
* 큐(Queue)가 대표적인 FIFO 구조다.
* 실생활의 예: 계산대에 줄 서 있는 사람들, 프린터의 인쇄 대기열

== 스택(Stack)의 특징 ==
# LIFO 원칙: 나중에 들어온 데이터가 가장 먼저 나간다.
# 주요 작업:
## Push: 스택의 위쪽(top)에 새로운 요소를 추가한다.
## Pop: 스택의 위쪽(top)에서 요소를 제거한다.
# 주요 위치:
## Top: 스택의 가장 위에 있는 요소의 위치

== 스택의 기본 연산 ==
# push(item): 스택의 위쪽(top)에 새로운 요소를 추가한다.
# pop(): 스택의 위쪽(top)에서 요소를 제거하고 반환한다.
# peek(): 스택의 가장 위에 있는 요소를 반환하지만 제거하지는 않는다.
# isEmpty(): 스택이 비어있는지 확인한다.
# isFull(): 스택이 가득 찼는지 확인한다. (배열로 구현된 경우)

== 스택의 구현 방식 ==
스택은 주로 두 가지 방식으로 구현된다:

=== 1. 배열 기반 구현 ===
배열을 사용하여 스택을 구현하는 방식이다.

==== 장점 ====
* 구현이 간단하다.
* 랜덤 접근이 가능하다.

==== 단점 ====
* 크기가 고정되어 있어 스택이 가득 찼을 때 새로운 요소를 추가할 수 없다.

==== C언어 예제 ====
<syntaxhighlight lang="c">
#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
int items[MAX_SIZE];
int top;
} Stack;

void initializeStack(Stack *s) {
s->top = -1;
}

int isEmpty(Stack *s) {
return (s->top == -1);
}

int isFull(Stack *s) {
return (s->top == MAX_SIZE - 1);
}

void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack is full!\n");
return;
}
s->items[++(s->top)] = value;
}

int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
return s->items[(s->top)--];
}

int main() {
Stack s;
initializeStack(&s);

push(&s, 10);
push(&s, 20);
push(&s, 30);

printf("%d\n", pop(&s));
printf("%d\n", pop(&s));

return 0;
}
</syntaxhighlight>

=== 2. 연결 리스트 기반 구현 ===
연결 리스트를 사용하여 스택을 구현하는 방식이다.

==== 장점 ====
* 크기가 동적으로 조절된다.
* 요소의 추가와 제거가 효율적이다.

==== 단점 ====
* 추가적인 메모리가 필요하다. (포인터를 저장해야 하므로)
* 랜덤 접근이 불가능하다.

==== C언어 예제 ====
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
int data;
struct Node* next;
} Node;

typedef struct {
Node* top;
} Stack;

void initializeStack(Stack* s) {
s->top = NULL;
}

int isEmpty(Stack* s) {
return (s->top == NULL);
}

void push(Stack* s, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
}

int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}

Node* temp = s->top;
int item = temp->data;
s->top = s->top->next;
free(temp);

return item;
}

int main() {
Stack s;
initializeStack(&s);

push(&s, 10);
push(&s, 20);
push(&s, 30);

printf("%d\n", pop(&s));
printf("%d\n", pop(&s));

return 0;
}
</syntaxhighlight>

== 스택의 응용 분야 ==
스택은 다양한 분야에서 활용된다:

# 함수 호출의 관리 (호출 스택)
# 수식 계산 및 구문 분석
# 웹 브라우저의 뒤로 가기 기능
# 깊이 우선 탐색(DFS) 알고리즘
# 역순 문자열 만들기
# 운영 체제의 메모리 관리

== 스택의 변형 ==
# 동적 스택(Dynamic Stack): 연결 리스트를 이용해 크기가 동적으로 조절되는 스택.
# 다중 스택(Multi Stack): 하나의 배열을 여러 개의 스택으로 나누어 사용하는 구조.
# 우선순위 스택(Priority Stack): 각 요소에 우선순위가 부여된 스택. (스택보다는 우선순위 큐에 가까운 개념)

== 결론 ==
스택은 LIFO 원칙을 따르는 간단하면서도 강력한 자료 구조이다. 이 구조는 많은 실제 상황을 모델링하는 데 이상적이며, 컴퓨터 과학의 여러 분야에서 중요한 역할을 한다. 스택의 개념을 이해하고 적절히 활용할 수 있다면, 다양한 프로그래밍 문제를 효과적으로 해결할 수 있을 것이다.


[[분류:자료구조]] [[분류:알고리즘]] [[분류:컴퓨터 과학]]

스택(프로그래밍) - 편집 역사

Gaon12: 시작