[6] 스택 ③ 연결리스트를 이용한 스택 알고리즘(ADT)

연결리스트를 이용한 스택 알고리즘

구조체 선언

스택(Stack) 자료구조를 구현하는 C 프로그램이다.

 

• element라는 이름으로 char 형을 새로운 타입으로 정의한다.
• 스택의 노드를 정의하는 구조체를 선언한다.
• 각 노드는 데이터를 담는 int 타입의 data 필드와 다음 노드를 가리키는 포인터인 next 필드를 가진다.
• 스택을 정의하는 구조체를 선언한다. 스택은 최상위 노드를 가리키는 포인터인 top 필드를 가진다.
• 각각의 노드는 스택의 최상위 노드를 가리키는 top을 통해 연결된다.

typedef char element;

// 스택 노드 구조체 정의
typedef struct StackNode {
    int data;           // 데이터
    struct StackNode* next;  // 다음 노드를 가리키는 포인터
} StackNode;

// 스택 구조체 정의
typedef struct Stack{
    StackNode* top;  
    // 스택의 최상위 노드를 가리키는 포인터
} Stack;

 

init: 스택 초기화 함수

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

• 스택의 최상위 원소(포인터)를 NULL로 설정하여 스택이 비어있음을 나타낸다.

// 스택 초기화 함수
void init(Stack* stack) {stack->top = NULL;}

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

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

