자료구조+알고리즘 4일차

오늘은 스택에 대해 배웠다.

스택(stack)

4일차 (23.08.01)

이진탐색 복습
스택 함수 구현
+) 스택 함수 응용해봄

스택(stack)은 데이터를 일시적으로 저장하기 위한 자료구조 중에 하나인데 후입선출 구조를 띰.

Last In First Out 즉 마지막에 넣어진 값이 첫번째로 나가는 형태이고.. 큐랑은 많이 다르지

데이터를 넣는 작업 : push

데이터를 빼내는 작업 : pop

데이터의 꼭대기 : top

1. 이진 탐색 복습

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

int binary_search_desc(const int *arr, int size, int value) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (arr[middle] == value) {
            return middle;
        } else if (arr[middle] > value) { // 내림차순의 경우 '>'
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}

int main(void) {
    int nx;
    int ky;
    printf("이진검색 함수2\n");
    printf("요소 개수 : ");
    scanf("%d", &nx);
    int *x = calloc(nx, sizeof(int));

    printf("첫 번째 요소: ");
    scanf("%d", &x[0]);
    for (int i = 1; i < nx; i++) {
        do {
            printf("x[%d]: ", i);
            scanf("%d", &x[i]);
        } while (x[i] >= x[i - 1]); // 내림차순이므로 다음 값이 같거나 더 커야 함
    }
    printf("검색할 값: ");
    scanf("%d", &ky);

    int index = binary_search_desc(x, nx, ky);

    if (index != -1) {
        printf("검색 값 %d은(는) x[%d]에 있음.\n", ky, index);
    } else {
        printf("검색 값 %d은(는) 없음.\n", ky);
    }

    free(x);

    return 0;
}

이런식으로 첫 번째 요소를 먼저 입력받고 그 다음 요소가 그 전의 요소보다 작아야만 다음으로 넘어가도록 while문을 돌렸고, 마지막에 검색할 값에서 찾는 값이 있으면 몇번째 요소인지를 알려주고, 없으면 없다고 뜬다.

2. 스택 구현

// 헤더파일(스택기능.h), 소스파일2개(메인.c/스택기능.c)
#include <stdio.h>
#include <stdlib.h>
// 헤더파일 선언

// 스택을 구현하는 구조체
typedef struct{
  int max; //스택의 용량 -> stk의 요소 갯수와 같아야 함.
  int ptr; // 스택포인터 -> 스택에 쌓여있는 데이터 개수, 스택 비어있으면 ptr 0/ 스택이 가득차있으면 max
  int *stk; //스택의 첫 요소에 대한포인터 -> 스택으로 사용할 배열을 가르키는 포인터
} IntStack;

/*--- 스택 초기화 ---*/
int Initialize(IntStack *s, int max){
  s->ptr =0; //처음 주소값은 0, 스택이 비어있어야 하니까
  if((s->stk = calloc(max,sizeof(int)))==NULL){
    s->max = 0; // 접근할 수 있는 skt[0], skt[1] ,... , skt[max-1]
    return -1;
  }
  s->max = max;
  return 0;
  
};

/*--- 스택 pop 데이터를 제거하는 함수 ---*/
// 꼭대기에서 제거합니다
int Pop(IntStack *s, int *x){
  if (s ->ptr <= 0) // 스택이 비어있는 경우
    return -1;
  
  *x = s -> stk[--s -> ptr]; // 감소를 시키면서 가져와야 한다
  return 0;
};


/*--- 스택 push 데이터를 추가하는 함수 ---*/
// 성공하면 0 반환, 실패하면 -1 반환

int Push(IntStack *s, int x){
  if (s -> ptr >= s -> max) // 스택이 가득차 있는 상태
    return -1;
  
  s -> stk[s->ptr++] = x;
  return 0;
};

/* --- 스택 peek 데이터를 제거하는 함수 ---*/
int Peek(IntStack * s, int *x){
  if (s->ptr <= 0) // 스택이 비어있는가?
      return -1;
  *x = s->stk[s->ptr-1];
  return 0;
};

/*--- 스택 clear 모든 데이터를 삭제하는 함수  ---*/
void Clear(IntStack *s){
  s->ptr = 0;
};




// main.c 구현
int main(void){
  IntStack s;
  if (Initialize(&s, 64) == -1){
    printf("스택 생성에 실패했습니다.");
    return 1;
  }
  while(1) {
    int menu, x;
    printf("현재 데이터 수: %d \n", s.ptr);
    printf("1.push 2.pop 3.peek 4.clear 5.종료\n");
    scanf("%d", &menu);
    if (menu == 1){
      Push(&s, x);
    }
    else if (menu == 2){
      Pop(&s, &x);
    }
    else if (menu == 3){
      Peek(& s, &x);
    }
    else if (menu == 4){
      Clear(&s);
    }
    else if (menu == 5){
      break;
    }
    
    
  }
  
  // Terminate(&s);
  free(s.stk);
  return 0;


  
}

