C로 구현하는 자료구조 스택

250x250

Notice

Recent Comments

Link

github

Tags more

Archives

Today

Total

관리 메뉴

주뇽's 저장소

C로 구현하는 자료구조 스택 본문

알고리즘/스택, 큐

C로 구현하는 자료구조 스택

뎁쭌 2023. 7. 4. 18:21

728x90

스택구조

스택은 자료구조의 기본이다

LIFO구조
- 제일 마지막에 들어온 원소가 제일 먼저 나감
  ex) 바닥부터 책을 하나하나 쌓아 올리는 느낌
  #배열과 스택은 비슷하지만 다르다 스택을 이용하여 처리하려면 배열의 값을 다시 스택에 담는 행위가 필요하다.

구현

init()함수
- Stack의 포인터를 배열의 외부로 설정 즉 포인터 = -1;
isFull()함수
- Stack의 들어갈 수 있는 공간의 모든 자리가 꽉 차 있는지 확인
isEmpty()함수
- Stack의 들어갈 수 있는 공간이 있는지 확인
push()함수
- Stack의 공간이 남아있다면 원하는 원소를 맨 뒤에 하나 추가
pop()함수
- Stack의 원소가 있는지 확인 후 있다면 가장 맨 뒤에 원소를 return 해주고 원소 삭제
peek()함수
- Stack의 원소가 있는지 확인 후 있다면 가장 맨 뒤에 원소를 return
print()함수
- Stack의 가장 아래에 있는 원소부터 끝까지 하나씩 출력
check()함수
- 입력받은 문자열배열의 괄호연산의 조건이 맞는지 확인해주는 Stack을 응용한 함수

Char형 Stack구조 구현

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

typedef struct
{
    char data[SIZE];
    int top;
}StackType;

void init(StackType * S)
{   
    S->top = -1; //배열이 아닌 배열의 밖을 지정해주는 행위
}

int isEmpty(StackType * S)
{
    return S->top == -1; //비었는지 안 비었는지 리턴
}

int isFull(StackType * S)
{
    return S->top == SIZE-1; // 꽉 차있는지 
}

void push(StackType * S, char elem)
{
    if(isFull(S))
        printf("Overflow!!\n");
     // 여기서는 주소연산자를 사용 안함 이미 주소를 받았기 때문에
    else
        S->top++;
        S->data[S->top] = elem;

}

char pop(StackType * S)
{
    if(isEmpty(S))
       { printf("Empty!!\n");
        return -1;
       }
    char elem = S->data[S->top];
    S->top--;
    return elem;
} //값을 리턴하고 제거

char peek(StackType * S)
{
    if(isEmpty(S))
       { printf("Empty!!\n");
        return -1;
       }
    return S->data[S->top];
} //값만 리턴

void print(StackType * S)
{
    for(int i=0; i<=S->top; i++){
        printf("%c ", S->data[i]);
    }
    printf("\n");
}


int main(void){
    StackType S;
    init(&S);

    pop(&S); getchar(); // 오류를 체크하기 위해
    push(&S, 'c');
    push(&S, 'a');
    push(&S, 't');
    push(&S, 's');
    print(&S); getchar();

    printf("Call pop() : %c\n", pop(&S)); print(&S); getchar();
    printf("Call peek() : %c\n", peek(&S)); print(&S); getchar();
    return 0;
}

기존 구현한 Stack구조에서 괄호의 짝이 맞는지 체크해주는 함수추가

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

#define SIZE 100

typedef struct
{
    char data[SIZE];
    int top;
}StackType;

void init(StackType * S)
{   
    S->top = -1; //배열이 아닌 배열의 밖을 지정해주는 행위
}

int isEmpty(StackType * S)
{
    return S->top == -1; //비었는지 안 비었는지 리턴
}

int isFull(StackType * S)
{
    return S->top == SIZE-1; // 꽉 차있는지 
}

void push(StackType * S, char elem)
{
    if(isFull(S))
        printf("Overflow!!\n");
     // 여기서는 주소연산자를 사용 안함 이미 주소를 받았기 때문에
    else
        S->top++;
        S->data[S->top] = elem;

}

char pop(StackType * S)
{
    if(isEmpty(S))
    {
        printf("Empty!!\n");
        return -1;
    }
    char elem = S->data[S->top];
    S->top--;
    return elem;
} //값을 리턴하고 제거

char peek(StackType * S)
{
    if(isEmpty(S))
    {
        printf("Empty!!\n");
        return -1;
    }
    return S->data[S->top];
} //값만 리턴

void print(StackType * S)
{
    for(int i=0; i<=S->top; i++){
        printf("%c ", S->data[i]);
    }
    printf("\n");
}

int check(char str[])
{
    StackType S;
    init (&S);

    char c,t;
    int len = strlen(str);

    for(int i=0; i<len; i++)
    {
        c = str[i]; //한글자씩 읽음
        if(c== ('(' || '{' || '[' ))
            push(&S,c); //열린 괄호는 스택에 저장
        else if(c == (')' || '}' || ']'))
        {
            if(isEmpty(&S))
                return 0;
            else
            {
                t = pop(&S);
                if( (t=='(' && c != ')') || ( t=='{' && c!= '}') || (t=='[' && c!= ']'))
                    return 0;
            } // else_if -> else
        } 
    } //for_i
    return isEmpty(&S);
}


int main(void)
{
    char str[SIZE];
    scanf("%s", str); //문자열->주소연산자 사용 안함

    if(check(str))
        printf("Success!!\n");
    else
        printf("Fail\n");
    return 0;
}

중위연산자 , 후위연산자

위에서 구현한 스택구조를 이용하요 중위연산자와 후위연산자 구현