// 스택이 비어있는지 확인하는 함수
int isEmpty(Stack* stack) {return(stack->top == NULL);

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

스택에 데이터를 추가하는 기능을 수행한다.

 

• 스택 노드의 크기만큼 메모리를 할당하고, 이를 StackNode* 형으로 형변환하여 new 포인터에 저장한다.
• 메모리 할당이 실패했다면 오류 메시지를 출력하고 함수를 종료한다.
• 새로운 노드의 data 필드에 추가할 데이터를 설정한다.
• 새로운 노드의 next 포인터를 현재 스택의 최상위 노드를 가리키도록 설정한다.
• 스택의 top 포인터를 새로 추가된 노드로 업데이트한다. 새로운 노드가 이제 스택의 최상위 노드가 된다.

// 스택에 데이터를 추가하는 함수
void push(Stack* stack, element data) {
    StackNode* new = (StackNode*)malloc(sizeof(StackNode)); // 새로운 노드 동적 할당
    if (new == NULL) {fprintf(stderr, "메모리 할당 오류\n");return;}
    new->data = data;  // 데이터 설정

    new->next = stack->top;  // 새로운 노드의 다음 노드를 현재의 top 노드로 설정
    stack->top = new;  // 새로운 노드를 스택의 top으로 설정
}

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

스택에서 데이터를 제거하고 반환하는 기능을 수행한다.

 

• isEmpty 함수를 사용하여 스택이 비어있는지 확인한다. 
• 현재의 최상위 노드를 임시 변수에 저장한다.
• 제거할 노드의 데이터를 임시 변수에 저장한다.
• 최상위 노드를 다음 노드로 변경한다. 즉, 스택에서 최상위 노드를 제거하는 것이다.
• 제거된 노드의 메모리를 해제한다.
• 제거된 데이터를 반환한다.

// 스택에서 데이터를 제거하고 반환하는 함수
element pop(Stack* stack) {
    if (isEmpty(stack)) {
        fprintf(stderr, "스택이 비어있습니다.\n");
        exit(1);
    }
    StackNode* temp = stack->top;  // 현재의 top 노드를 임시 변수에 저장
    element data = temp->data;  // 제거할 노드의 데이터를 저장
    stack->top = temp->next;  // top을 다음 노드로 변경
    free(temp);  // 제거된 노드 메모리 해제
    return data;  // 제거된 데이터 반환
}

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

스택의 연결리스트에 저장된 스택의 개수를 반환하는 기능을 수행한다.

 

• 스택의 개수를 저장할 변수 count를 0으로 초기화한다.
• 현재의 최상위 노드를 나타내는 포인터 current를 선언하고, 이를 스택의 최상위 노드를 가리키도록 설정한다.
• current가 NULL이 아닐 때까지 반복한다. 각 반복마다 count를 증가시키고, current를 다음 노드로 이동한다.
• 스택의 연결리스트에 저장된 스택의 개수를 반환한다.

// 스택의 연결리스트에 저장된 스택의 개수를 반환하는 함수
int size(Stack* stack) {
    int count = 0;
    StackNode* current = stack->top;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

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

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

// 스택에서 최상위 데이터를 반환하는 함수 (제거하지 않음)
element peek(Stack* stack) {
    element e = stack->top->data;
    return e;
}

duplicate : 스택 복제 함수

스택의 최상위에 있는 데이터를 복제하여 스택에 추가하는 기능을 수행한다.

 

• pop 함수를 사용하여 스택의 최상위 데이터를 제거하고 변수 dup에 저장한다.
• dup 변수에 저장된 데이터를 두 번 스택에 추가한다. 따라서 스택의 최상위에는 원래의 데이터가 두 개 추가된다.

void duplicate(Stack *stack){
    element dup = pop(stack);
    push(stack,dup); push(stack,dup);
}

upRotate : 상향 회전 함수

스택의 맨 위 n 개의 데이터를 회전시키는 기능을 수행한다.

 

• 스택이 비어있는지 확인한다. 만약 스택이 비어있다면 오류 메시지를 출력하고 함수를 종료한다.
• n 값이 음수인지 확인한다. 만약 음수이면 오류 메시지를 출력하고 함수를 종료한다.
• 스택의 최상위에 있는 데이터를 제거하고 변수 e에 저장한다.
• 임시 스택 tempStack을 선언하고 초기화한다.
• 임시 변수 tmp를 선언한다.
• 스택에서 최상위 데이터부터 n-1 개를 임시 스택에 넣는다. 이렇게 하면 스택에서는 원하는 위치에 있는 데이터가 제거된다.
• 변수 e에 저장된 데이터를 스택의 맨 위로 넣는다. 이렇게 하면 스택에서 n번째 위치에 데이터가 추가된다.
• 임시 스택에 저장된 데이터를 다시 원래 스택으로 옮긴다. 이렇게 하면 스택의 맨 위에 있는 데이터들이 회전된다.

 

// 스택의 맨 위 n 개의 데이터를 회전시키는 함수
void upRotate(Stack *stack, int n) {
    if (isEmpty(stack)) {
        fprintf(stderr, "스택이 비어있습니다.\n");
        return;
    }
    if (n < 0) {
        fprintf(stderr, "잘못된 인덱스입니다.\n");
        return;
    }
    element e = pop(stack); // 스택의 top에 있는 값을 pop하여 변수 e에 저장
    Stack tempStack;
    init(&tempStack);

    element tmp;
    for(int i=0;i<n-1;i++){tmp = pop(stack);push(&tempStack,tmp);}
    push(stack, e); // n번째 위치에 pop한 값을 다시 스택에 push
    for(int i=0;i<n-1;i++){tmp = pop(&tempStack);push(stack,tmp);}
}

downRotate: 하향 회전 함수

스택의 맨 위 n 개의 데이터를 반시계 방향으로 회전시키는 기능을 수행한다.

 

• 스택이 비어있는지 확인한다. 만약 스택이 비어있다면 오류 메시지를 출력하고 함수를 종료한다.
• n 값이 음수인지 확인한다. 만약 음수이면 오류 메시지를 출력하고 함수를 종료한다.
• 임시 스택 tempStack을 선언하고 초기화한다.
• 임시 변수 tmp를 선언한다.
• 스택에서 최상위 데이터부터 n-1 개를 임시 스택에 넣는다. 이렇게 하면 스택에서는 원하는 위치에 있는 데이터가 제거된다.
• 스택의 최상위에 있는 데이터를 제거하고 변수 e에 저장한다.
• 임시 스택에 저장된 데이터를 다시 원래 스택으로 옮긴다.
• 변수 e에 저장된 데이터를 스택의 맨 위로 넣는다. 이렇게 하면 스택의 맨 아래에 있는 데이터가 회전하여 맨 위로 올라간다.

// 스택의 맨 위 n 개의 데이터를 반시계 방향으로 회전시키는 함수
void downRotate(Stack* stack, int n) {
if (isEmpty(stack)) {
        fprintf(stderr, "스택이 비어있습니다.\n");
        return;
    }
    if (n < 0) {
        fprintf(stderr, "잘못된 인덱스입니다.\n");
        return;
    }

    Stack tempStack;
    init(&tempStack);

    element tmp;
    for(int i=0;i<n-1;i++){tmp = pop(stack);push(&tempStack,tmp);}
    element e = pop(stack); // 스택의 top에 있는 값을 pop하여 변수 e에 저장
    for(int i=0;i<n-1;i++){tmp = pop(&tempStack);push(stack,tmp);}
    push(stack, e); // n번째 위치에 pop한 값을 다시 스택에 push
}

print : 스택 데이터 출력 함수

스택의 모든 데이터를 출력하는 기능을 수행한다.

• printf("[ TOP ] ");: 스택의 맨 위를 나타내는 [ TOP ]를 출력한다.
• 현재의 최상위 노드를 나타내는 포인터 current를 선언하고, 이를 스택의 최상위 노드를 가리키도록 설정한다.
• current가 NULL이 아닐 때까지 반복한다. 각 반복마다 현재 노드의 데이터를 출력하고, 다음 노드로 이동한다.
• printf("[BOTTOM]\n");: 스택의 맨 아래를 나타내는 [BOTTOM]을 출력한다. 이후에는 줄을 바꾼다.

// 스택의 모든 데이터를 출력하는 함수
void print(Stack* stack) {
    printf("[ TOP ] ");
    StackNode* current = stack->top;  // 현재의 top 노드부터 시작
    while (current != NULL) {
        printf("[%c] -> ", current->data);  // 현재 노드의 데이터 출력
        current = current->next;  // 다음 노드로 이동
    }
    printf("[BOTTOM]\n");
    // printf("\n");
}

main 함수

// 메인 함수
int main() {
    Stack stack;// 스택 노드 구조체 선언
    init(&stack);
    // stack이라는 스택 구조체(Stack)에 스택 노드(StackNode)연결

    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 (i+1 > N) {printf("Stack FULL\n");continue;}
            push(&stack, data);
        }
        else if (strcmp(input, "POP") == 0) {
            if (stack.top == NULL ) {printf("Stack Empty\n");continue;}
            data = pop(&stack);
        }
        else if (strcmp(input, "PEEK") == 0) {
            if (stack.top == NULL ) {printf("Stack Empty\n");continue;}
            element e = peek(&stack);
            printf("%c\n",e);
        }
        else if (strcmp(input, "DUP") == 0) {
            if (i+1 > N) {printf("Stack FULL\n");continue;}
            if (stack.top == NULL ) {printf("Stack Empty\n");continue;}
            duplicate(&stack);

        }
        else if (strcmp(input, "UpR") == 0) {
            scanf("%d", &n); getchar();
            if (n > size(&stack)) continue;
            // 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;
            if (n > size(&stack)) continue;
            downRotate(&stack, n);
        }
        else if (strcmp(input, "PRINT") == 0) {
            print(&stack);
        }

    }
    return 0;
}

