자료구조 4(스택)

---

- 스택

컴퓨터에서 많이 사용되는 자료구조로 후입 선출(LIFO : Last-in-first-out) 형태이다.

---

- 스택의 추상자료형

create : 공백 스택을 생성

is_full : 스택이 포화상태인지 확인

is_empty : 스택이 공백상태인지 확인

push : 스택의 삽입 연산

pop : 스택의 삭제 연산

peek : 스택의 맨 위의 원소를 삭제하지 않고 반환

---

- 스택의 구현

#include <stdio.h>
#define MAX 5


typedef struct stack {
    int stack[MAX];
    int top;
}Stack;

void init_stack(Stack *A) {
    A->top = -1;
}

void is_empty(Stack *A) {
    if(A->top == -1)
        printf("스택이 공백상태입니다. \n");
}

void is_full(Stack *A) {
    if(A->top == MAX -1)
        printf("스택이 포화상태입니다. \n");
}

void push(Stack *A, int data) {
    A->stack[++(A->top)] = data;
}

int pop(Stack *A) {
    return A->stack[(A->top)--];
}

int peek(Stack *A) {
    return A->stack[A->top];
}

int main(void) {
    
    int i, j;
    Stack A;    //스택 A생성
    init_stack(&A);
    is_empty(&A);
    push(&A,1);
    push(&A,2);
    push(&A,3);
    push(&A,4);
    push(&A,5);
    
    for(i = 0; i <= A.top; i++) {
        printf("[%d] ", A.stack[i]);
    }
    printf("\n");
    
    is_full(&A);
    
    j = pop(&A);
    printf("pop(A) = [%d] \n", j);
    j = peek(&A);
    printf("peek(A) = [%d] \n", j);
    
    for(i = 0; i <= A.top; i++) {
        printf("[%d] ", A.stack[i]);
    }
    printf("\n");
    
}

실행화면

---

- 스택의 활용

문자열을 입력받아 희문인지 아닌지 판별해주는 프로그램

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

#define MAX_SIZE 100

//정말 간단히 구현하였기 때문에 영어만입력받을 수 있고 대문자와 소문자를 다른 문자로 파악하여 Moom을 넣었을 경우 희문이 아니라고 나옴

typedef char element;    //스택에 들어가는 요소의 자료형이므로 이것만 바꾸면 다른것은 안바꿔도됨 (정수형에서 문자형으로 갈때도 그냥 char로만 바꾸면됨)

typedef struct stack {    //스택의 구조체
    element data[MAX_SIZE];
    int top;
}Stack;

int size(Stack *p) {
    return p->top+1;
}

int is_empty(Stack *p) {    //공백상태검출함수
    return (p->top == -1);
}

int is_full(Stack *p) { //포화상태검출함수
    return (p->top == (MAX_SIZE - 1));
}

void stack_init(Stack *p) { //스택초기화함수
    p->top = -1;
}

void push(Stack *p, element item) { //push연산
    if(is_full(p)) {
        fprintf(stderr, "스택 포화 에러 \n");
        exit(1);
    }
    else
        p->data[++(p->top)] = item;
}

element pop(Stack *p) { //pop연산
    if(is_empty(p)) {
        fprintf(stderr, "스택 공백 에러 \n");
        exit(1);
    }
    else
        return p->data[(p->top)--];    //해당위치의 값을 반환하고 top값 --하므로 안에는 값이 여전히 남아있긴함
}

element peek(Stack *p) {    //peek연산
    if(is_empty(p)) {
        fprintf(stderr, "스택 공백 에러 \n");
        exit(1);
    }
    else
        return p->data[(p->top)];    //해당위치의 값만 반환함
}

int main(void) {
    Stack s1, s2;
    stack_init(&s1);
    stack_init(&s2);
    int i = 0, count = 0;
    char st[MAX_SIZE];
    printf("문자열을 입력하세요 : ");
    scanf("%s", st);
    
    while(st[i] != '\0') {
        push(&s1, st[i]);
        i++;
    }

    while(s1.top != -1) {
        push(&s2, pop(&s1));
    }
    i = 0;
    while(st[i] != '\0') {
        push(&s1, st[i]);
        i++;
    }
    
    while(!is_empty(&s1)) {
        if(pop(&s1) == pop(&s2))
            count++;
    }
    
    if(count == strlen(st))
        printf("희문입니다. \n");
        
    else
        printf("희문이아닙니다. \n");
    return 0;
}

실행화면

 

---