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

728x90

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

구조체 선언

스택(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;
}

728x90

저작자표시

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

[6] 스택 ⑥ 스택의 응용 : 중위수식 변환 (0)	2024.05.17
[6] 스택 ⑤ 스택의 응용 : 괄호 (0)	2024.05.15
[6] 스택 ④ 스택의 응용 : 스택 ADT (0)	2024.05.13
[6] 스택 ② 배열을 이용한 스택 알고리즘(ADT) (0)	2024.05.12
[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

우당탕탕 코딩 제작소

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

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

구조체 선언

init: 스택 초기화 함수

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

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

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

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

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

duplicate : 스택 복제 함수

upRotate : 상향 회전 함수

downRotate: 하향 회전 함수

print : 스택 데이터 출력 함수

main 함수

전체 코드

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

티스토리툴바

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

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

구조체 선언

init: 스택 초기화 함수

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

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

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

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

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

duplicate : 스택 복제 함수

upRotate : 상향 회전 함수

downRotate: 하향 회전 함수

print : 스택 데이터 출력 함수

main 함수

전체 코드

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

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

티스토리툴바

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