[4장] 스택

스택에 대한 문제풀이 내용이다.
스택(Stack)이란?

 - 한마디로 표현하면 선입후출, FILO(First In, Last Out) 형태의 자료구조이다.

 - 주로 컴파일러에서 괄호검사를 시행할 때, '{' 중괄호는 '}' 중괄호, '('소괄호는 ')' 소괄호로 닫혀야 한다. (Syntex Check)

 - 여러 줄의 구문들이 섞여 있을 때 쌍쌍의 짝이 맞아 떨어져서 최종적으로 스택이 공백이 되어있어야 정상일 것이다.

예제를 통해 괄호검사 프로그램을 정적 배열로도 구현해보고, 포인터 변수를 활용한 동적 배열로도 구현해 볼 것이다.

스택을 구현하기에 앞서 사용할 배열 리스트를 학습해보자.

 

정적 배열 리스트

#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST_SIZE 100
typedef int element;
typedef struct
{
 int list[MAX_LIST_SIZE];
 int length;
}ArrayListType;
void error(char *message);
void init(ArrayListType *L);
int is_empty(ArrayListType *L);
int is_full(ArrayListType *L);
void add_list(ArrayListType *L, int position, element item);
element Delete(ArrayListType *L, int position);
void display(ArrayListType *L);
void add_last(ArrayListType *list, int item);
void add_last(ArrayListType *list, int item);
void add_first(ArrayListType *list, int item);
void clear(ArrayListType *list);
void replace(ArrayListType *list, int pos, int item);
int is_in_list(ArrayListType *list, int item);
int get_entry(ArrayListType *list, int pos);
int get_length(ArrayListType *list);
void add(ArrayListType *list, int pos, int item);
int main(void)
{
 ArrayListType *plist;
 int i;
 int temp;
 int temp2;
 
 printf("plist 생성\n");
 plist = (ArrayListType *)malloc(sizeof(ArrayListType));
 
 
 init(plist);
 for(i=10;i<=30;i+=10){
  add_last(plist , i);
 }
 
 display(plist);
 
 printf("\n첫번째위치에 100 삽입\n");
 add_first(plist, 100);
 display(plist);
 
 printf("\n마지막위치에 200 삽입\n");
 add_last(plist, 200);
 display(plist);
 
 printf("\n두번째 요소[1] 50으로 치환\n");
 replace(plist, 1, 50);
 display(plist);
 
 printf("\n세번째 요소[2]에 300 삽입\n");
 add(plist, 2, 300);
 display(plist);
 
 printf("\n요소가 몇번 인덱스에 있는지? (item): ");
 scanf("%d", &temp);
 temp2 = is_in_list(plist, temp);
 if(temp2 != 0)
  printf("%d번 인덱스에 있음\n", temp2);
 else
  printf("%d는 리스트에 없음\n");
 
 printf("\n몇번째 요소? : ");
 scanf("%d", &temp);
 printf("list[%d] -> %d\n", temp, get_entry(plist, temp));
 
 printf("\n현재 리스트의 길이 : %d\n", get_length(plist));
 
 free(plist);
 
 
}
void add_last(ArrayListType *list, int item){
 if(!is_full(list)){
  list->list[list->length] = item;
  list->length++;
 }
 else
  printf("리스트 오버플로우!\n");
}
void add_first(ArrayListType *list, int item){
 int i;
 if(!is_full(list)){
  for(i=list->length;i>0;i--){
   list->list[i] = list->list[i-1];
   
  }
  list->list[0] = item;
  list->length++;
 }
 else
  printf("리스트 오버플로우!\n");
}
void clear(ArrayListType *list){
 int i;
 for(i=0;ilength;i++){
  list->list[i] = 0;
 }
 list->length = 0;
 
}
void replace(ArrayListType *list, int pos, int item){
 
 if(pos >= list->length){
  printf("pos 위치지정 오류 \n");
  exit(0);
  
 }
 
 list->list[pos] = item;
 
}
int is_in_list(ArrayListType *list, int item){
 
 int i;
 for(i=0;ilength;i++){
  if(list->list[i] == item)
   return i;
 }
 
 return 0;
 
}
int get_entry(ArrayListType *list, int pos){
 if(pos >= list->length){
  printf("pos 위치지정 오류 \n");
  return -1;
  
 }
 
 return list->list[pos];
 
}
int get_length(ArrayListType *list){
 
 return list->length;
 
}
void error(char *message){
 fprintf(stderr,"%s\n", message);
 exit(1);
}
void add(ArrayListType *list, int pos, int item){
 int i;
 if(!is_full(list)){
  for(i=list->length;i>pos;i--){
   list->list[i] = list->list[i-1];
   
  }
  list->list[pos] = item;
  list->length++;
 }
 else
  printf("리스트 오버플로우!\n");
 
}
void init(ArrayListType *L)
{
 L->length = 0;
}
int is_empty(ArrayListType *L)
{
 return L -> length == 0;
}
int is_full(ArrayListType *L)
{
 return L -> length == MAX_LIST_SIZE;
}
void add_list(ArrayListType *L, int position, element item)
{
 if(!is_full(L))
 {
  int i;
  for( i = 0 ; i < L->length ; i++ )
   if( L->list[i] >= item )
    break;
   position = i;
   for(i=(L->length-1); i>=position; i--)
   {
    L->list[i+1] = L->list[i];
   }
   L->list[position] = item;
   L->length++;
 }
}
element Delete(ArrayListType *L, int position)
{
 int i;
 element item;
 
 if((position <0) ||( position >=L->length))
 {
  error("위치오류");
 }
 item = L -> list[position];
 for(i = position; i<(L->length-1); i++)
 {
  L->list[i] = L->list[i+1];
 }
 L-> length--;
 return item;
}
void display(ArrayListType *L)
{
 int i;
 for(i = 0; i< L->length; i++)
  printf("%d ",L->list[i]);
 
 printf("\n");
}

 

