[6] 스택 ② 배열을 이용한 스택 알고리즘(ADT)

728x90

1. 스택(Stack)

아래 블로그를 참조했다.

[자료구조] 4. 스택(Stack)이란? / 연산, 구현방법

이번 포스팅에서는 스택의 개념과 구조, 연산과 함께 스택을 각각 정적 및 동적으로 구현하는 방법에 대해서 정리해보았습니다. 📌 주요 개념 ✔️ 스택(Stack)이란? ✔️ 스택 vs 리스트 vs 큐 (비

roi-data.com

스택이란 데이터를 일시적으로 저장하기 위해 사용하는 자료 구조이다.

스택(stack)은 말 그대로 '쌓아놓은 더미'를 뜻하며, 데이터가 추가되고 삭제되는 과정이 마치 프링글스를 먹고 추가하는 과정과 비슷하다.

※ 후입선출 (LIFO: Last-In First-Out)

스택의 가장 큰 특징은 후입선출('LIFO')이다.

후입 선출이란 가장 최근에 들어온 데이터가 가장 먼저 나간다는 뜻으로, 이는 선입선출(먼저 들어온 데이터가 먼저 나감)의 방식인 '큐(Queue)' 와의 가장 큰 차이점 이라고도 할 수 있다.

※ 스택 vs. 큐 vs. 리스트

스택, 큐 모두 리스트 자료구조의 특별한 경우이며, 이들 간에는 공통점과 차이점을 지닌다.

자료구조	공통점	차이점
리스트(List)	선형 자료 구조, 순서가 있다	읽기, 삽입(insert)과 삭제(delete)를 리스트의 어느 곳에서나 행함
스택(Stack)		삽입(insert)과 삭제(delete)를 리스트의 한쪽(top) 에서 행함
큐(Queue)		삽입(insert)은 리스트의 한쪽(rear)에서 하고, 삭제(delete)는 삽입의 반대쪽(front)에서 행함

2. 스택의 구조 & 사용

스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 용이한 자료구조이다.

스택의 사용

스택의 사용 예시는 아래와 같다. 우리 삶에서 빈번하게 사용되어지는 것을 확인할 수 있다.

후위 표기법 계산: 수식을 후위 표기법으로 변환하여 스택을 사용하여 계산할 수 있다. 이때, 연산자와 피연산자를 스택에 저장하고 연산자를 만나면 스택에서 필요한 피연산자를 꺼내어 연산을 수행한다.
웹 브라우저의 뒤로/앞으로 가기 기능: 웹 브라우저에서 사용자가 방문한 웹 페이지의 URL을 스택에 저장하여 뒤로 가기 기능을 구현할 수 있다. 사용자가 뒤로 가기를 클릭하면 스택에서 가장 최근에 방문한 페이지의 URL을 꺼내어 표시하고, 앞으로 가기를 클릭하면 다시 스택에 해당 URL을 저장한다.
문자열 괄호 검사: 괄호가 제대로 닫혔는지 검사할 때 스택을 활용할 수 있다. 여는 괄호를 만나면 스택에 push 하고, 닫는 괄호를 만나면 스택에서 pop 하여 여는 괄호와 쌍을 이루는지 확인한다. 모든 괄호를 검사한 후에도 스택이 비어있지 않거나 여는 괄호가 남아있다면 올바른 괄호가 아니다.
후위 표현식에서 중위 표현식으로 변환: 후위 표현식을 중위 표현식으로 변환할 때 스택을 사용할 수 있다. 후위 표현식을 왼쪽에서 오른쪽으로 읽으면서 피연산자는 그대로 출력하고, 연산자를 만나면 스택에 저장된 피연산자를 꺼내어 중위 표현식에 삽입한다.

스택의 구조

상단(stack top) : 스택에서 입출력이 이루어지는 부분
하단(stack bottom): 반대쪽 바닥 부분
요소(element): 스택에 저장되는 것
공백 스택(empty stack): 공백 상태의 스택
포화 스택(full stack): 포화 상태의 스택

3. 스택 추상자료형

스택을 추상 자료형으로 정의해 보았을 때, 스택(Stack)은 후입선출(LIFO)의 접근방법을 유지하는 0개 이상의 요소를 지닌 선형 리스트의 일종이라 할 수 있다.

1) 스택 ADT (추상데이터타입)

