스택(Stack)

스택이란?

스택은 마지막에 들어온 데이터가 첫번째로 나가는 후입선출 구조다. 프링글스를 생각하면 쉽게 이해가 간다.

스택의 push와 pop 과정

스택은 top이라는 포인터를 통하여 데이터를 삽입/삭제 한다. 스택에서 삽입은 push라 하고 삭제는 pop이라 한다.
push 과정에서 top은 추가한 데이터를 가리키고 pop 과정에서는 삭제할 데이터의 이전 노드를 가리킨다.
핵심은 top은 항상 제일 마지막 데이터를 가리켜야 한다는 것이다.

스택의 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<stdio.h>
#include<stdlib.h>
 
typedef struct node{
    int data;
    struct node *next;
}node;
 
/*
main함수 안에 선언하면 이중포인터를 사용하거나
리턴을 해야해서 전역변수로 선언함
*/
node *top = NULL;
 
//node를 추가하는 함수
void push(int data){
    node *newNode = (node*)malloc(sizeof(node));
    newNode->data = data;
    newNode->next = top;
    top = newNode;
}
 
//node를 삭제하는 함수
void pop(){
    if(top == NULL){
        printf("Node가 없습니다!");
        return;
    }
 
    node *old = top;
    top = old->next;
 
    free(old);
}
 
void printStack(){
    node *temp = top;
 
    printf("stack = [ ");
 
    while(temp->next != NULL){
        printf("%d ", temp->data);
        temp = temp->next;
    }
 
    printf("%d ]", temp->data);
}
 
int main(){
    push(100);
    push(200);
    push(300);
    push(400);
    push(500);
    pop();
    printStack();
}
 
cs