Case 1: 괄호검사 프로그램(정적 배열 스택)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

#define MAX_STACK_SIZE 100

#define TRUE 1

#define FALSE 0

 

typedef char element;

 

typedef struct{

        element stack[MAX_STACK_SIZE];

        int top;

}StackType;

 

void init(StackType *s){

        s->top = -1;

}

 

int is_empty(StackType *s){

         return (s->top == -1);

}

 

int is_full(StackType *s){

        return (s->top == (MAX_STACK_SIZE-1));

}

 

void push(StackType *s, element item){

        if(is_full(s)){

                fprintf(stderr, "스택 포화 에러\n");

                return;

        }

        

        else s->stack[++(s->top)] = item;

}

 

void display(StackType *s){

        int i;

        for(i=0;i<=s->top;i++){

                printf("%c ", s->stack[i]);

                

        }

        printf("\n");           

}

 

element pop(StackType *s){

        if(is_empty(s)){

                fprintf(stderr, "스택 공백 에러 \n");

                exit(1);

        }

        else return s->stack[(s->top)--];

}

 

element peek(StackType *s){

        if(is_empty(s)){

                fprintf(stderr,"스택 공백 에러\n");

                exit(1);

        }

        else return s->stack[s->top];

}

 

int check_matching(char *in){

        StackType s;

        char ch, open_ch;

        

        int i, n = strlen(in);

        init(&s);

        

        for(i=0;i<n;i++){

                ch = in[i];

                switch(ch){

                case '(': case '[': case '{':

                        push(&s, ch);

                        printf("현재 스택의 상태 : ");

                        display(&s);

                        system("pause");

                        break;

                        

                case ')': case ']': case '}':

                        if(is_empty(&s)) return FALSE;

                        else{

                                open_ch = pop(&s);

                                printf("현재 스택의 상태 : ");

                                display(&s);

                                system("pause");

                                

                                if( (open_ch == '(' && ch != ')') ||

                                        (open_ch == '(' && ch != ')') ||

                                        (open_ch == '(' && ch != ')')) {

                                        return FALSE;

                                }                       

                                break;

                        }

                }

        }

        if(!is_empty(&s)) return FALSE;

        return TRUE;

}

 

int main(){

        char operation[100];

        printf("수식을 입력하세요 > "); /* ex) {A[(i+1)]=0;} */

        scanf("%s", operation);

        

        if(check_matching(operation) == TRUE)

                printf("괄호검사 성공\n");

        else

                printf("괄호검사 실패\n");  

}

