스택(프로그래밍) 편집하기 (부분)

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

=== 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>