[5] Stack

1.  스택(Stack)이란?

- 더미, 낟가리라는 사전적 의미를 갖고 있음.

- 실생활의 예로는 식당의 접시 더미, 책상에 쌓인 책, 창고에 쌓인 상자 등임.

- 후입 선출(LIFO : Last In First Out)의 입출력 형태를 갖고 있음.

2. 전형적인 스택의 사용 예

- 함수 호출에서 복귀 주소를 기억하는 데에 스택을 사용함.

3. 스택의 구현 방법

	Array	Linked List
장점	구현 간단	스택 크기 자유자재
단점	스택 크기 고정	구현 복잡

4. 스택 구현(Code)

1) 단일 element를 저장하는 Stack

#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() {
    for (int i = 1; i <= 3; i++)
        push(i);
 
    for (int i = 0; i < 4; i++)
        printf("%d\n", pop());
}
 

- 이 방법은 프로그램에서 하나 이상의 스택을 사용해야 할 때, 상당히 곤란해질 수 있음

- 전역 변수를 사용하는 것은, 프로그램을 복잡하게 만들어서 오류가 발생할 확률을 높임.

2) 여러가지 element를 갖는 Struct 스택

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define MAX_STACK_SIZE 100
#define MAX_STRING 100
 
typedef struct element{
    int student_no;
    char name[MAX_STRING], 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];
}
 
int main() {
 
    element ie, oe;
 
    strcpy(ie.name, "홍길동");
    strcpy(ie.address, "서울");
    ie.student_no = 20053001;
 
    push(ie);
 
    oe = pop();
 
    printf("name : %s\n", oe.name);
    printf("address : %s\n", oe.address);
    printf("student number : %d\n", oe.student_no);
 
    return 0;
}

- 단점이 있다면, stack 배열과 top이 전역 변수로 선언되기 때문에 전체 프로그램에서 여러 개의 스택을 사용하기가 어렵다는 점임.

3) 관련 데이터를 합수의 매개 변수로 전달하는 방법.

- 위의 단점을 보완해줄 방법.

#include<stdio.h>
#include<stdlib.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];
}
 
int main() {
 
    StackType s;
 
    init(&s);
 
    for (int i = 1; i <= 3; i++)
        push(&s, i);
    for (int i = 1; i < 5; i++) 
        printf("%d\n", pop(&s));
    return 0;
}

- 위의 코드가 복잡한 이유는 구조체의 포인터를 각 함수에 전달해야되는 점 때문임.

- 각 함수에서는 구조체의 포인터를 이용해서 스택을 조작함.

- C언어에서 함수 매개 변수 전달 방식이 기본적으로 call by value라서, 그냥 구조체만 전달할 경우 원본이 아니라 복사본이 전달되는 것.

- 그래서 함수 내부에서 값을 바꿔도, 파라미터로 들어온 값에는 영향을 미치지 못한다.

- 그러나 원본에 대한 포인터를 전달하면 원본을 변경할 수 있음.

- 그치만, 구조체 복사에 따른 부담이 고려되므로 주의.

- 이 방법은 여러 개의 스택을 만들 수 있다는 큰 장점을 갖고 있음.

4) 링크드리스트로 만든 스택

- 메모리상의 제한을 해결한 스택이지만, 삽입과 삭제에는 시간이 조금 걸린다.

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
 
typedef int element;
typedef struct StackNode {
    element item;
    StackNode *link;
}StackNode;
 
typedef struct {
    StackNode *top;
}LinkedStackType;
 
void init(LinkedStackType *s) {
    s->top = NULL;
}
 
int is_empty(LinkedStackType *s) {
    return (s->top == NULL);
}
 
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 {
        // top을 임시로 가리킬 temp
        StackNode *temp = s->top;
        // pop할 item을 임시 저장
        element item = temp->item;
        // top은 한 칸 뒤로감
        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;
}
 
int main() {
    LinkedStackType s;
    init(&s);
 
    for (int i = 0; i < 3; i++)
        push(&s, i);
    for (int i = 0; i < 5; i++) 
        printf("%d\n", pop(&s));
    
}

5. 스택의 응용

- 괄호 검사 프로그램, 중위, 전위, 후위 표기 프로그램, 미로찾기(DFS)