[C] 스택(Stack)

스택(Stack)

 

- 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조. (후입 선출(LIFO: Last-In-First-Out)

- 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 함.

- 스택에 저장되는 것을 요소(element)라고 함.

- 스택에 요소가 하나도 없을 때 스택을 공백 스택(empty stack)이라고 함.

- 삽입 연산을 push 연산이라고 하고, 삭제 연산은 pop 연산이라고 함.

- is_empty 연산과 is_full 연산은 스택이 공백 상태에 있는지와 포화 상태에 있는지를 검사함.

- create 연산은 스택을 생성함.

- peek 연산은 요소를 스택에서 삭제하지 않고 보기만 하는 연산임.

- pop 연산은 요소를 스택에서 완전히 삭제하면서 가져옴.

- 가장 전형적인 스택의 사용 예는 함수 호출에서 복귀 주소를 기억하는 데 스택을 사용하는 것.

 

 

배열로 구현한 스택

[1] 전역 변수로 구현한 정수 배열 스택 프로그램 (Array of Integer)

// 정수 배열 스택 프로그램 (전역 변수로 구현)

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100

typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;

// 공백 상태 검출 함수
int is_empty() {
    return (top == -1);
}

// 포화 상태 검출 함수
int is_full() {
    return (top == (MAX_STACK_SIZE - 1));
}

// 삽입 함수
void push(element item) {
    if (is_full()) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else stack[++top] = item;
}

// 삭제 함수
element pop() {
    if (is_empty()) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top--];
}

// 피크 함수
element peek() {
    if (is_empty()) {
        fprintf(stderr, "스택 공백 에러\n");                                                                                      
        exit(1);
    }
    else return stack[top];
}

// 주 함수
void main() {
    push(1);
    push(2);
    push(3);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", is_empty());
}

 

[2] 전역 변수로 구현한 구조체 배열 스택 프로그램 (Array of Structure)

// 구조체 배열 스택 프로그램 (전역 변수로 구현)

#include <stdio.h>
#include <string.h>

#define MAX_STACK_SIZE 100
#define MAX_STRING 100

typedef struct {
    int sudent_no;
    char name[MAX_STRING];
    char address[MAX_STRING];
} element;

element stack[MAX_STACK_SIZE];
int top = -1;

// 공백 상태 검출 함수
int is_empty() {
    return (top == -1);
}

// 포화 상태 검출 함수
int is_full() {
    return (top == (MAX_STACK_SIZE - 1));
}

// 삽입 함수
void push(element item) {
    if (is_full()) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else stack[++top] = item;
}

// 삭제 함수
element pop() {
    if (is_empty()) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top--];
}

// 피크 함수
element peek() {
    if (is_empty()) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return stack[top];
}

// 주 함수
void main() {
    element ie, oe;
    strcpy(ie.name, "HongGilDong");
    strcpy(ie.address, "Seoul");
    ie.sudent_no = 20053001;
    push(ie);
    oe = pop();
    printf("name : %s\n", oe.name);
    printf("address : %s\n", oe.address);
    printf("student number : %d\n", oe.sudent_no);
}

 

 

[3] 관련된 데이터를 함수의 매개 변수로 전달하는 방법을 이용한 일반적인 배열 스택 프로그램

// 일반적인 배열 스택 프로그램 (관련된 데이터를 함수의 매개 변수로 전달)

#include <stdio.h>

#define MAX_STACK_SIZE 100

typedef int element;
typedef struct {
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;

// 스택 초기화 함수
void init(StackType *s) {
    s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s) {
    return (s->top == - 1);
}

int is_full(StackType *s) {
    return (s->top == (MAX_STACK_SIZE - 1));
}

// 삽입 함수
void push(StackType *s, element item) {
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->stack[++(s->top)] = item;
}

// 삭제 함수
element pop(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[(s->top)--];
}

// 피크 함수
element peek(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[s->top];
}

// 주 함수
void main() {
    StackType s;

    init(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", is_empty(&s));
}

 

cs

 

 

연결된 스택 (Linked Stack)

- 연결리스트로 구현된 스택.

- 외부에서 보기에는 배열을 이용한 스택이나 연결 리스트를 이용한 스택이나 전혀 차이가 없음. (제공되는 외부 인터페이스는 완전 동일함.)

- 달라지는 것은 스택의 내부 구현.

- 크기가 제한되지 않는다는 장점이 있음.

- 동적 메모리 할당이나 해제를 해야 하므로 삽입이나 삭제 시간이 좀 더 걸린다는 단점이 있음.

 

[4] 연결된 스택 프로그램 (Linked Stack using Linked List)

// 연결된 스택 프로그램

#include <stdio.h>
#include <malloc.h>

typedef int element;
typedef struct StructNode {
    element item;
    struct StackNode *link;
} StackNode;

typedef struct {
    StackNode *top;
} LinkedStackType;

// 초기화 함수
void init(LinkedStackType *s) {
    s->top = NULL;
}

// 공백 상태 검출 함수
int is_empty(LinkedStackType *s) {
    return (s->top == NULL);
}

// 포화 상태 검출 함수 (없어도 됨)
int is_full(LinkedStackType *s) {
    return 0;
}

// 삽입 함수
void push(LinkedStackType *s, element item) {
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
    if (temp == NULL) {
        fprintf(stderr, "메모리 할당에러\n");
        return;
    }
    else {
        temp->item = item;
        temp->link = s->top;
        s->top = temp;
    }
}

// 삭제 함수
element pop(LinkedStackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        StackNode *temp = s->top;
        element item = temp->item;
        s->top = s->top->link;
        free(temp);
        return item;
    }
}

// 피크 함수
element peek(LinkedStackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        return s->top->item;
    }
}

// 주 함수
void main() {
    LinkedStackType s;
    init(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", is_empty(&s));
}

 

[5] 포인터를 이용하여 구현한 연결된 스택 프로그램 (Linked Stack using Linked List (Pinter ONLY))

// 포인터를 이용하여 구현한 스택 프로그램 (NOTE)

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct {
    element *stack;
    int size;
    int top;
} StackType;

// 스택 초기화 함수
void init(StackType *s) {
    s->size = 1;
    s->stack = (element *)malloc(sizeof(element)*s->size);
    s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s) {
    return s->top == -1;
}

// 포화 상태 검출 함수
int is_full(StackType *s) {
    return s->top == s->size - 1;
}

void stack_full(StackType *s) {
    int i;
    element *data = (element *)malloc(sizeof(element)*s->size);
    for (i = 0; i <= s->top; i++) {
        data[i] = s->stack[i];    // 기존 스택 데이터 임시 저장
    }
    s->size *= 2;    // 크기를 2배로 증가
    free(s->stack);    // 기존 스택은 메모리 해제
    s->stack = (element *)malloc(sizeof(element)*s->size);        // 2배 크기의 스택 동적 할당
    for (i = 0; i <= s->top; i++) {
        s->stack[i] = data[i];        // 다시 스택으로 저장
    }
    free(data);    // 임시 저장소는 메모리 해제
}

// 삽입 함수
void push(StackType *s, element item) {
    if (is_full(s)) {
        stack_full(s);                // 포화 상태인 경우 스택 크기를 2배로 증가
    }
    s->stack[++s->top] = item;        // 앞에 else를 쓰면 안 됨.
}

// 삭제 함수
element pop(StackType *s) {
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    return s->stack[s->top--];
}

// 주 함수
void main() {
    StackType s;

    init(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    free(s.stack);
}

 

내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)