스택구조

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

• 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;
}