- 객체: n개의 요소(element)들의 선형 리스트

연산	기능
init()	스택을 초기화
create()	스택을 생성
is_empty(s)	스택이 비어있는지 검사
is_full(s)	스택이 가득 찼는지 검사
push(e)	스택의 맨 위에 요소 e 추가
pop(s)	스택의 맨 위 요소를 삭제
peek(s)	스택의 맨 위 요소를 삭제하지 않고 반환

2) 스택의 연산

스택에 요소를 추가/삭제하는 연산과, 현재 스택 상태를 검사하는 연산들로 구성된다.

연산	기능
top()	스택 맨 위에 있는 데이터 값 반환
push()	스택에 데이터 삽입
pop()	스택에서 데이터 삭제하여 반환
isempty()	스택에 원소가 없으면 'True', 있으면 'False' 값 반환
isfull()	스택에 원소가 없으면 'False', 있으면 'True' 값 반환

4. 스택 알고리즘 구현

Ⅰ . 배열을 이용한 스택 구현

구조체 선언

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

typedef char element;
#define MAX_SIZE 100 //배열 스택 사이즈

typedef struct {
    int data[MAX_SIZE]; // 스택의 데이터를 저장할 배열
    int top; // 스택의 최상위 원소의 인덱스를 나타내는 변수
    int max;
} Stack;

typedef char element; : 스택의 요소(element)의 데이터 타입을 char로 정의한다.
#define MAX_SIZE 100 : 배열 스택의 최대 크기를 정의한다. 이 값은 스택이 저장할 수 있는 최대 요소 수를 나타낸다.
typedef struct {... } Stack; : 스택 구조체를 정의한다.
스택은 배열로 구현되며, 구조체 멤버로는 데이터 배열(data), 최상위 원소의 인덱스(top), 그리고 스택의 최대 크기(max)를 갖는다.
int data[MAX_SIZE]; : 스택의 데이터를 저장할 정수형 배열을 선언합니다. 이 배열은 스택의 실제 데이터를 저장한다.
int top; : 스택의 최상위 원소의 인덱스를 나타내는 변수입니다. 스택에 데이터가 없을 때는 -1의 값을 가지며, 스택에 데이터가 추가될 때마다 증가한다.
int max; : 스택의 최대 크기를 나타내는 변수입니다. 이 값은 스택이 저장할 수 있는 최대 요소의 수를 나타낸다.

initStack : 스택 초기화 함수

void initStack(Stack *stack){
    stack->top = -1; 
    /*
    스택 최상위 원소의 인덱스를 -1로 설정 : 0 부터 유효 인덱스
    ☑ 0번 인덱스 부터 값이 저장되도록 설정
    ☑ 최상위 인덱스 : 맨 마지막에 저장된 데이터 값
    */
}

• 스택을 사용하기 전에 초기화해야 하므로, 스택 구조체를 가리키는 포인터를 매개변수로 받아 해당 스택을 초기화한다.

• 여기서 stack->top = -1; 코드는 스택의 최상위 원소의 인덱스를 -1로 설정하는 역할을 한다. 이 값은 스택이 비어있음을 나타낸다.

• 스택에서 데이터가 추가될 때마다 top 값이 증가하므로, 최상위 원소의 인덱스가 0부터 시작하도록 -1로 초기화한다.

이렇게 하면 스택의 최상위 인덱스가 맨 마지막에 저장된 데이터 값을 가리키게 되므로,

스택에서 가장 최근에 추가된 데이터를 쉽게 참조할 수 있다.

isEmpty: 스택이 비어있는지 여부를 확인하는 함수

주어진 스택이 비어있는지 여부를 판별한다.

• 스택이 비어있으면 stack->top 값이 -1이므로, 이 값을 비교하여 결과를 반환한다.

• stack->top이 -1이면 스택이 비어있으므로 1(참)을 반환하고, 그렇지 않으면 0(거짓)을 반환한다.

int isEmpty(Stack *stack){
    return (stack->top == -1);
}

isFull : 스택이 가득 찼는지 여부를 확인하는 함수

• 주어진 스택이 가득 찼는지 여부를 판별한다.

