[자료구조] - 스택 (C언어)

스택의 개념

: 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 구조 (LIFO : Last In First Out)

 

[Push, Pop]

Push : 스택에 자료를 밀어 넣는 것

Pop : 스택에 있는 자료를 꺼내는 것. 이 때 제일 최근에 밀어넣은 자료부터 꺼내지게 된다.

 

Push

 

Push 는 위 그림처럼 한쪽으로만 뚫려있는 스택의 출/입구에 자료를 밀어넣는 것을 의미합니다.

 

Pop

Pop 은 위 그림처럼 한쪽으로만 뚫려있는 스택의 출/입구로 자료를 꺼내는 것을 의미합니다. 제일 최근에 집어넣은 자료인 C 자료부터 꺼내집니다.

 

그러면 위 그림을 예로 들어 만약 Push 순서가 A -> B -> C 라면 Pop 순서는 C -> B -> A 순서가 되겠죠. 

즉, Pop 되어지는 자료들은 Push 된 자료들의 역순으로 Pop 되어집니다.

그리고 가장 안쪽에 있는 데이터를 bottom, 가장 바깥쪽에 있는(최신의) 데이터를 top 이라고 합니다.

 

Peek : top 에 있는 데이터 정보를 보는 것을 의미합니다.

 

[스택의 구현]

스택은 연결리스트로 구현 가능합니다.

 

0. 노드 구조체 선언

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

2 line : 노드의 데이터 정보 (1,2,3,,,,)

3 line : 현 노드의 다음 노드를 지칭할 자기참조 구조체 포인터

4 line : 현 노드의 이전 노드를 지칭할 자기참조 구조체 포인터 

 

1. 스택 구조체 선언

typedef struct _Stack {
    Node* top;
    int dataNum;
}Stack;

2 line : 스택의 top 데이터를 지칭할 포인터

3 line : 스택 안에 들어있는 데이터 개수를 저장하는 변수

 

2. 스택 초기화

void Initialize(Stack* s) {
    s->top = -1;
    s->dataNum = 0;
}

bool isStackEmpty(Stack* s) {
    if (s->dataNum == 0) {
        return true;
    }
    return false;
}

 

2 line : 현재 스택에 들어있는 데이터 개수가 0이라면 

3 line : true 반환

4 line : 조건문이 거짓이라면 false 반환

 

4. PUSH 함수

void Push(Stack* s, int Data) {
    Node *newNode = (Node*)malloc(sizeof(Node));//새 노드 생성
    newNode->data = Data;
    newNode->next = NULL;
    newNode->before = NULL;
 
    if (!isStackEmpty(s)) {
        s->top->next = newNode;
        newNode->before = s->top;
    }
 
    s->top = newNode;
    (s->dataNum)++;//->보다 ++의 우선순위가 높기 때문에 () 필수
}

2 line : 새 노드 생성

3 line : 새 노드의 data 입력

4, 5 line : 새 노드의 전, 후 포인터를 NULL로 설정

7~10 line : 만약 스택이 비어있지 않으면 현 스택의 top 노드의 next를 새 노드로 지정하고 새 노드의 이전 노드를 현 스택의 top으로 지정

12 line : 스택의 top을 새 노드로 지정

13 line : 스택의 데이터 개수 1 증가

 

5. POP 함수

void Pop(Stack* s) {
    if (isStackEmpty(s)) {
        printf("스택이 비어있어서 pop 할 수 없습니다.\n");
        return;
    }
    Node* waste = (Node*)malloc(sizeof(Node));//버리는 노드
 
    waste = s->top;
    int result = waste->data;
    s->top = s->top->before;
    s->top->next = NULL;
 
    free(waste);//버리는 노드 메모리 해제
 
    (s->dataNum)--;
    printf("pop 한 결과 %d가 나왔습니다\n", result);
}

2~5 line : 스택이 비어있으면 pop 할 수 없음을 알림

6 line : pop 해서 버릴 노드를 지칭할 포인터 생성

8 line : pop하면 top이 버려지므로 버려질 노드를 현 스택의 top노드로 지정

