오늘은 스택에 대해 배웠다.
스택(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일차 끝-
반응형
'공부기록 > 자료구조알고리즘' 카테고리의 다른 글
| 자료구조+알고리즘 2일차 (1) | 2023.07.29 |
|---|---|
| 자료구조+알고리즘 1일차 (3) | 2023.07.27 |