[자료구조] ep5) 스택(Stack)

ㅇ스택 ADT: 임의의 개체를 저장하며, 후입선출(Last-In First-Out, LIFO) 순서를 따른다

삽입(push)과 삭제(pop)는 스택의 top(스택 포인터)이라 불리는 위치에서 수행

LIFO

 

 

- 직접 응용: 웹페이지들의 기록, ctrl+z, Window OS에서 겹쳐진 윈도우들, C++이나 JVM에서 메서드의 연쇄적인 호출, 재귀의 구현 등

- 간접 응용: 알고리즘 구현, 자료구조 구현

 

 

 

우리는 스택을 배열과 리스트 2가지 방법으로 구현할 수 있다

1. 배열에 기초한 스택

 

 

2. 연결리스트에 기초한 스택

 

※ 삽입과 삭제가 특정위치에서만 수행되므로, 헤더노드는 불필요

 

 

 

 

 

 

 

 

문제) 배열을 이용해 스택을 구현하시오

• 원소 : 영문자
• 다음 연산을 지원해야 함.
• - push(stack, ‘c’) : stack의 top에 원소를 추가한다. stack이 이미 꽉 차있으면 해당 데이터는 스택에 저장하지 않고 “Stack FULL”을 출력한다.
• - pop(stack) : stack의 top에 있는 원소를 반환하고 stack에서 제거한다. stack이 비어 있으면 “Stack Empty”를 출력한다.
• - peek(stack) : stack의 top에 있는 원소를 화면에 출력한다. stack은 변화하지 않는다. stack이 비어 있으면 “Stack Empty”를 출력한다.
• - duplicate(stack) : stack의 top에 있는 원소를 pop해서 두 번 push한다. stack이 이미 꽉 차 있으면 “Stack FULL”을 출력한다. 원소를 하나씩 위쪽으로 이동시킨다. 맨 위쪽(top)의 std1은 n-1번 아래쪽으로 이동해서 스택의 내용은 elem2, elem3, elem1, ... 이 된다. 원소를 하나씩 아래쪽으로 이동시킨다. top에서부터 n번째의 원소를 top으로 이동해서 스택의 내용은 elem3, elem1, elem2, ... 이 된다.
• - upRotate(stack, n) : stack의 맨 위 n개의 원소를 회전시킨다. 예를 들어 n이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면
• - downRotate(stack, n) : stack의 맨 위 n개의 원소를 회전시킨다. 예를 들어 n이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면
• - print(stack) : stack의 모든 원소를 top에서부터 순서대로 공간없이 출력한다.

 

test case

 

 

(전체코드)

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

int N; // 스택의 크기
int g_top = -1; // 스택 top 포인터 인덱스값

void push(char* stack, char c);
char pop(char* stack);
void peek(char* stack);
void duplicate(char* stack);
void upRotate(char* stack, int n);
void downRotate(char* stack, int n);
void print(char* stack);

int main() {
    int cnt;
    char cmd[6] = {0};
    char c;
    int n;

    scanf("%d", &N);
    char* stack = (char*)malloc(N * sizeof(char)); // 스택 생성 및 할당
    scanf("%d", &cnt);
    for (int i = 0; i < cnt; i++) {
        scanf("%s", cmd);
        if (strcmp(cmd, "PUSH") == 0) {
            scanf(" %c", &c);
            push(stack, c);
        }
        else if (strcmp(cmd, "POP") == 0) {
            pop(stack);
        }
        else if (strcmp(cmd, "PEEK") == 0) {
            peek(stack);
        }
        else if (strcmp(cmd, "DUP") == 0) {
            duplicate(stack);
        }
        else if (strcmp(cmd, "UpR") == 0) {
            scanf(" %d", &n);
            upRotate(stack, n);
        }
        else if (strcmp(cmd, "DownR") == 0) {
            scanf(" %d", &n);
            downRotate(stack, n);
        }
        else if (strcmp(cmd, "PRINT") == 0) {
            print(stack);
        }
    }

    return 0;
}

