[자료구조 - C언어] 자료구조 [15강-17강] 복습 및 정리

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

자료구조 15강

• 스택: 삽입과 삭제가 한쪽 끝에서 이루어지는 리스트의 일종
  • 삽입과 삭제가 일어나는 쪽을 스택의 top이라고 부름
  • LIFO: 가장 나중에 들어간 애가 가장 먼저 나옴
• 스택이 지원하는 연산
  • push: 스택에 새로운 원소를 삽입하는 연산
  • pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환
  • peek: 스택의 top에 있는 원소를 제거하지 않고 값만 반환 → 스택은 변화 없음
  • is_empty: 스택이 비었는지 검사
• 배열을 이용한 스택의 구현

  

  //int를 Item으로 부르겠다: 코드의 재사용성을 높이기 위해
  typedef int Item;
  //*Stack이 가리키고 있는 장소에 있는 데이터의 타입이 struct stack_type                 
  typedef struct stack_type *Stack; 
  
  //contents, top, size를 하나의 스택으로
  struct stack_type{
      Item *contents;    //배열
      int top;           //스택의 top을 가리키는 변수
      int size;          //배열의 크기
  };

  • 스택의 생성

    #define INIT_CAPACITY 100
    
    //스택을 만들어서 주소를 리턴해주는 함수
    Stack create(){
        Stack s = (Stack)malloc(sizeof(struct stack_type));
        if(s==NULL)
            printf("Error in create: stack could not be created.\n");
    	
        s->contents = (Item *)malloc(INIT_CAPACITY * sizeof(Item));
        if(s->contents==NULL){
            free(s);
            printf("Error in create: stack could not be created.\n");
        }
    	
        s->top = -1;
        s->size = INIT_CAPACITY;
        return s;
    }
    
    //생성 예시
    Stack s = create();

  • push

    void push(Stack s, Item i){
        //스택이 가득 찼다면 ~ 재할당
        if(s->top + 1 == s->size)
            reallocateStack(s);
        s->top++;
        s->contents[s->top] = i;
    }
    
    //재할당 함수
    void reallocateStack(Stack s){
        Item *tmp = (Item *)malloc(2 * s->size * sizeof(Item));
        if(tmp==NULL)
            printf("Error in create: stack could not be created.\n");
        for(int i=0;i<s->size;i++){
            tmp[i] = s->contents[i];
        free(s->contents);
        s->contents = tmp;
        s->size *= 2;
    }

  • pop

    //스택에서 가장 마지막에 들어온 데이터를 삭제하고 값을 반환하는 함수
    Item pop(Stack s){
        //스택이 비어 있다면
        if(is_empty())
            printf("Error in pop: stack is empty.\n");
        s->top--;
        return s->contents[s->top+1];
    }

  • peek
    

    Item peek(Stack s){
        if(is_empty(s))
            terminate("Error in peek: stack is empty.");
        return s->contents[s->top];
    }

  • is_empty
    

    bool is_empty(Stack s){
        return s->top == -1;
    }

• 연결 리스트를 이용한 스택의 구현
  • 연결 리스트의 맨 앞이 노드를 삽입/삭제하기에 편하다→ 맨 앞을 스택의 top으로 한다.
    • 단방향 연결 리스트에서 노드를 삭제할 때 이전 노드의 주소가 필요하기 때문 ~ 마지막은 top(X)

  

  //int를 Item으로 부르겠다: 코드의 재사용성을 높이기 위해
  typedef int Item;
  //*Stack이 가리키고 있는 장소에 있는 데이터의 타입이 struct stack_type                 
  typedef struct stack_type *Stack; 
  
  struct node{
      Item data;
      struct node *next;
  };
  
  //노드들이 연결된 구조로, 배열이나 사이즈 필요 없음
  struct stack_type{
      struct node *top;
  }

  • 스택의 생성

    Stack create(){
        Stack s = malloc(sizeof(struct stack_type));
        if(s==NULL)
            terminate("Error in create: stack could not be created.");
        s->top = NULL;    //empty stack
        return s;
    }

  • push

    void push(Stack s, Item i){
        struct node *new_node = malloc(sizeof(struct node));
        if(new_node==NULL)
            terminate("Error in push: stack is full.");
        new_node->data = i;
        new_node->next = s->top;
        s->top = new_node;
    }

  • pop

    Item pop(Stack s){
        struct node *old_top;
        Item i;
        
        if(is_empty(s))
            terminate("Error in pop: stack is empty.");
        
        //old_top이 현재 pop할 노드를 기억
        old_top = s->top;
        //최종적으로 리턴해주어야 할 값 i
        i = old_top->data;
        s->top = old_top->next;
        free(old_top);    //i에 저장해두었기 때문에 free해도 됨
        return i;
    }

  • peek

    Item peek(Stack s){
        if(is_empty(s))
            printf("Error in peek: stack is empty.\n");
        return s->top->data;
    }

  • is_empty
    

    bool is_empty(Stack s){
        return s->top==NULL;
    }

 

자료구조 16강

• 스택을 응용해서
  • 후위 표기식을 계산할 수 있다. 
  • 중위 표기식 → 후기 표기식으로 변환할 수 있다.

    

  • 괄호가 있는 중위 표기식 → 후기 표기식으로 변환할 수 있다.

    

 

자료구조 17강

• 스택을 응용해서 미로 찾기를 구현할 수 있다.
  • 잘못된 길에 들어섰을 때 이전으로 돌아갈 때 스택을 사용할 수 있다.
    • 이동한 방향을 스택에 저장해 두고 → 돌아가야 할 때마다 스택의 top을 pop 해서 직전 위치로 이동

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.