Goal

  • 스택 자료구조를 이해한다.
  • 스택을 c언어를 통해서 구현할 수 있다.

스택

  • 스택은 한쪽으로 들어가서 한쪽으로 나오는 자료구조 이다.
  • 수식계산등의 알고리즘에서 다방면으로 활용된다.
  • push연산,pop연산이 있다.
  • 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나눠진다.

image.png

image.png

image.png

image.png

image.png

image.png

image.png

배열을 이용한 스택(stack)

#include<stdio.h>
#include<stdlib.h>
#define SIZE 10000
#define INF 9999999
int stack[SIZE];
int top = -1;

void push(int data) {

    if ( top == SIZE - 1){
        printf("Stack OverFlow");
    }
    stack[++top] = data;
}
int pop() {
    if ( top == -1) {
        printf("Stack UnderFlow");
        return -INF;
    }
    return stack[top--];
}
void show() {
    printf("--- 스택의 최상단 ---\n");
    for(int i = top; i >= 0; i--) {
        printf("%d\n",stack[i]);
    }
    printf("--- 스택의 최 하단 ---");
}
int main(void) {

    push(7);
    push(6);
    push(5);
    push(4);
    push(3);
    pop();
    show();
    return 0;
}

연결리스트를 이용한 스택(stack)

스택의 삽입 연산

  1. 데이터를 삽입할때는 항상 top에 들어와야 한다.
    image.png

  2. 삽입할 노드를 생성
    image.png

  3. 삽입할 노드의 next를 top노드를 가르키도록 한다
    image.png

  4. top노드의 next를 삽입할 노드를 가르키도록 한다.
    image.png

void push(Stack *stack, int data) {

    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;

}

스택의 추출 연산

삭제할 노드를 따로 기록해 뒀다가, top을 삭제할 노드의 뒤쪽에 있는 노드를 가르키도록 하고, 삭제할 노드를 free시키면 된다.

void pop(Stack *stack) {
    if(stack->top == NULL) {
        printf("Stack Underflow")
    }
    Node *node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}

연결리스트 스택 전체 코드


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

typedef struct Node {
    int data;
    Node *next;
} Node;
typedef struct top {
    Node *top;
} Stack;
void push(Stack *stack, int data) {

    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = stack->top;
    stack->top = node;

}
int pop(Stack *stack) {

    if(stack->top == NULL) {
        printf("Stack Underflow");
        return -1;
    }
    Node *node = stack->top;
    int data = node->data;
    stack->top = node->next;
    free(node);
    return data;
}
void show(Stack *stack) {
    Node *cur = stack->top;
    while(cur != NULL) {
        printf("%d\n",cur->data);
        cur = cur->next;
    }

}
int main(void) {
    Stack s;
    s.top = NULL;    
    push(&s,7);
    push(&s,6);
    push(&s,5);
    push(&s,4);
    push(&s,3);
    pop(&s);
    show(&s);
    return 0;
}