1. 스택이 가득 차면 stack->top 값이 MAX_SIZE - 1과 같아지므로, 이 값을 비교하여 결과를 반환한다.

2. tack->top이 MAX_SIZE - 1과 같으면 스택이 가득 찼으므로 1(참)을 반환하고, 그렇지 않으면 0(거짓)을 반환한다.

int isFull(Stack *stack){
    return (stack->top ==( MAX_SIZE -1 ));
    /*
    스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    → stack->top가 (MAX_SIZE-1)이면 가득 찬 상태.
    → stack->top가 (MAX_SIZE-1)보다 크다면 과포화 상태임.
    */
}

push : 스택에 데이터를 추가하는 함수

1. 스택의 top을 증가시킨다. 새로운 데이터를 추가하기 위해 스택의 인덱스를 다음 위치로 이동시키기 위함이다.

2. 스택의 top 위치에 새로운 데이터 e를 저장한다.

• 함수의 결과로, 스택에는 top 인덱스 위치에 새로운 데이터가 추가되고, top 인덱스는 새로운 데이터가 추가된 위치를 가리킨다.

void push(Stack *stack, element e){
    // if(isFull(stack)){printf("Stack FULL\n"); return ;}
    stack->top ++; //스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    stack->data[stack->top] = e;
}

pop : 스택에서 데이터를 제거하고 반환하는 함수

1. 스택의 top 위치에 있는 데이터를 가져와 변수 del에 저장합니다. 이것은 제거될 데이터를 임시로 저장하기 위함이다.

2. 그 후, 스택의 top 값을 감소시킵니다. 이는 스택에서 데이터가 제거되었음을 나타낸다.

3. 제거된 데이터를 반환한다.

• 함수의 결과로, 스택에서 제거된 데이터를 호출한 곳으로 전달하여 호출한 곳에서 필요한 작업을 수행할 수 있도록 한다.

element pop(Stack *stack){
    // if(isEmpty(stack)) {printf("Stack Empty\n");return -1;}
    element del = stack->data[stack->top];
    stack->top --;
    return del;
}

size : 스택에 저장된 데이터의 개수를 반환하는 함수

1. 스택의 (top 값 + 1)을 반환한다.

2. 스택의 top값은 스택의 맨 위 요소의 인덱스(0부터 시작)를 나타내므로, 스택에 저장된 노드의 개수는 (top + 1) 이어야 한다.

int size(Stack *stack){
    return stack->top + 1 ;
}

peek: 스택의 top 데이터를 반환하는 함수

• 스택의 top 인덱스의 데이터를 반환한다. 이때 스택의 데이터를 추가 혹은 제거를 해서는 안된다.

element peek(Stack *stack){ //top과 기능 동일
    // if(isEmpty(stack)) printf("Stack Empty\n");
    return stack->data[stack->top];
}

duplicate : 스택 복제 함수

1. 스택이 이미 꽉 차있는지 확인한다.
2. 스택의 top에 있는 데이터를 pop 하여 임시로 저장한다.
3. pop 한 데이터를 두 번 push 하여 스택의 top 바로 아래에 두 번 저장한다.
4. 위 과정에 따라, 스택의 top에 있는 데이터가 두 번씩 스택에 저장되므로 스택의 크기는 두 배가 된다.

void duplicate(Stack *stack){
    // if(isFull(stack)){printf("Stack FULL\n"); return ;}
    element dup = pop(stack);
    push(stack,dup); push(stack,dup);
}

upRotate : 상향 회전 함수

• upRotate는 스택에서 상위 n개의 원소를 회전시키는 기능을 한다.

• 구체적으로는 가장 상위에 있는 원소를 맨 아래로 이동시키고, 나머지 원소들은 한 칸씩 위로 이동하여 회전하는 것이다.

함수의 동작은 다음과 같다:

스택의 가장 상위에 있는 원소를 임시 변수 e에 저장한다.
상위 n개의 원소를 한 칸씩 위로 이동시킨다. 이 때, 상위 원소부터 하위 원소까지 차례대로 한 칸씩 위로 올려야 하므로, for 루프를 사용하여 각 원소를 한 칸씩 위로 이동시킨다.
이동이 완료된 후, 임시 변수에 저장된 가장 상위 원소를 맨 아래 위치로 이동시킨다.
결과적으로 상위 n개의 원소가 회전된다.

