[자료구조 - C언어] 자료구조 제15강: 스택(Stack) 개념과 구현(3)

2022. 11. 10. 17:27ㆍCS/자료구조

728x90

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

 

1. 문제점

  • 만약 스택이 동시에 2개 이상 필요하다면?
    ⇒ 하나의 함수로 문제를 해결하기 위해서는
    • push(), pop() 등의 함수가 매개변수로 stack을 받아야 한다.
    Stack s1 = create();
Stack s2 = create();

push(s1, 12);
push(s2, 9);

 

2. stackADT.h

//  stackADT.h

#ifndef STACKADT_H
#define STACKADT_H

#include <stdio.h>
#include <stdbool.h>

//re-definition, 별명을 만들어 줌, int를 Item이라고 부르겠다.
typedef int Item;

typedef struct stack_type *Stack;

Stack create();
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
void push(Stack s, Item i);
Item pop(Stack s);
Item peek(Stack s);
void reallocateStack(Stack s)

//임의 작성
bool is_full(Stack s);
void printStack(Stack s);
#endif /* STACKADT_H */

2-1. typedef int Item;

typedef int Item;
  • re-definition: 별명을 만들어줌
  • 그냥 int를 Item으로 부르겠다.
    • 현재 코드에서는 정수(int)형을 저장하는데
    • 만약 다른 실수(float)형 등의 자료형을 저장할 때 → 코드의 재사용성을 높이기 위해서
    //코드 한 줄만 수정하면 된다.
typedef float Item;

2-2. typedef struct stack_type *Stack;

typedef struct stack_type *Stack;
  1. struct stack_type * 를 stack이라고 한다.
  2. *Stack이 가리키고 있는 장소에 있는 데이터의 타입이 struct stack_type이다.
  • 1과 2는 동일한 의미이며, 다음과 같이 정의하면 코드에서 ‘*’를 사용할 일이 줄어든다. 
    //Stack 자체가 struct stack_type *로 정의했기 때문에 '(Stack *)'를 사용하지 않아도 됨
//Stack * 타입이 아니라 Stack 타입 -> Stack 자체가 struct stack_type *으로 정의했기 때문
Stack s = (Stack)malloc(sizeof(struct stack_type));
    • 만약 *를 사용하지 않았다면 
      typedef struct stack_type Stack;
Stack s = (Stack *)malloc(sizeof(struct stack_type));

 

3. 배열로 구현한 stackADT_array.c

3-1. struct stack_type

//contents, top, size를 하나의 스택으로
struct stack_type{
    Item *contents;            //배열
    int top;                   //스택의 top을 가리키는 변수
    int size;                  //배열의 크기
};

3-2. stackADT_array.c

//  stackADT.c

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

#define INIT_CAPACITY 100

//contents, top, size를 하나의 스택으로
struct stack_type{
    Item *contents;            //배열
    int top;                   //스택의 top을 가리키는 변수
    int size;                  //배열의 크기
};

;

//예외적 상황에 대한 메세지 출력 함수
//static 함수 - 해당 파일 내에서만 호출할 수 있는 함수
//->같은 이름의 함수를 여러 개의 파일에서 생성할 수 있어 충돌을 방지
static void terminate(const char *message){
    printf("%s\\n", message);
    exit(1);    //종료
}

//스택을 만들어서 주소를 리턴해주는 함수
Stack create(){
    //Stack 자체가 struct stack_type *로 정의했기 때문에 '(Stack *)'를 사용하지 않아도 됨
    //Stack * 타입이 아니라 Stack 타입 -> Stack 자체가 struct stack_type *으로 정의했기 때문
    Stack s = (Stack)malloc(sizeof(struct stack_type));
    if(s==NULL)
        terminate("Error in create: stack could not be created.");
    
    //스택 자체만 생성해서는 안되고, 내부의 contents에 달려 있는 배열도 동적 할당으로 생성
    s->contents = (Item *)malloc(INIT_CAPACITY * sizeof(Item));
    if(s->contents == NULL){
        free(s);
        terminate("Error in create: stack could not be created.");
    }
    s->top = -1;
    s->size = INIT_CAPACITY;
    return s;    //동적으로 생성된 s의 주소를 리턴
}

//스택이 필요 없어 졌을 때 free해서 가비지 문제 해결
void destroy(Stack s){
    free(s->contents);
    free(s);
}

//스택의 내용만 비우는 함수, 스택을 다른 용도로 사용하기 위해서 스택을 초기화
void make_empty(Stack s){
    s->top = -1;
}