스택을 사용하여 문자열 압축하기

위에서 구현한 스택구조를 이용하요 문자열을 압축하여 문자의 갯수와 문자 출력


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100

typedef struct
{
    char data[SIZE];
    int top;
}StackType;

void init(StackType * S)
{   
    S->top = -1; //배열이 아닌 배열의 밖을 지정해주는 행위
}

int isEmpty(StackType * S)
{
    return S->top == -1; //비었는지 안 비었는지 리턴
}

int isFull(StackType * S)
{
    return S->top == SIZE-1; // 꽉 차있는지 
}

void push(StackType * S, char elem)
{
    if(isFull(S))
        printf("Overflow!!\n");
     // 여기서는 주소연산자를 사용 안함 이미 주소를 받았기 때문에
    else
        S->top++;
        S->data[S->top] = elem;

}

char pop(StackType * S)
{
    if(isEmpty(S))
       { printf("Empty!!\n");
        return -1;
       }
    char elem = S->data[S->top];
    S->top--;
    //printf("elem is %c\n" , elem);
    return elem;
} //값을 리턴하고 제거

char peek(StackType * S)
{
    if(isEmpty(S))
       { printf("Empty!!\n");
        return -1;
       }
    return S->data[S->top];
} //값만 리턴

void print(StackType * S)
{
    for(int i=0; i<=S->top; i++){
        printf("%c ", S->data[i]);
    }
    printf("\n");
}


int main(){
    char str[100];
    char temp = 0;
    int cnt = 1;
    scanf("%s", str);
    StackType S1;
    StackType S2;
    init(&S1);
    init(&S2);

    int len = strlen(str);
    for(int i=0; i<len; i++){
        if(str[i] >64 && str[i]<97)
            str[i] = str[i] + 32;
        push(&S1, str[i]);
    }
    temp = pop(&S1);
    for(int i=1; i<len; i++){
        if(temp == peek(&S1)){
            cnt ++;
            pop(&S1);
        }
        else{
            push(&S2, temp);
            push(&S2, cnt+'0');
            temp = pop(&S1);
            cnt = 1;
        }
    }
    push(&S2, temp);
    push(&S2, cnt+'0');

    while(isEmpty(&S2) !=1 ){
        printf("%c",pop(&S2));
    }
    printf("\n");
    return 0;
}

스택을 사용하여 중복된 값 제거하기

위에서 구현한 스택구조를 이용하요 배열안의 중복된 숫자 제거

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100

typedef struct
{
    char data[SIZE];
    int top;
}StackType;

void init(StackType * S)
{   
    S->top = -1; //배열이 아닌 배열의 밖을 지정해주는 행위
}

int isEmpty(StackType * S)
{
    return S->top == -1; //비었는지 안 비었는지 리턴
}

int isFull(StackType * S)
{
    return S->top == SIZE-1; // 꽉 차있는지 
}

void push(StackType * S, char elem)
{
    if(isFull(S))
        printf("Overflow!!\n");
     // 여기서는 주소연산자를 사용 안함 이미 주소를 받았기 때문에
    else
        S->top++;
        S->data[S->top] = elem;

}

char pop(StackType * S)
{
    if(isEmpty(S))
       { printf("Empty!!\n");
        return -1;
       }
    char elem = S->data[S->top];
    S->top--;
    return elem;
} //값을 리턴하고 제거

char peek(StackType * S)
{
    if(isEmpty(S))
       { printf("Empty!!\n");
        return -1;
       }
    return S->data[S->top];
} //값만 리턴

void print(StackType * S)
{
    for(int i=0; i<=S->top; i++){
        printf("%c ", S->data[i]);
    }
    printf("\n");
}



int main(){
    char str[100];
    scanf("%s", str);
    StackType S1;
    StackType S2;
    init(&S1);
    init(&S2);

    int len = strlen(str);
    for(int i=0; i<len; i++){
        push(&S1, str[i]);
    }
    char temp = pop(&S1);
    push(&S2, temp);
    for(int i=0; i<len-1; i++){
        if(temp == peek(&S1)){
            pop(&S1);
        }
        else{
            temp = pop(&S1);
            push(&S2, temp);
        }
    }
    while(isEmpty(&S2) !=1 ){
        printf("%c",pop(&S2));
    }
    printf("\n");
    return 0;
}

저작자표시

'알고리즘 > 스택, 큐' 카테고리의 다른 글

프로그래머스 스쿨(고득점 Kit) - 같은 숫자는 싫어 (0)	2023.07.16
C로 구현하는 자료구조 큐 (0)	2023.07.04
프로그래머스 스쿨 고득점 스택/큐 같은 숫자는 싫어 (0)	2023.07.04

'알고리즘/스택, 큐' Related Articles

주뇽's 저장소

C로 구현하는 자료구조 스택 본문

C로 구현하는 자료구조 스택

스택구조

스택은 자료구조의 기본이다

#배열과 스택은 비슷하지만 다르다 스택을 이용하여 처리하려면 배열의 값을 다시 스택에 담는 행위가 필요하다.

구현

Char형 Stack구조 구현

기존 구현한 Stack구조에서 괄호의 짝이 맞는지 체크해주는 함수추가

중위연산자 , 후위연산자

위에서 구현한 스택구조를 이용하요 중위연산자와 후위연산자 구현

스택을 사용하여 문자열 압축하기

위에서 구현한 스택구조를 이용하요 문자열을 압축하여 문자의 갯수와 문자 출력

스택을 사용하여 중복된 값 제거하기

위에서 구현한 스택구조를 이용하요 배열안의 중복된 숫자 제거

'알고리즘 > 스택, 큐' 카테고리의 다른 글

티스토리툴바