• 이러한 회전은 스택에서 가장 최근에 추가된 데이터가 가장 위에 위치하도록 하는데 유용하다.

• 일반적으로 스택에서 데이터를 처리할 때, 최근에 추가된 데이터에 더 관심이 많은 경우에 회전 기능을 사용할 수 있다.

void upRotate(Stack *stack, int n){
    // if(n > stack->top){printf("Stack FULL\n"); return ;}
    element e = stack->data[stack->top];
    for(int i=0;i<n;i++){
        stack->data[stack->top - i] = stack->data[stack->top - i - 1];
        // stack->data[stack->top - n + 1 + i] = stack->data[stack->top - n + 1 + i]
    }stack->data[stack->top - n + 1] = e;
}

/*
upRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 
예를 들면 n 이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면 데이터를 하나씩 위 쪽으로 이동시킨다. 맨 위쪽 (top)의 std1은 n-1번 아래쪽으로 이동해서 스택의 결과는 elem2, elem3, elem1, ...이된다.
단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.
*/

downRotate: 하향 회전 함수

• 주어진 upRotate 함수는 스택에서 상위 n개의 원소를 회전시키는 기능을 수행한다.

• 구체적으로는 가장 상위에 있는 원소를 맨 아래로 이동시키고, 나머지 원소들은 한 칸씩 위로 이동하여 회전한다.

함수의 동작은 다음과 같다:

스택의 가장 상위에 있는 원소를 임시 변수 e에 저장한다.
상위 n개의 원소를 한 칸씩 위로 이동시킨다.
for 루프를 사용하여 각 원소를 한 칸씩 위로 이동시킨다.
이동은 가장 상위 원소부터 시작하여 하위 원소까지 차례대로 이루어진다.
이동이 완료된 후, 임시 변수에 저장된 가장 상위 원소를 맨 아래 위치로 이동시킨다.
상위 n개의 원소가 회전된다.

void downRotate(Stack *stack, int n){
    // if(n > stack->top){printf("Stack FULL\n"); return ;}
    element e = stack->data[stack->top - n + 1];
    for(int i = stack->top - n + 1 ; i<= stack->top ; i++){
        stack->data[i] = stack->data[i+1];
    }stack->data[stack->top] = e;
}
/*
downRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 예를 들면 n 이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면 데이터를 하나씩 d 아래쪽으로 이동시킨다. top에서부터 n번째의 데이터는 top으로 이동해서, 스택의 결과
는 elem3, elem1, elem2, ...이된다.
단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.
*/

print : 스택 데이터 출력 함수

• 주어진 스택의 모든 원소를 출력한다.

• 스택의 가장 상위에 있는 원소부터 하위에 있는 원소까지 역순으로 출력한다.

함수의 동작은 다음과 같다:

for 루프를 사용하여 스택의 가장 상위부터 가장 하위까지의 모든 원소를 반복적으로 출력한다.
이를 위해 i 변수는 stack->top부터 0까지 감소하면서 반복된다.
각 반복에서는 stack->data [i] 위치에 있는 원소를 출력한다. 이는 현재 인덱스에 해당하는 원소를 출력하는 것을 의미한다.
모든 원소 출력이 완료된 후에는 줄 바꿈을 추가하여 출력 결과를 보기 좋게 정리한다.

void print(Stack *stack){
    // printf("[TOP] ");
    for(int i=stack->top ; i>=0 ; i--){
        printf("%c",stack->data[i]);
        // printf("[%c] ",stack->data[i]);
    }
    // printf("[BOTTOM]");
    printf("\n");
}

main 함수

위 코드는 주어진 연산에 따라 스택을 조작하고, 각각의 조작에 대한 결과를 출력한다.