push, pop, peek, clear 기능을 구현해보았다.

근데 해보니까 너무 심심해서 시각적으로 보이면 어떨까 싶었다. 그리고 나는 실제로 c를 할 때 visual studio 쓰니까 헤더파일이랑 소스파일 나눠서 구현해보면 어떨까 싶어서 나눠서 좀 멋있게 해봄.. 근데 peek 은 처음 보는데 어디에 쓰는건지 나중에 조금 더 공부해야겠다

3. 스택 함수 응용해봄

#pragma once
#define _CRT_SECURE_NO_WARNINGS


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

typedef struct {
	int max;
	int ptr;
	int* stk;

}IntStack;

int Initialize(IntStack* s, int max);
int Pop(IntStack* s, int* x);
int Push(IntStack* s, int max);
int Peek(IntStack* s, int* max);
void Clear(IntStack* s);
void Print(const IntStack* s);

먼저 stack.h 헤더파일을 따로 만들었다.

#include "stack.h"



int Initialize(IntStack* s, int max) {
    s->ptr = 0; //처음 주소값은 0, 스택이 비어있어야 하니까
    if ((s->stk = calloc(max, sizeof(int))) == NULL) {
        s->max = 0; // 접근할 수 있는 skt[0], skt[1] ,... , skt[max-1]
        return -1;
    }
    s->max = max;
    return 0;

};

/*--- 스택 pop 데이터를 제거하는 함수 ---*/
// 꼭대기에서 제거합니다
int Pop(IntStack* s, int* x) {
    if (s->ptr <= 0) // 스택이 비어있는 경우
        return -1;

    *x = s->stk[--s->ptr]; // 감소를 시키면서 가져와야 한다
    printf("Pop 값: %d\n", *x);
    return 0;
};


/*--- 스택 push 데이터를 추가하는 함수 ---*/
// 성공하면 0 반환, 실패하면 -1 반환

int Push(IntStack* s, int x) {
    if (s->ptr >= s->max) // 스택이 가득차 있는 상태
        return -1;
    
    printf("값을 입력하세요: ");
    scanf("%d", &x);
    s->stk[s->ptr++] = x;
    return 0;
};

/* --- 스택 peek 데이터를 제거하는 함수 ---*/
int Peek(IntStack* s, int* x) {
    if (s->ptr <= 0) // 스택이 비어있는가?
        printf("스택이 비어 있습니다.\n");
        return -1;
    *x = s->stk[s->ptr - 1];
    printf("스택의 꼭대기에 있는 요소: %d\n", s->stk[s->ptr - 1]);
    return 0;
};

/*--- 스택 clear 모든 데이터를 삭제하는 함수  ---*/
void Clear(IntStack* s) {
    s->ptr = 0;
    printf("스택이 비워졌습니다.\n");
};

/*--- 스택의 모든 요소를 시각적으로 출력하는 함수 ---*/
void Print(const IntStack* s) {
    printf("스택 상태: \n");
    for (int i = s->max - 1; i >= 0; i--) {
        if (i < s->ptr) {
            printf("| %d |\n", s->stk[i]);
        }
        else {
            printf("|   |\n"); // 비어 있는 슬롯을 표시
        }
    }
    printf("------\n");
}

소스파일 중에 스택의 기능만 가지고 있는 function.c 를 따로 만들었다

#include "stack.h"

// main.c 구현
int main(void) {
    IntStack s;
    if (Initialize(&s, 64) == -1) {
        printf("스택 생성에 실패했습니다.");
        return 1;
    }
    printf("1. push 2. pop 3. clear 4. 출력 5. 종료\n");
    while (1) {
        int menu, x=0;
        
        
        scanf("%d", &menu);
        if (menu == 1) {
            Push(&s, x);
            Print(&s);
            
        }
        else if (menu == 2) {
            Pop(&s, &x);
            Print(&s);
        }
        else if (menu == 3) {
            Clear(&s);
            Print(&s);
        }
        else if (menu == 4) {
            Peek(&s, &x);
            printf("현재 데이터 수: %d \n", s.ptr);
        }
        else if (menu == 5) {
            break;
        }


    }

    // Terminate(&s);
    free(s.stk);
    return 0;



}

마지막으로 main.c를 따로 나눠서 구현해줬다.

아 동영상 잘 보이게 올려지는 줄 알았는데 아니었네..ㅜ

-4일차 끝-