[Do it! 자료구조와 함께 배우는 알고리즘 입문 C언어편] 04장 스택과 큐

etc./Do it! 공부단

[Do it! 자료구조와 함께 배우는 알고리즘 입문 C언어편] 04장 스택과 큐

innit 2021. 9. 1. 21:38

1. 책 DB를 넣어주세요.

2. 나의 스터디 흔적을 사진으로 보여주세요.

3. 이번 스터디에서 특별히 좋았던 점이나 어려웠던 점이 있었나요? 새로 알게된 부분이 있다면 알려주세요. 다음에 이 책으로 공부할 스터디룸의 독자들에게 큰 도움이 됩니다.

- (p.133) 스택 구조체 IntStack의 멤버 3가지

- int *stk : 배열을 가르키는 포인터

- int max : 스택의 최대 용량

- int ptr : 현재 데이터 개수

- (p.134) 스택 관련 함수

- int Initialize (IntStack *s, int max) : 크기가 max인 스택 s를 만들겠다

- int Push (IntStack *s, int x) : x를 스택 s에 넣겠다

- int Pop (IntStack *s, int *x) : 스택 s 꼭대기 값을 꺼내서 포인터 x에 기억하겠다

- int Peek (const IntStack *s, int *x) : 스택 s 꼭대기 값을 포인터 x에 기억하겠다

- void Clear (IntStack *s) : 스택 s를 비우겠다

- int Capacity (const IntStack *s) : 스택 s의 크기를 반환

- int Size (const IntStack *s) : 현재 스택 s에 있는 데이터 개수 반환

- int IsEmpty (const IntStack *s) : 스택 s가 비어있으면 1을 반환

- int IsFull (const IntStack *s) : 스택 s가 가득 찼으면 1을 반환

- int Search (const IntStack *s, int x) : 스택 s에서 x의 위치를 반환 (존재하지 않으면 -1을 반환)

- int Print (const IntStack *s) : 스택 s에 있는 모든 데이터를 출력

- void Terminate (IntStack *s) : 스택 s를 삭제

IntStack.h	IntStack.c	IntStackTest.c
#ifndef ___IntStack #define ___IntStack typedef struct { int max; int ptr; int* stk; } IntStack; int Initialize(IntStack* s, int max); int Push(IntStack* s, int x); int Pop(IntStack* s, int x); int Peek(const IntStack s, int* x); void Clear(IntStack* s); int Capacity(const IntStack* s); int Size(const IntStack* s); int IsEmpty(const IntStack* s); int IsFull(const IntStack* s); int Search(const IntStack* s, int x); void Print(const IntStack* s); void Terminate(IntStack* s); #endif	#include <stdio.h> #include <stdlib.h> #include "IntStack.h" int Initialize(IntStack* s, int max) { s->ptr = 0; if ((s->stk = calloc(max, sizeof(int))) == NULL) { s->max = 0; return -1; } s->max = max; return 0; } int Push(IntStack* s, int x) { if (s->ptr >= s->max) return -1; s->stk[s->ptr++] = x; return 0; } int Pop(IntStack* s, int* x) { if (s->ptr <= 0) return -1; x = s->stk[s->ptr--]; return 0; } int Peek(const IntStack s, int* x) { if (s->ptr <= 0) return -1; x = s->stk[s->ptr - 1]; return 0; } void Clear(IntStack s) { s->ptr = 0; } int Capacity(const IntStack* s) { return s->max; } int Size(const IntStack* s) { return s->ptr; } int IsEmpty(const IntStack* s) { return s->ptr <= 0; } int IsFull(const IntStack* s) { return s->ptr >= s->max; } int Search(const IntStack* s, int x) { int i; for (i = s->ptr - 1; i >= 0; i--) if (s->stk[i] == x) return i; return -1; } void Print(const IntStack* s) { int i; for (i = 0; i < s->ptr; i++) printf("%d ", s->stk[i]); putchar( '\n'); } void Terminate(IntStack* s) { if (s->stk != NULL) free(s->stk); s->max = s->ptr = 0; }	#include <stdio.h> #include "IntStack.h" int main(void) { IntStack s; if (Initialize(&s, 64) == -1) { puts("스택 생성에 실패하였습니다."); return 1; } while (1) { int menu, x; printf("현재 데이터 수 : %d / %d\n", Size(&s), Capacity(&s)); printf("(1) 푸시 (2) 팝 (3) 피크 (4) 출력 (5) 종료 : "); scanf("%d", &menu); if (menu == 0) break; switch (menu) { case 1: printf("데이터 : "); scanf("%d", &x); if (Push(&s, x) == -1) puts("\a오류 : 푸시에 실패하였습니다."); break; case 2: if (Pop(&s, &x) == -1) puts("\a오류 : 팝에 실패하였습니다."); else printf("팝 데이터는 %d입니다.\n", x); break; case 3: if (Peek(&s, &x) == -1) puts("\a오류 : 피크에 실패하였습니다."); else printf("피크 데이터는 %d입니다.\n", x); break; case 4: Print(&s); break; } } Terminate(&s); return 0; }