스택을 초기화하고, 스택의 크기 N과 연산의 개수 M을 입력받는다.
각 연산에 따라 다음을 수행한다:
- PUSH: 스택에 데이터를 추가한다. 단, 스택이 가득 찬 경우 "Stack FULL"을 출력한다.
- POP: 스택에서 데이터를 제거한다. 단, 스택이 비어 있는 경우 "Stack Empty"를 출력한다.
- PEEK: 스택의 최상위 데이터를 조회하여 출력한다. 단, 스택이 비어 있는 경우 "Stack Empty"를 출력한다.
- DUP: 스택의 최상위 데이터를 복제하여 스택에 추가한다. 단, 스택이 가득 찬 경우 "Stack FULL", 비어 있는 경우 "Stack Empty"를 출력한다.
- UpR: 스택의 상위 n개의 데이터를 회전시킨다. 단, n이 스택의 크기를 초과하는 경우 무시한다.
- DownR: 스택의 상위 n개의 데이터를 역순으로 회전시킨다. 단, n이 스택의 크기를 초과하는 경우 무시한다.
- PRINT: 스택의 모든 데이터를 출력한다.
각 연산이 완료된 후 프로그램을 종료한다.

int main() {
    Stack stack;
    initStack(&stack);

    int N, M, n;
    char input[10] = { };
    char data;
    scanf("%d", &N);//stack의 크기 N
    scanf("%d", &M);//연산의 개수
    getchar();


    for (int i = 0; i < M; i++) {
        scanf("%s", input);getchar();

        if (strcmp(input, "PUSH") == 0) {
            scanf("%c", &data);getchar();
            if (stack.top == (N-1)) {printf("Stack FULL\n");continue;}
            push(&stack, data);
        }
        else if (strcmp(input, "POP") == 0) {
            if (stack.top == -1 ) {printf("Stack Empty\n");continue;}
            data = pop(&stack);
        }
        else if (strcmp(input, "PEEK") == 0) {
            if (stack.top == -1 ) {printf("Stack Empty\n");continue;}
            element e = peek(&stack);
            printf("%c\n",e);
        }
        else if (strcmp(input, "DUP") == 0) {
            if (stack.top == (N-1)) {printf("Stack FULL\n");continue;}
            if (stack.top == -1 ) {printf("Stack Empty\n");continue;}
            duplicate(&stack);

        }
        else if (strcmp(input, "UpR") == 0) {
            scanf("%d", &n); getchar();
            if (n > stack.top + 1) continue;
            upRotate(&stack, n);
        }
        else if (strcmp(input, "DownR") == 0) {
            scanf("%d", &n);getchar();
            if (n > stack.top + 1) continue;
            downRotate(&stack, n);
        }
        else if (strcmp(input, "PRINT") == 0) {
            print(&stack);
        }

    }
    return 0;
}

전체 알고리즘 : ADT

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

typedef char element;
#define MAX_SIZE 100 //배열 스택 사이즈

typedef struct {
    int data[MAX_SIZE]; // 스택의 데이터를 저장할 배열
    int top; // 스택의 최상위 원소의 인덱스를 나타내는 변수
    int max;
} Stack;

void initStack(Stack *stack){
    stack->top = -1; 
    /*
    스택 최상위 원소의 인덱스를 -1로 설정 : 0 부터 유효 인덱스
    ☑ 0번 인덱스 부터 값이 저장되도록 설정
    ☑ 최상위 인덱스 : 맨 마지막에 저장된 데이터 값
    */
}

int isEmpty(Stack *stack){
    return (stack->top == -1);
}

int isFull(Stack *stack){
    return (stack->top ==( MAX_SIZE -1 ));
    /*
    스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    → stack->top가 (MAX_SIZE-1)이면 가득 찬 상태.
    → stack->top가 (MAX_SIZE-1)보다 크다면 과포화 상태임.
    */
}

void push(Stack *stack, element e){
    // if(isFull(stack)){printf("Stack FULL\n"); return ;}
    stack->top ++; //스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    stack->data[stack->top] = e;
}

element pop(Stack *stack){
    // if(isEmpty(stack)) {printf("Stack Empty\n");return -1;}
    element del = stack->data[stack->top];
    stack->top --;
    return del;
}


int size(Stack *stack){
    return stack->top + 1 ;
}

element peek(Stack *stack){ //top과 기능 동일
    // if(isEmpty(stack)) printf("Stack Empty\n");
    return stack->data[stack->top];
}