//스택이 비었는지 검사하는 함수
bool is_empty(Stack s){
    return s->top == -1;
}

void push(Stack s, Item i){
    if(is_full(s))
        reallocateStack(s);
    s->top++;
    s->contents[s->top] = i;
}

Item pop(Stack s){
    if(is_empty(s))
        terminate("Error in pop: stack is empty.");
    s->top--;
    //top을 감소시키고, 감소시키기 전의 위치를 반환
    return s->contents[s->top+1];
}

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

//스택이 꽉 찼을 때 reallocate
void reallocateStack(Stack s){
    //현재 사이즈의 2배 크기의 메모리를 malloc
    Item *tmp = (Item *)malloc(2 * s->size * sizeof(Item));
    if(tmp==NULL)
        terminate("Error in create: stack could not be created.");
    //현재 배열내의 데이터를 새로운 배열로 복사하고
    for(int i=0; i<s->size;i++)
        tmp[i] = s->contents[i];
    //필요 없어진 s는 free
    free(s->contents);
    //스택의 contents는 새로 생성된 tmp, 사이즈는 2배 증가
    s->contents = tmp;
    s->size *= 2;
}

//임의로 생성
bool is_full(Stack s){
    return s->top + 1 == s->size;
}
//임의로 생성
void printStack(Stack s){
    for(int i=s->top; i>-1; i--){
        printf(" %d", s->contents[i]);
    }
    printf("\\n");
}

3-3. stackADT_main.c

//  stackADT_main.c

#include "stackADT_array.h"

int main(){
    Stack s1 = create();
    Stack s2 = create();
    
    push(s1, 1);push(s1, 3); push(s1, 4);
    push(s2, 2);
    
    pop(s1);
    
    printStack(s1);    // 3 1
    printStack(s2);    // 2
}

4. 연결리스트로 구현한 stackADT_linkedlist.c

  • 동일한 헤더 파일 사용

4-1. stackADT_linkedlist.c

//  stackADT_linkedlist.c

#include <stdlib.h>
#include "stackADT.h"

struct node{
    Item data;
    struct node *next;
};

//배열이나 사이즈 필요 없음
//노드들이 연결된 구조
struct stack_type{
    struct node *top;
};

static void terminate(const char *message){
    printf("%s\\n", message);
    exit(EXIT_FAILURE);
}

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

//각각의 노드를 먼저 삭제하고 스택 free
void destroy(Stack s){
    make_empty(s);
    free(s);
}

//스택이 empty가 될 때 까지 pop
//pop 내부에서 데이터 free
void make_empty(Stack s){
    while(!is_empty(s))
        pop(s);
}

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

//add_first()와 유사
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;
}

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

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

//임의 생성
void printStack(Stack s){
    while(s->top != NULL){
        printf(" %d", s->top->data);
        s->top = s->top->next;
    }
    printf("\\n");
}

4-2. stackADT_main.c

//  stackADT_main.c

#include "stackADT_array.h"

int main(){
    Stack s1 = create();
    Stack s2 = create();
    
    push(s1, 1);push(s1, 3); push(s1, 4);
    push(s2, 2);
    
    pop(s1);
    
    printStack(s1);    // 3 1
    printStack(s2);    // 2
}

 

5. 남아있는 문제점

  • 서로 다른 타입의 데이터를 저장할 스택이 필요하다면?
    → Generic Program
    • void * 타입을 이용하여 generic 한 스택을 구현할 수 있으나 단점이 있음
    • 주로 c++과 같은 객체지향 프로그래밍 언어를 사용하는 것이 좋음

 

 

 

 

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

https://www.youtube.com/watch?time_continue=1834&v=PQHnuPnfqgU&feature=emb_title 

 

728x90

'CS > 자료구조' 카테고리의 다른 글

[자료구조 - C언어] 자료구조 제16강: 스택의 응용 - 후위표기식(2), (3)  (0) 2022.11.11
[자료구조 - C언어] 자료구조 제16강: 스택의 응용 - 후위표기식(1)  (0) 2022.11.11
[자료구조 - C언어] 자료구조 제15강: 스택(Stack) 개념과 구현(2)  (0) 2022.11.10
[자료구조 - C언어] 자료구조 제15강: 스택(Stack) 개념과 구현(1)  (0) 2022.11.10
[자료구조 - C언어] 자료구조 [11강-14강] 복습 및 정리  (0) 2022.11.09

관련글

댓글 0

티스토리툴바