int 타입의 top 변수에 스택의 인덱스를 관리하면서 배열 최대값에 도달하지 않도록 관리하고 있다.

아래 똑같은 코드에서 해당 구조체의 주소를 관리하는 top 포인터 변수를 사용하여 스택 포화 문제점을 해결해보자.

 

Case 2: 괄호검사 프로그램(동적 배열 스택)

#include <stdio.h>

#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
typedef struct StackNode{
 int item;
 struct StackNode *link;
}StackNode;
typedef struct{
 StackNode *top;
}LinkedStackType;
void init(LinkedStackType *s)
{
 s->top = NULL;
}
int is_empty(LinkedStackType *s)
{
 return (s->top == NULL);
}
int pop(LinkedStackType *s)
{
 if(is_empty(s)){
  fprintf(stderr, "stack is empty!\n");
  exit(1);
 }
 else{
  StackNode *temp=s->top;
  int item = temp->item;
  s->top = s->top->link;
  free(temp);
  return item;
 }
 
}
void push(LinkedStackType *s, int item)
{
 StackNode *temp=(StackNode *)malloc(sizeof(StackNode));
 if(temp == NULL){
  fprintf(stderr,"메모리할당에러\n");
  return;
 }
 else{
  temp->item = item;
  temp->link = s->top;
  s->top = temp;
 }
}
int check_matching(char *in){
 LinkedStackType s;
 char ch, open_ch;
 int i,n = strlen(in);
 init(&s);
 
 for(i=0;i<n;i++){
  ch = in[i];
  switch(ch){
  case '(': case '[' : case'{':
   push(&s,ch);
   break;
  case ')': case ']': case'}':
   if(is_empty(&s)) return FALSE;
   else{
    open_ch = pop(&s);
    if((open_ch == '(' && ch != ')') ||
     (open_ch == '[' && ch!= ']') ||
     (open_ch == '{' && ch!= '}'))
     return FALSE;
    break;
   }
  }
 }
 if(!is_empty(&s)) return FALSE;
 return TRUE;   
}
void main(){
 if(check_matching("{A[(i+1)]=0;}") == TRUE)
  printf("괄호검사성공\n");
 else
  printf("괄호검사실패\n");
}

 

심화과정 Linked Stack(연결 리스트를 활용한 스택)

#include <stdio.h>

#include <stdlib.h>

typedef int element;

typedef struct StackNode{

        element data;

        struct StackNode *link;

} StackNode;

typedef struct StackType{

        StackNode *top;

} QueueType;

void error(char *message){

        fprintf(stderr,"%s\n",message);

        exit(1);

}

void init(StackType *s){

        s->top = NULL;

}

int is_empty(StackType *s){

        return (s->top == NULL);

}

int is_full(StackType *s){

        return 0;

}

void push(StackType *s, element item){

        StackNode *Newnode = (StackNode *)malloc(sizeof(StackNode));

        if(Newnode == NULL)

                error("메모리를 할당할 수 없습니다");

        else{

                Newnode->data = item;

                Newnode->link = s->top;

                s->top = Newnode;

        }

}

element pop(StackType *s){

        if(is_empty(s))

                error("스택이 비어 있습니다");

        else{

                StackNode *Newnode = s->top;

                element item = Newnode->data;

                s->top = s->top->link;

                free(Newnode);

                return item;

        }

}

element peek(StackType *s){

        if(is_empty(s))

                error("스택이 비어 있습니다");

        else{

                return s->top->data;

        }

}

 

void display(StackType *s){

        StackNode *temp = s->top;

        while(temp != NULL){

                printf("%d-> ",temp->data);

                temp = temp->link;

        }

        printf("\n");

}

 

element get_count(StackType *s){

        int count=0;

        StackNode *temp = s->top;

        while(temp != NULL){

                count++;

                temp = temp->link;

        }

        printf("현재 스택의 item의 개수 : %d개\n", count);

        return count;

}

void main(){

        StackType s;

 

        init(&s);

        push(&s, 1);

        push(&s, 2);

        push(&s, 3);

        push(&s, 4);

        pop(&s);

        display(&s);

        get_count(&s);

}