전체 코드

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

typedef int element;

// 스택 노드 구조체 정의
typedef struct StackNode {
    int data;           // 데이터
    struct StackNode* next;  // 다음 노드를 가리키는 포인터
} StackNode;

// 스택 구조체 정의
typedef struct Stack{
    StackNode* top;  
    // 스택의 최상위 노드를 가리키는 포인터
} Stack;

// 스택 초기화 함수
void init(Stack* stack) {
    stack->top = NULL;
}

// 스택이 비어있는지 확인하는 함수
int isEmpty(Stack* stack) {
    return(stack->top == NULL);
}

// 스택에 데이터를 추가하는 함수
void push(Stack* stack, int data) {
    StackNode* new = (StackNode*)malloc(sizeof(StackNode)); 
    StackNode* p = stack->top;

    new->data = data;
    if(stack->top == NULL) stack->top = new;
    else{
        while(p->next != NULL){p = p->next;}
        p->next = new;
    }
}

// 스택에서 데이터를 제거하고 반환하는 함수
element pop(Stack* stack) {
    StackNode* p = stack->top;
    while(p->next->next != NULL){p = p->next;} 
    element e = p->next->data;
    
    p->next = NULL;

    return e;
}

// 스택에서 최상위 데이터를 반환하는 함수 (제거하지 않음)
element peek(Stack* stack) {
    StackNode* p = stack->top;
    while(p->next->next != NULL){p = p->next;} 
    element e = p->next->data;
    return e;
}