void duplicate(Stack *stack){
    // if(isFull(stack)){printf("Stack FULL\n"); return ;}
    element dup = pop(stack);
    push(stack,dup); push(stack,dup);
}
/*
1. 스택이 이미 꽉 차있는지 확인합니다.
2. 스택의 top에 있는 데이터를 pop하여 임시로 저장합니다.
3. pop한 데이터를 두 번 push하여 스택의 top 
    바로 아래에 두 번 저장합니다.
4.이렇게 하면 스택의 top에 있는 데이터가 
    두 번씩 스택에 저장되므로, 스택의 크기는 두 배가 됩니다. 
    주로 스택의 top에 있는 데이터를 복제하여 두 번 처리해야 할 때 사용됩니다.
*/

void upRotate(Stack *stack, int n){
    // if(n > stack->top){printf("Stack FULL\n"); return ;}
    element e = stack->data[stack->top];
    for(int i=0;i<n;i++){
        stack->data[stack->top - i] = stack->data[stack->top - i - 1];
        // stack->data[stack->top - n + 1 + i] = stack->data[stack->top - n + 1 + i]
    }stack->data[stack->top - n + 1] = e;
}

/*
upRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 
예를 들면 n 이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면 데이터를 하나씩 위 쪽으로 이동시킨다. 맨 위쪽 (top)의 std1은 n-1번 아래쪽으로 이동해서 스택의 결과는 elem2, elem3, elem1, ...이된다.
단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.
*/

void downRotate(Stack *stack, int n){
    // if(n > stack->top){printf("Stack FULL\n"); return ;}
    element e = stack->data[stack->top - n + 1];
    for(int i = stack->top - n + 1 ; i<= stack->top ; i++){
        stack->data[i] = stack->data[i+1];
    }stack->data[stack->top] = e;
}
/*
downRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 예를 들면 n 이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면 데이터를 하나씩 d 아래쪽으로 이동시킨다. top에서부터 n번째의 데이터는 top으로 이동해서, 스택의 결과
는 elem3, elem1, elem2, ...이된다.
단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.
*/

void print(Stack *stack){
    // printf("[TOP] ");
    for(int i=stack->top ; i>=0 ; i--){
        printf("%c",stack->data[i]);
        // printf("[%c] ",stack->data[i]);
    }
    // printf("[BOTTOM]");
    printf("\n");
}



int main() {
    Stack stack;
    initStack(&stack);

    int N, M, n;
    char input[10] = { };
    char data;
    scanf("%d", &N);//stack의 크기 N
    scanf("%d", &M);//연산의 개수
    getchar();


    for (int i = 0; i < M; i++) {
        scanf("%s", input);getchar();

        if (strcmp(input, "PUSH") == 0) {
            scanf("%c", &data);getchar();
            if (stack.top == (N-1)) {printf("Stack FULL\n");continue;}
            push(&stack, data);
        }
        else if (strcmp(input, "POP") == 0) {
            if (stack.top == -1 ) {printf("Stack Empty\n");continue;}
            data = pop(&stack);
        }
        else if (strcmp(input, "PEEK") == 0) {
            if (stack.top == -1 ) {printf("Stack Empty\n");continue;}
            element e = peek(&stack);
            printf("%c\n",e);
        }
        else if (strcmp(input, "DUP") == 0) {
            if (stack.top == (N-1)) {printf("Stack FULL\n");continue;}
            if (stack.top == -1 ) {printf("Stack Empty\n");continue;}
            duplicate(&stack);

        }
        else if (strcmp(input, "UpR") == 0) {
            scanf("%d", &n); getchar();
            if (n > stack.top + 1) continue;
            upRotate(&stack, n);
        }
        else if (strcmp(input, "DownR") == 0) {
            scanf("%d", &n);getchar();
            if (n > stack.top + 1) continue;
            downRotate(&stack, n);
        }
        else if (strcmp(input, "PRINT") == 0) {
            print(&stack);
        }

    }
    return 0;
}

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


*/

전체 알고리즘 : 입력 불필요 & 확인코드

코드는 [더 보기]을 클릭하여 확인한다.

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

typedef char element;
#define MAX_SIZE 100 //배열 스택 사이즈

typedef struct {
    int data[MAX_SIZE]; // 스택의 데이터를 저장할 배열
    int top; // 스택의 최상위 원소의 인덱스를 나타내는 변수
} Stack;