9 line : pop할 노드의 데이터 정보를 result 변수에 담음 (16line에서 출력)

10 line : 스택의 top을 현 top 노드의 이전 노드로 지정(현 top은 버려질 것이기 때문에)

11 line : top 노드의 next를 NULL로 지정

12 line : waste 노드의 메모리 해제

13 line : 스택의 데이터 개수 감소

 

6. PEEK 함수

void Peek(Stack* s) {
    printf("스택의 top에 있는 정보는 %d입니다\n", s->top->data);
}

void showData(Stack* s) {
    if (isStackEmpty(s)) {
        printf("스택이 비어있어서 출력할게 없습니다\n");
        return;
    }
    printf("현재 스택에는 ");
    Node* current = (Node*)malloc(sizeof(Node));
    current = s->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->before;
    }
    printf(" 가 들어있습니다\n");
}

int main() {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    Initialize(s);
    if (isStackEmpty(s))
        printf("스택이 비어있습니다\n");
 
    printf("스택에 1을 push합니다\n");
    Push(s, 1);
    printf("스택에 2을 push합니다\n");
    Push(s, 2);
    printf("스택에 3을 push합니다\n");
    Push(s, 3);
    showData(s);
    Pop(s);
    showData(s);
    Peek(s);
    showData(s);
    
    if (isStackEmpty(s))
        printf("스택이 비어있습니다\n");
    return 0;
}

2 line : 스택 포인터 생성

3 line : 스택 초기화

4~5 line : 스택이 비어있는지 확인

7~17 line : push, pop, peek, showData 함수를 실행해봄

19~20 line : 위에서 함수 다 실행하고 나서 스택이 비어있는지 확인해봄

출력결과

< 전체 소스코드 >

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef struct _Node {
    int data;
    struct Node* next;
    struct Node* before;
}Node;
 
typedef struct _Stack {
    Node* top;
    int dataNum;
}Stack;
 
void Initialize(Stack* s) {
    s->top = -1;
    s->dataNum = 0;
}
 
bool isStackEmpty(Stack* s) {
    if (s->dataNum == 0) {
        return true;
    }
    return false;
}
 
void Push(Stack* s, int Data) {
    Node *newNode = (Node*)malloc(sizeof(Node));//새 노드 생성
    newNode->data = Data;
    newNode->next = NULL;
    newNode->before = NULL;
 
    if (!isStackEmpty(s)) {
        s->top->next = newNode;
        newNode->before = s->top;
    }
 
    s->top = newNode;
    (s->dataNum)++;//->보다 ++의 우선순위가 높기 때문에 () 필수
}
 
void Pop(Stack* s) {
    if (isStackEmpty(s)) {
        printf("스택이 비어있어서 pop 할 수 없습니다.\n");
        return;
    }
    Node* waste = (Node*)malloc(sizeof(Node));//버리는 노드
 
    waste = s->top;
    int result = waste->data;
    s->top = s->top->before;
    s->top->next = NULL;
 
    free(waste);//버리는 노드 메모리 해제
 
    (s->dataNum)--;
    printf("pop 한 결과 %d가 나왔습니다\n", result);
}
 
void Peek(Stack* s) {
    printf("스택의 top에 있는 정보는 %d입니다\n", s->top->data);
}
 
void showData(Stack* s) {
    if (isStackEmpty(s)) {
        printf("스택이 비어있어서 출력할게 없습니다\n");
        return;
    }
    printf("현재 스택에는 ");
    Node* current = (Node*)malloc(sizeof(Node));
    current = s->top;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->before;
    }
    printf(" 가 들어있습니다\n");
}
 
int main() {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    Initialize(s);
    if (isStackEmpty(s))
        printf("스택이 비어있습니다\n");
 
    printf("스택에 1을 push합니다\n");
    Push(s, 1);
    printf("스택에 2을 push합니다\n");
    Push(s, 2);
    printf("스택에 3을 push합니다\n");
    Push(s, 3);
    showData(s);
    Pop(s);
    showData(s);
    Peek(s);
    showData(s);
    
    if (isStackEmpty(s))
        printf("스택이 비어있습니다\n");
    return 0;
}