void duplicate(Stack *stack){

    element dup = pop(stack);
    push(stack,dup); push(stack,dup);
}

// 스택의 맨 위 n 개의 데이터를 회전시키는 함수
void upRotate(Stack* stack, int n) {
    if (isEmpty(stack)) return;  // 스택이 비어있으면 아무 작업도 하지 않음

    // 스택의 크기를 확인하고 n이 스택의 크기보다 클 경우 아무 작업도 하지 않음
    int size = 0;
    StackNode* current = stack->top;
    while (current != NULL) {size++;current = current->next;}
    if (n > size) return;

    // 맨 위 n 개의 데이터를 회전시킴
    StackNode* prev = NULL;
    current = stack->top;
    for (int i = 0; i < n; i++) {
        prev = current;
        current = current->next;
    }
    prev->next = NULL;  // 회전할 범위의 마지막 노드를 끊음

    // 회전한 범위의 마지막 노드를 새로운 최상위 노드로 만듦
    StackNode* newTop = current;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = stack->top;
    stack->top = newTop;
}

// 스택의 맨 위 n 개의 데이터를 반시계 방향으로 회전시키는 함수
void downRotate(Stack* stack, int n) {
    if (isEmpty(stack)) return;  // 스택이 비어있으면 아무 작업도 하지 않음

    // 스택의 크기를 확인하고 n이 스택의 크기보다 클 경우 아무 작업도 하지 않음
    int size = 0;
    StackNode* current = stack->top;
    while (current != NULL) {
        size++;
        current = current->next;
    }
    if (n > size) return;

    // 맨 위 n 개의 데이터를 회전시킴
    StackNode* prev = NULL;
    current = stack->top;
    for (int i = 0; i < n; i++) {
        prev = current;
        current = current->next;
    }
    prev->next = NULL;  // 회전할 범위의 마지막 노드를 끊음

    // 회전한 범위의 첫 번째 노드를 새로운 최하위 노드로 만듦
    StackNode* newBottom = stack->top;
    stack->top = current;

    // 회전한 범위의 마지막 노드를 찾아서 연결
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newBottom;
}

// 스택의 연결리스트에 저장된 스택의 개수를 반환하는 함수
int size(Stack* stack) {
    int count = 0;
    StackNode* current = stack->top;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}


// 스택 출력 함수
void print(Stack* stack) {

}

// 메인 함수
int main() {
    Stack stack;// 스택 노드 구조체 선언
    init(&stack);
    // stack이라는 스택 구조체(Stack)에 스택 노드(StackNode)연결

    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 (i+1 > N) {printf("Stack FULL\n");continue;}
            push(&stack, data);
        }
        else if (strcmp(input, "POP") == 0) {
            if (stack.top == NULL ) {printf("Stack Empty\n");continue;}
            data = pop(&stack);
        }
        else if (strcmp(input, "PEEK") == 0) {
            if (stack.top == NULL ) {printf("Stack Empty\n");continue;}
            element e = peek(&stack);
            printf("%c\n",e);
        }
        else if (strcmp(input, "DUP") == 0) {
            if (i+1 > N) {printf("Stack FULL\n");continue;}
            if (stack.top == NULL ) {printf("Stack Empty\n");continue;}
            duplicate(&stack);

        }
        else if (strcmp(input, "UpR") == 0) {
            scanf("%d", &n); getchar();
            if (n > size(&stack)) continue;
            // 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;
            if (n > size(&stack)) continue;
            downRotate(&stack, n);
        }
        else if (strcmp(input, "PRINT") == 0) {
            print(&stack);
        }

    }
    return 0;
}