void push(char* stack, char c) {
    if (g_top + 2 > N) {
        printf("Stack FULL\n");
        return;
    }
    stack[++g_top] = c;
}

char pop(char* stack) {
    if (g_top <= -1) {
        printf("Stack Empty\n");
        return 0;
    }
    return stack[g_top--];
}

void peek(char* stack) {
    if (g_top <= -1) {
        printf("Stack Empty\n");
        return;
    }
    printf("%c", stack[g_top]);
}

void duplicate(char* stack) {
    if (g_top + 2 > N) {
        printf("Stack FULL\n");
        return;
    }
    push(stack, pop(stack));
    push(stack, stack[g_top]);
}

// 0 0 0 3 2 1
// upRotate(stack, n);
// 0 0 0 1 3 2
void upRotate(char* stack, int n) {
    if (n > g_top + 1) {
        return;
    }
    int temp = stack[g_top];
    for (int i = 0; i < n - 1; i++) {
        stack[g_top - i] = stack[g_top - (i + 1)];
    }
    stack[g_top - (n - 1)] = temp;
}

// 0 0 0 3 2 1
// downRotate(stack, n);
// 0 0 0 2 1 3
void downRotate(char* stack, int n) {
    if (n > g_top + 1) {
        return;
    }
    int temp = stack[g_top - (n - 1)]; 
    for (int i = 0; i < n - 1; i++) {
        stack[g_top - (n - 1 - i)] = stack[g_top - (n - 2 - i)];
    }
    stack[g_top] = temp;
}

void print(char* stack) {
    if (g_top <= -1) {
        return;
    }
    for (int i = g_top; i >= 0; i--) {
        printf("%c", stack[i]);
    }
    printf("\n");
}

/*
4
10
POP
PUSH s
PUSH t
PUSH a
PUSH r
PRINT
UpR 3
PRINT
PUSH s
PEEK

Stack Empty
rats
atrs
Stack FULL
a
*/

 

 

 

 

 

 

 

참고) 단일연결리스트로 구현한 스택

// 단일연결리스트로 스택 구현
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct NODE {
    char c;
    struct NODE* next; 
} NODE;

typedef struct STACK {
    NODE* top; // 헤드포인터
} STACK;

void push(STACK* stack, char c);
char pop(STACK* stack);
void peek(STACK* stack);
void print(STACK* stack);

int main() {
    int cnt;
    char cmd[6] = {0};
    char c;
    int n;

    STACK* stack = (STACK*)malloc(1 * sizeof(STACK)); // 스택 생성 및 할당
    stack->top = NULL;
    scanf("%d", &cnt);
    for (int i = 0; i < cnt; i++) {
        scanf("%s", cmd);
        if (strcmp(cmd, "PUSH") == 0) {
            scanf(" %c", &c);
            push(stack, c);
        }
        else if (strcmp(cmd, "POP") == 0) {
            pop(stack);
        }
        else if (strcmp(cmd, "PEEK") == 0) {
            peek(stack);
        }
        else if (strcmp(cmd, "PRINT") == 0) {
            print(stack);
        }
    }

    free(stack);
    return 0;
}

void push(STACK* stack, char c) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE));
    newNode->c = c;
    newNode->next = stack->top;
    stack->top = newNode;
}

char pop(STACK* stack) {
    if (stack->top == NULL) {
        printf("STACK Empty\n");
        return 0;
    }
    NODE* newNode = stack->top;
    char temp = newNode->c;
    stack->top = newNode->next;
    free(newNode);
    return temp;
}

void peek(STACK* stack) {
    if (stack->top == NULL) {
        printf("STACK Empty\n");
        return;
    }
    printf("%c\n", stack->top->c);
}

void print(STACK* stack) {
    if (stack->top == NULL) {
        printf("STACK Empty\n");
        return;
    }

    NODE* cur = stack->top;
    while (cur != NULL) {
        printf("%c", cur->c);
        cur = cur->next;
    }
    printf("\n");
}

/*
9
POP
PUSH s
PUSH t
PUSH a
PUSH r
PRINT
PEEK
PUSH s
PEEK

STACK Empty
rats
r
s
*/

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국)