- (p.145) 링버퍼 : 큐에서 디큐할 때마다 배열 요소들을 모두 앞쪽으로 옮기는 수고를 덜기 위해서 사용되는 자료구조

- (p.148) 큐 구조체 IntQueue의 멤버 5가지

- int* que : 배열을 가르키는 포인터

- int max : 큐의 최대 용량

- int num : 현재 데이터 개수

- int front : 큐의 첫 요소

- int rear : 큐의 마지막 요소

IntQueue.h	IntQueue.c	IntQueueTest.c
#ifndef ___IntQueue #define ___IntQueue typedef struct { int max; int num; int front; int rear; int* que; } IntQueue; int Initialize(IntQueue* q, int max); int Enque(IntQueue* q, int x); int Deque(IntQueue* q, int* x); int Peek(const IntQueue* q, int* x); void Clear(IntQueue* q); int Capacity(const IntQueue* q); int Size(const IntQueue* q); int IsEmpty(const IntQueue* q); int IsFull(const IntQueue* q); int Search(const IntQueue* q, int x); void Print(const IntQueue* q); void Terminate(IntQueue* q); #endif	#include <stdio.h> #include <stdlib.h> #include "IntQueue.h" int Initialize(IntQueue* q, int max) { q->num = q->front = q->rear = 0; if ((q->que = calloc(max, sizeof(int))) == NULL) { q->max = 0; return -1; } q->max = max; return 0; } int Enque(IntQueue* q, int x) { if (q->num >= q->max) return -1; else { q->num++; q->que[q->rear++] = x; if (q->rear == q->max) q->rear = 0; return 0; } } int Deque(IntQueue* q, int* x) { if (q->num <= 0) return -1; else { q->num--; x = q->que[q->front++]; if (q->front == q->max) q->front = 0; return 0; } } int Peek(const IntQueue q, int* x) { if (q->num <= 0) return -1; x = q->que[q->front]; return 0; } void Clear(IntQueue q) { q->num = q->front = q->rear = 0; } int Capacity(const IntQueue* q) { return q->max; } int Size(const IntQueue* q) { return q->num; } int IsEmpty(const IntQueue* q) { return q->num <= 0; } int IsFull(const IntQueue* q) { return q->num >= q->max; } int Search(const IntQueue* q, int x) { int i, idx; for (i = 0; i < q->num; i++) { if (q->que[idx = (i + q->front) % q->max] == x) return idx; } return -1; } void Print(const IntQueue* q) { int i; for (i = 0; i < q->num; i++) printf("%d ", q->que[(i + q->front) % q->max]); putchar('\n'); } void Terminate(IntQueue* q) { if (q->que != NULL) free(q->que); q->max = q->num = q->front = q->rear = 0; }	#include <stdio.h> #include "IntQueue.h" int main() { IntQueue que; if (Initialize(&que, 5) == -1) { puts("큐의 생성에 실패하였습니다."); return 1; } while (1) { int m, x; printf("현재 데이터 수 : %d / %d \n", Size(&que), Capacity(&que)); printf("(1)인큐 (2)디큐 (3)피크 (4)삭제 (5)최대 용량 (6)쌓여있는 데이터 수 (7)비어 있나요? (8)가득 찼나요? (9)검색 (10)모두 출력 : "); scanf("%d", &m); if (m == 0) break; switch (m) { case 1: printf("데이터 : "); scanf("%d", &x); if (Enque(&que, x) == -1) puts("\a오류: 인큐에 실패하였습니다."); break; case 2: if (Deque(&que, &x) == -1) puts("\a오류 : 디큐에 실패하였습니다."); else printf("디큐한 데이터는 %d입니다.\n", x); break; case 3: if (Peek(&que, &x) == -1) puts("\a오류 : 피크에 실패하였습니다."); else printf("피크한 데이터는 %d입니다.\n", x); break; case 4: Clear(&que); puts("큐에 있는 데이터를 모두 삭제하였습니다."); break; case 5: printf("큐의 최대 용량은 %d입니다.\n", Capacity(&que)); break; case 6: printf("큐에 있는 데이터는 %d개 입니다.\n", Size(&que)); break; case 7: if (IsEmpty(&que) == 1) puts("큐는 비어있습니다."); else puts("큐는 비어있지 않습니다."); break; case 8: if (IsFull(&que) == 1) puts("큐는 가득 찼습니다."); else puts("큐는 가득 차지 않았습니다."); break; case 9: printf("검색할 데이터 : "); scanf("%d", &x); if (Search(&que, x) == -1) puts("해당 데이터가 존재하지 않습니다."); else printf("%d는 %d번째에 위치하고 있습니다.", Search(&que, x)); break; case 10: Print(&que); break; } } Terminate(&que); return 0; }