[자료구조] Stack / Linked-List Stack

메르센고수·2024년 1월 30일
Cstack자료구조

DataStructure

목록 보기
1/2
post-thumbnail

개요

자료구조론에서 빼놓을 수 없는 개념이 스택과 큐이다. 두 자료구조의 차이는 일방통행이냐 양방통행이냐의 차이이다.
그러므로, 일방통행인 스택의 경우는 처음에 들어간 element가 계속 쌓이는 LIFO(Last in First Out) 구조이기 때문에 Postfix 연산에 적합하다고 생각해서 작년에 배운 자료구조론 복습 겸 LinkedList로 스택 구조를 만드는 방법도 연습하기 위해 시작하게 되었다.

참고

1. Stack

Stack - Wikipedia

  • 주요한 연산으로는 3가지가 있다.
    1. PUSH(S,x)
    : Stack S에 element x를 집어넣는 과정
    2. Pop(S)
    : Stack S의 top위치에 있는 값을 stack 밖으로 빼는 과정
    3. Top(S)
    : Stack S에서 제일 위에 있는 element로 stack에 element가 없는 경우 default 값이 -1이다.

2. Postfix


Postfix를 살펴보기 전에 3가지의 연산 방법을 비교해보면,

  1. infix의 경우는 연산자가 중앙에 있는 흔히 아는 사칙연산이랑 똑같은 형태이다.
  2. prefix의 경우는 앞에 붙은 접두어 pre로 유추할 수 있듯이 연산자가 앞쪽에 온다.
    예를 들어, *+346의 경우 +34가 먼저 만나기 때문에 7이 계산되고 그 다음에 *76에 의해 42가 결과 값으로 도출되게 된다.
  3. postfix도 마찬가지로 앞의 접두어를 통해 연산자가 뒤쪽에 온다는 것을 알 수 있다. 그렇기 때문에 postfix를 stack에 적용하게 되면 숫자가 먼저 들어가고 연산자가 그 다음에 들어가기 때문에 연산자를 Pop한 뒤 Pop 되는 연속된 2개의 수를 연산해주면 되기 때문에 적합하다고 생각했다.

    이런 식으로 연산이 진행되는데, 또 다른 예시를 Stack에 적용해보면 다음과 같다.

LinkedList Stack

LinkedList stack의 경우 약간 주의 깊게 봐야할 점이 있다.

위의 사진은 push의 연산인데 Element=x인 TmpCell을 만들어서 노드와 포인터들을 조정해주어야한다.

void Push(Stack S, ElementType x){
    PtrToNode tmpCell=malloc(sizeof(struct Node));
    if(tmpCell==NULL)
        return;
    else{
        tmpCell->Element=x;
        tmpCell->Next=S->Next;
        S->Next=tmpCell;
    }
}

코드로 보면 else 부분의 연산이 핵심이라는 것을 알 수 있다.
먼저 tmpcell의 element를 x로 설정한 뒤, 기존의 노드가 가리키고 있던 포인터 위치를 TmpCell의 포인터가 가리키도록 설정해주고 자리를 뺏긴 이전 노드의 포인터를 TmpCell을 가리키게 해주면 LinkedList를 유지하면서 TmpCell을 끼워넣을 수 있다.

그 다음으로 Pop 연산인데, Pop 연산도 포인터를 조정해주어야 하기 때문에 조금 까다롭다.

int Pop(Stack S){
    PtrToNode FirstCell;
    if(IsEmpty(S)){
        return 0;
    }else{
        FirstCell=S->Next;
        S->Next=S->Next->Next;
        int poppedElement = FirstCell->Element;
        free(FirstCell);
        return poppedElement;
    }
}

else 부분을 보면 이전 노드가 갖고 있는 포인터가 FirstCell을 가리키게 하고
S->Next=S->Next->Next 이 부분을 통해 S의 포인터가 FirstCell이 가리키고 있던 노드를 가리키게 한 다음 return 값을 FirstCell이 갖고 있던 element로 설정해주면 된다.

기존의 Stack의 Push/Pop 연산보다는 약간 복잡하게 느껴질 수 있지만, LinkedList의 구성원리를 이해하고 있다면 충분히 구현할 수 있다.

소스 코드

1. Stack.C

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 10

typedef struct StackRecord{
    int* key; // element
    int top; // 제일 마지막 element가 있는 위치
    int Capacity; // Stack의 용량
}*Stack;

Stack CreateStack(int maxElements);
void Push(Stack S, int x);
int Pop(Stack S);
int Top(Stack S);
void DeleteStack(Stack S);
int IsEmpty(Stack S);
int IsFull(Stack S);
void PostFix(Stack S, char c);

int main(int argc, char* argv[]){
    FILE *fi = fopen(argv[1], "r"); // file을 읽기 모드로 불러오기

    Stack stack = CreateStack(MAX_STACK_SIZE); // 스택 생성

    char c;
    printf("Top numbers: ");
    while (fscanf(fi, "%c", &c) != EOF){ // 파일의 끝까지 scanf 수행
        if(c == '#')
            break;
        PostFix(stack, c);
        printf("%d ",Top(stack));
    }
    printf("\n");
    printf("Evaluation result: %d\n", Pop(stack)); // 마지막 결과 출력

    fclose(fi);
    DeleteStack(stack);
    return 0;
}

