배열 stack / 단순연결리스트 stack

/***********************************************/
// ex. 1 배열스택
/***********************************************/

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

#define STACK_SIZE      5
int stack[STACK_SIZE];
int top;                // stack공간에 값이 저장되어 있는 최상단의 위치값

int getnum(void);
void init_stack(void);
void push(int data);
int pop(void);
void print_stack(void);
void all_data_delete(void);

void main(void)
{
        int menu, num;

        // stack 초기화
        init_stack();   
        
        while(1)
        {
                fflush(stdin);
                printf("\n1. PUSH\n");  
                printf("2. POP\n");
                printf("3. PRINT\n");
                printf("4. ALL_DATA_DELETE\n");
                printf("5. EXIT\n");
                printf(" >> ");
                menu = getnum();
                
                fflush(stdin);

                // stack에 data를 삽입 : push
                if(menu == 1)
                {
                        printf("Enter the push_number >> ");
                        num = getnum();
                        push(num);
                }

                // stack의 data를 삭제 : pop
                else if(menu == 2)
                {
                        num = pop();
                        if(num != -100)
                                printf("[%d]가 삭제되었습니다.\n", num);
                }

                // 스택의 data 출력
                else if(menu == 3) print_stack();

                // 연결리스트의 모든 내용 삭제
                else if(menu == 4) all_data_delete();

                // 프로그램 종료
                else if(menu == 5)
                {
                        printf("프로그램을 종료합니다.\n");
                        exit(1);
                }

                else
                        printf("# 잘못된 입력입니다.\n");
        }
}

int getnum(void)
{
        char ch;
        int num = 0;
        while((ch = getchar()) != '\n')
                num = num * 10 + (ch - '0');
        return num;
}

void init_stack(void)
{
        top = -1;       // stack의 값이 저장되어 있는 최상단의 위치
}

// top의 값을 하나 증가시키고 data를 insert하는 push function
void push(int data)
{
        // overflow
        if(top >= STACK_SIZE - 1)
        {
                printf(" # STACK OVERFLOW\n");
                return;
        }
        //top += 1;
        //stack[top] = data;
        stack[++top] = data;
}

// 삭제될 data의 값을 main함수에 돌려주고,
// top의 값을 하나 감소시키는 pop function
int pop(void)
{
        //int num;

        // underflow
        if(top < 0)
        {
                printf(" # STACK UNDERFLOW\n");
                return -100;
        }

        //num = stack[top];
        //top--;
        //return num;
        return stack[top--];
}

// stack에 저장된 값을 출력하는 print_stack function
void print_stack(void)
{
        int i;
        if(top < 0)
        {
                printf("비어있는 스택입니다.\n");
                return;
        }

        printf("BASE ----------------- TOP\n");
        for(i = 0; i <= top; i++)
        {
                printf("%5d", stack[i]);
        }
        putchar('\n');
}

// stack의 모든 값을 삭제하는 all_data_delete function
void all_data_delete(void)
{
        // 삭제되어지는 공간의 값을 깨끗이 초기화해도 되겠지만,
        // top값만을 초기화 시키는 것으로도 충분히 all_data_delete가
        // 수행되어 질 수 있다.
        // stack의 push & pop은 top값을 기준으로 판단하기 때문에...

        init_stack();
}

 

/***********************************************/
// ex. 2 단순연결리스트 스택
/***********************************************/

#include <stdio.h>
#include <stdlib.h>
 
// stack은 단순연결리스트만으로 충분하다?
// stack의 data push & pop은 stack의 상단지점에서만
// 일어나게 된다. stack의 상단지점이라고 하는 것은
// head->next 지점이기 때문에, 이 문제는
// "임의의 노드 뒤에 data 삽입 & 삭제"로 해석할 수 있고,
// 이러한 과정은 자신의 뒷 노드값만을 알고 있는
// 단순연결리스트만으로도 충분히 해결가능하다.
typedef struct list_stack
{
        int data;
        struct list_stack *next;
}stack;

stack *head, *tail;

int getnum(void);
void init_stack(void);
void push(int data);
int pop(void);
void print_stack(void);
void all_data_delete(void);

void main(void)
{
        int menu, num;

        // stack 초기화
        init_stack();   
        
        while(1)
        {
                fflush(stdin);
                printf("\n1. PUSH\n");  
                printf("2. POP\n");
                printf("3. PRINT\n");
                printf("4. ALL_DATA_DELETE\n");
                printf("5. EXIT\n");
                printf(" >> ");
                menu = getnum();
                
                fflush(stdin);

                // stack에 data를 삽입 : push
                if(menu == 1)
                {
                        printf("Enter the push_number >> ");
                        num = getnum();
                        push(num);
                }

                // stack의 data를 삭제 : pop
                else if(menu == 2)
                {
                        num = pop();
                        if(num != -100)
                                printf("[%d]가 삭제되었습니다.\n", num);
                }

                // 스택의 data 출력
                else if(menu == 3) print_stack();

                // 연결리스트의 모든 내용 삭제
                else if(menu == 4) all_data_delete();

                // 프로그램 종료
                else if(menu == 5)
                {
                        all_data_delete();
                        free(head);
                        free(tail);
                        printf("프로그램을 종료합니다.\n");
                        exit(1);
                }

                else
                        printf("# 잘못된 입력입니다.\n");
        }
}

int getnum(void)
{
        char ch;
        int num = 0;
        while((ch = getchar()) != '\n')
                num = num * 10 + (ch - '0');
        return num;
}

void init_stack(void)
{
        head = (stack *)malloc(sizeof(stack));
        tail = (stack *)malloc(sizeof(stack));
        head->next = tail;
        tail->next = tail;
}

// 연결리스트의 상단(head->next)지점에 data를 insert : push
void push(int data)
{
        stack *new_stack;
        new_stack = (stack *)malloc(sizeof(stack));
        
        // 동적할당을 받지 못하는 것이 연결리스트의 overflow
        if(new_stack == NULL)
        {
                printf("# STACK OVERFLOW\n");
                return;
        }
        new_stack->data = data;
        new_stack->next = head->next;
        head->next = new_stack;
}

// 연결리스트의 상단(head->next)지점의 data를 delete : pop
int pop(void)
{
        int ret;
        stack *del;

        // 저장된 data가 없는 경우는 head->next == tail인 조건
        if(head->next == tail)
        {
                printf("# STACK UNDERFLOW\n");
                return -100;
        }
        del = head->next;
        ret = del->data;
        head->next = head->next->next;
        free(del);
        return ret;
}

// 연결리스트내에 들어있는 data 출력하는 print_stack function
void print_stack(void)
{
        stack *print = head->next;
        if(head->next == tail)
        {
                printf(" # 비어있는 스택입니다.\n");
                return;
        }

        printf("TOP --------------------- BASE\n");
        while(print != tail)
        {
                printf("%5d", print->data);
                print = print->next;
        }
        putchar('\n');
}

// stack의 모든 값을 삭제하는 all_data_delete function
void all_data_delete(void)
{
        stack *del, *del_next = head->next;
        while(del_next != tail)
        {
                del = del_next;
                del_next = del_next->next;
                free(del);
        }
        head->next = tail;
        printf(" # 모든 data가 삭제되었습니다.\n");
}