void initStack(Stack *stack){
    stack->top = -1; 
    /*
    스택 최상위 원소의 인덱스를 -1로 설정 : 0 부터 유효 인덱스
    ☑ 0번 인덱스 부터 값이 저장되도록 설정
    ☑ 최상위 인덱스 : 맨 마지막에 저장된 데이터 값
    */
}

int isEmpty(Stack *stack){
    return (stack->top == -1);
}

int isFull(Stack *stack){
    return (stack->top ==( MAX_SIZE -1 ));
    /*
    스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    → stack->top가 (MAX_SIZE-1)이면 가득 찬 상태.
    → stack->top가 (MAX_SIZE-1)보다 크다면 과포화 상태임.
    */
}

void push(Stack *stack, element e){
    if(isFull(stack)){printf("Stack is full.\n"); return ;}
    stack->top ++; //스택 데이터 인덱스는 0 ~ (MAX_SIZE-1)까지임.
    stack->data[stack->top] = e;
}

element pop(Stack *stack){
    if(isEmpty(stack)) {printf("Stack is empty.\n");return -1;}
    element del = stack->data[stack->top];
    stack->top --;
    return del;
}


int size(Stack *stack){
    return stack->top + 1 ;
}

element top(Stack *stack){
    if(isEmpty(stack)) printf("Stack is empty.\n");
    return stack->data[stack->top];
}

element peek(Stack *stack){ //top과 기능 동일
    if(isEmpty(stack)) printf("Stack is empty.\n");
    return stack->data[stack->top];
}

void duplicate(Stack *stack){
    if(isFull(stack)){printf("Stack is full.\n"); return ;}
    element dup = pop(stack);
    push(stack,dup); push(stack,dup);
}
/*

스택 ADT(추상 데이터 타입)에서 duplicate는 
    현재 스택의 top에 있는 데이터를 복제하여 
    스택의 top 바로 아래에 두 번 저장하는 기능을 말합니다. 
    
즉, 스택의 top에 있는 데이터를 하나 pop하여 
    그 값을 다시 두 번 push하는 것을 의미합니다.

일반적으로 스택 ADT에서 duplicate 함수는 다음과 같은 기능을 수행합니다:

1. 스택이 이미 꽉 차있는지 확인합니다.
2. 스택의 top에 있는 데이터를 pop하여 임시로 저장합니다.
3. pop한 데이터를 두 번 push하여 스택의 top 
    바로 아래에 두 번 저장합니다.
4.이렇게 하면 스택의 top에 있는 데이터가 
    두 번씩 스택에 저장되므로, 스택의 크기는 두 배가 됩니다. 
    주로 스택의 top에 있는 데이터를 복제하여 두 번 처리해야 할 때 사용됩니다.
------------------------------------------------------------------------------------------------
stack의 top에 있는 데이터를 pop해서 두 번 push 한다. 
stack이 이미 꽉 차있으면 “Stack FULL”을 출력한다.
*/

void upRotate(Stack *stack, int n){
    if(n > stack->top) return ;
    element e = stack->data[stack->top];
    for(int i=0;i<n;i++){
        stack->data[stack->top - i] = stack->data[stack->top - i - 1];
        // stack->data[stack->top - n + 1 + i] = stack->data[stack->top - n + 1 + i]
    }stack->data[stack->top - n + 1] = e;
}

/*
upRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 
예를 들면 n 이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면 데이터를 하나씩 위 쪽으로 이동시킨다. 맨 위쪽 (top)의 std1은 n-1번 아래쪽으로 이동해서 스택의 결과는 elem2, elem3, elem1, ...이된다.
단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.
*/

void downRotate(Stack *stack, int n){
    if(n > stack->top) return ;
    element e = stack->data[stack->top - n + 1];
    for(int i = stack->top - n + 1 ; i<= stack->top ; i++){
        stack->data[i] = stack->data[i+1];
    }stack->data[stack->top] = e;
}
/*
downRotate(stack, n): stack의 맨 위 n 개의 데이터를 회전시킨다. 예를 들면 n 이 3이고 stack의 top에서부터 elem1, elem2, elem3, .... 이 저장되어 있으면 데이터를 하나씩 d 아래쪽으로 이동시킨다. top에서부터 n번째의 데이터는 top으로 이동해서, 스택의 결과
는 elem3, elem1, elem2, ...이된다.
단, n이 데이터의 개수보다 큰 경우에는 아무 작업을 하지 않는다.
*/