Stack CreateStack(int maxElements){
    Stack S = (Stack)malloc(sizeof(struct StackRecord));
    S->key=malloc(sizeof(int)*maxElements);
    S->top=-1;
    S->Capacity=maxElements;
    if (S == NULL || S->key == NULL){
        exit(1);
    }
    return S;
}
void Push(Stack S, int x){
    if(IsFull(S))
        return;
    S->key[++S->top]=x; // top이 있던 위치의 한 칸 위에 x 삽입
}
int Pop(Stack S){
    if(IsEmpty(S))
        return -1;
    return S->key[S->top--]; // top 위치의 element를 반환하고 top의 위치를 한 칸 내림
}
int Top(Stack S){
    if(IsEmpty(S))
        return -1;
    return S->key[S->top]; // top 위치에 있는 element 반환
}
void DeleteStack(Stack S){
    free(S->key);
    free(S);
}
int IsEmpty(Stack S){
    return S->top==-1; // stack이 빈상태 (default=-1)
}
int IsFull(Stack S){
    return S->top==S->Capacity-1; // stack이 가득 찬 상태 (최대 용량-1)
}

// Postfix이기 때문에 연산자를 확인한 뒤 x,y를 pop해서 연산 결과를 다시 stack에 push
void PostFix(Stack S, char c){ 
    int x, y;
    switch(c){
        case '+':
            y=Pop(S);
            x=Pop(S);
            Push(S, x+y);
            break;
        case '-':
            y=Pop(S);
            x=Pop(S);
            Push(S,x-y);
            break;
        case '*':
            y=Pop(S);
            x=Pop(S);
            Push(S,x*y);
            break;
        case '/':
            y=Pop(S);
            x=Pop(S);
            if(y!=0){
                Push(S, x/y);
            }else{
                break;
            }
            break;
        case '%':
            y=Pop(S);
            x=Pop(S);
            Push(S,x%y);
            break;
        default:
            Push(S,c-'0');
            break;
    }
}

2. LinkedList_stack.c

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 10

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Stack;
typedef int ElementType;

struct Node{
    ElementType Element; // Node에 있는 Element
    PtrToNode Next; // Node가 갖고 있는 Pointer
};

Stack CreateStack(int maxElements);
void MakeEmpty(Stack S);
void Push(Stack S, ElementType x);
int Pop(Stack S);
ElementType Top(Stack S);
int IsEmpty(Stack S);
void PostFix(Stack S, char c);

// main함수는 동일
int main(int argc, char *argv[]){
    FILE *fi = fopen(argv[1], "r");

    Stack stack = CreateStack(MAX_STACK_SIZE);
    char c;
    printf("Top numbers: ");
    while(fscanf(fi, "%c", &c) != EOF){
        if (c == '#')
            break;
        PostFix(stack, c);
        printf("%d ", Top(stack));
    }
    printf("\n");
    printf("Evaluation result: %d\n", Pop(stack));

    fclose(fi);
    free(stack);
    return 0;
}

Stack CreateStack(int maxElements){
    Stack S=(Stack)malloc(sizeof(struct Node));
    if(S==NULL)
        exit(1);
    S->Next=NULL;
    return S;
}

void MakeEmpty(Stack S){
    if(S==NULL){
        return;
    }else{
        while(!IsEmpty(S))
            Pop(S);
    }
}

void Push(Stack S, ElementType x){
    PtrToNode tmpCell=malloc(sizeof(struct Node));
    if(tmpCell==NULL)
        return;
    else{
        tmpCell->Element=x;
        tmpCell->Next=S->Next;
        S->Next=tmpCell;
    }
}

ElementType Top(Stack S){
    if(!IsEmpty(S)){
        return S->Next->Element;
    }else{
        printf("Empty Stack\n");
        return 0;
    }
}

int Pop(Stack S){
    PtrToNode FirstCell;

    if(IsEmpty(S)){
        return 0;
    }else{
        FirstCell=S->Next;
        S->Next=S->Next->Next;
        int poppedElement = FirstCell->Element;
        free(FirstCell);
        return poppedElement;
    }
}

int IsEmpty(Stack S){
    return S->Next==NULL;
}

void PostFix(Stack S, char c){
    int x, y;
    switch (c){
        case '+':
            y = Pop(S);
            x = Pop(S);
            Push(S, x + y);
            break;
        case '-':
            y = Pop(S);
            x = Pop(S);
            Push(S, x - y);
            break;
        case '*':
            y = Pop(S);
            x = Pop(S);
            Push(S, x * y);
            break;
        case '/':
            y = Pop(S);
            x = Pop(S);
            if (y != 0){
                Push(S, x / y);
            }else{
                break;
            }
            break;
        case '%':
            y = Pop(S);
            x = Pop(S);
            Push(S, x % y);
            break;
        default:
            Push(S, c - '0');
            break;
    }
}

3. input.txt

4736%+*42/-9+23*-#

결과


2개의 파일 모두 input.txt를 집어넣으면 위의 이미지와 같은 결과가 출력된다.
따라서 LinkedList도 Stack의 기능을 한다는 것을 알 수 있다.

결론

Stack은 자료구조 뿐만 아니라 코테나 전공지식 면접 등에서 자주 등장하는 개념이기 때문에 상당히 중요하다고 할 수 있다. 특히나 LinkedList로 Stack의 기능을 구현할 수 있다는 점을 알아두면 상당히 도움이 될 것 같다.

profile
메르센고수
블로그 이전했습니다 (https://phj6724.tistory.com/)
다음 포스트

[자료구조] DisjointSet / 백준 1976 - 여행가자

0개의 댓글