void print(Stack *stack){
    printf("[TOP] ");
    for(int i=stack->top ; i>=0 ; i--){
        printf("[%c] ",stack->data[i]);
    }
    printf("[BOTTOM]");
    printf("\n");
}


int main(){
    Stack stack;
    initStack(&stack);

    printf("--------------------[push]--------------------\n");
    push(&stack,'s');push(&stack,'t');push(&stack,'a');push(&stack,'r');print(&stack);
    
    printf("\n-----------------[duplicate]----------------\n");
    duplicate(&stack);print(&stack);

    printf("\n-------------------[pop]---------------------\n");
    printf("[%c] is poped.\n",pop(&stack));
    
    printf("\n-----------------[upRotate]-----------------\n");
    upRotate(&stack,3);
    print(&stack);

    printf("\n-----------------[downRotate]---------------\n");
    downRotate(&stack,3);
    print(&stack);

    printf("\n-------------------[peek]-------------------\n");
    printf("[%c] is peeked.\n",peek(&stack));

    printf("\n--------------------[top]-------------------\n");
    printf("[%c] is top.\n",top(&stack));

}

728x90

저작자표시

'Datastructure > [6] 스택' 카테고리의 다른 글

[6] 스택 ⑥ 스택의 응용 : 중위수식 변환 (0)	2024.05.17
[6] 스택 ⑤ 스택의 응용 : 괄호 (0)	2024.05.15
[6] 스택 ④ 스택의 응용 : 스택 ADT (0)	2024.05.13
[6] 스택 ③ 연결리스트를 이용한 스택 알고리즘(ADT) (0)	2024.05.13
[6] 스택 ① (0)	2024.03.02

일	월	화	수	목	금	토
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

우당탕탕 코딩 제작소

[6] 스택 ② 배열을 이용한 스택 알고리즘(ADT)

1. 스택(Stack)

2. 스택의 구조 & 사용

스택의 사용

스택의 구조

3. 스택 추상자료형

1) 스택 ADT (추상데이터타입)

2) 스택의 연산

4. 스택 알고리즘 구현

Ⅰ . 배열을 이용한 스택 구현

구조체 선언

initStack : 스택 초기화 함수

isEmpty: 스택이 비어있는지 여부를 확인하는 함수

isFull : 스택이 가득 찼는지 여부를 확인하는 함수

push : 스택에 데이터를 추가하는 함수

pop : 스택에서 데이터를 제거하고 반환하는 함수

size : 스택에 저장된 데이터의 개수를 반환하는 함수

peek: 스택의 top 데이터를 반환하는 함수

duplicate : 스택 복제 함수

upRotate : 상향 회전 함수

downRotate: 하향 회전 함수

print : 스택 데이터 출력 함수

main 함수

전체 알고리즘 : ADT

전체 알고리즘 : 입력 불필요 & 확인코드

'Datastructure > [6] 스택' 카테고리의 다른 글

티스토리툴바

[6] 스택 ② 배열을 이용한 스택 알고리즘(ADT)

1. 스택(Stack)

2. 스택의 구조 & 사용

스택의 사용

스택의 구조

3. 스택 추상자료형

1) 스택 ADT (추상데이터타입)

2) 스택의 연산

4. 스택 알고리즘 구현

Ⅰ . 배열을 이용한 스택 구현

구조체 선언

initStack : 스택 초기화 함수

isEmpty: 스택이 비어있는지 여부를 확인하는 함수

isFull : 스택이 가득 찼는지 여부를 확인하는 함수

push : 스택에 데이터를 추가하는 함수

pop : 스택에서 데이터를 제거하고 반환하는 함수

size : 스택에 저장된 데이터의 개수를 반환하는 함수

peek: 스택의 top 데이터를 반환하는 함수

duplicate : 스택 복제 함수

upRotate : 상향 회전 함수

downRotate: 하향 회전 함수

print : 스택 데이터 출력 함수

main 함수

전체 알고리즘 : ADT

전체 알고리즘 : 입력 불필요 & 확인코드

'Datastructure > [6] 스택' 카테고리의 다른 글

'Datastructure/[6] 스택' 관련글

티스토리툴바

size : 스택에 저장된 데이터의 개수를 반환하는 함수