티스토리 뷰
Develop Story/Data Structure & Algorithm
<뇌를 자극하는 알고리즘 #3>: 배열로 구현된 스택(AS) 퀴즈풀이
wisecow 2017. 7. 22. 13:43Vitamin Quiz
문제) 위 예제의 AS_IsFULL(ArrayStack *Stack) 함수를 추가하라. 스택을 생성할 때 정한 용량이 가득 차 있는지 체크하는 기능이다. 함수의 원형은 다음과 같다.
int AS_IsFULL(ArrayStack *Stack);
풀이 // 이 글은 드래그 및 복붙이 안되므로 아래 첨부한 파일을 다운받아 보시기 바랍니다. 첫 번째는 교재의 소스코드 및 헤더파일, 두 번째는 데브맷의 풀이입니다.
문제가 굉장히 쉽다. 왜냐하면, 애초에 ArrayStack 구조체를 정의할 때, Capacity라는 변수도 추가해줬기 때문이다. 따라서 스택이 가득 차 있는지 확이하려면 현재 배열에 들어온 원소의 갯수를 나타내는 Top 변수와 Capacity가 같은지 여부만 체크해주면 된다.
/************************************************* ** ArrayStack Vitamin Quiz *************************************************/ #include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct tagNode { ElementType Data; } Node; typedef struct tagArrayStack { int Capacity; int Top; Node *Nodes; } ArrayStack; void AS_CreateStack(ArrayStack **Stack, int Capacity) { // 스택을 동적할당 (*Stack) = (ArrayStack *)malloc(sizeof(ArrayStack)); // 입력된 Capacity 만큼의 노드를 동적할당 (*Stack)->Nodes = (Node *)malloc(sizeof(Node) * Capacity); // Capacity 및 Top 초기화 (*Stack)->Capacity = Capacity; (*Stack)->Top = 0; } void AS_DestroyStack(ArrayStack *Stack) { free(Stack->Nodes); free(Stack); } void AS_Push(ArrayStack *Stack, ElementType Data) { int Position = Stack->Top; Stack->Nodes[Position].Data = Data; Stack->Top++; } ElementType AS_Pop(ArrayStack *Stack) { int Position = --(Stack->Top); return Stack->Nodes[Position].Data; } // 배열의 특성상 인덱스 값은 Top - 1 이 되어야 한다. ElementType AS_Top(ArrayStack *Stack) { int Position = Stack->Top - 1; return Stack->Nodes[Position].Data; } // Stack에 존재하는 원소의 갯수를 리턴 int AS_GetSize(ArrayStack *Stack) { return Stack->Top; } int AS_IsEmpty(ArrayStack *Stack) { return (Stack->Top == 0); } int AS_IsFull(ArrayStack *Stack) { return (Stack->Top == Stack->Capacity); } void main() { int i = 0; ArrayStack *Stack = NULL; AS_CreateStack(&Stack, 10); AS_Push(Stack, 3); AS_Push(Stack, 37); AS_Push(Stack, 11); AS_Push(Stack, 12); AS_Push(Stack, 13); AS_Push(Stack, 14); AS_Push(Stack, 15); AS_Push(Stack, 16); AS_Push(Stack, 17); AS_Push(Stack, 128); printf("Capacity: %d, Size: %d, Top: %d\n\n", Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack)); printf("IsFullStack ? %s\n", AS_IsFull(Stack) == 1 ? "TRUE" : "FALSE"); for (i = 0; i < 10; i++) { if (AS_IsEmpty(Stack)) break; printf("Poped: %d, ", AS_Pop(Stack)); if (!AS_IsEmpty(Stack)) printf("Current Top: %d\n", AS_Top(Stack)); else printf("Stack Is Empty.\n"); } AS_DestroyStack(Stack); } /************************************************* ** End Line *************************************************/
'Develop Story > Data Structure & Algorithm' 카테고리의 다른 글
<뇌를 자극하는 알고리즘 #5>: 버블정렬(BubbleSort) 퀴즈풀이 (0) | 2017.07.23 |
---|---|
<뇌를 자극하는 알고리즘 #4>: 트리(LCRSTree) 퀴즈풀이 (0) | 2017.07.22 |
<뇌를 자극하는 알고리즘 #2>: 이중 연결 리스트(DLL) 퀴즈풀이 (0) | 2017.07.22 |
<뇌를 자극하는 알고리즘 #1>: 단일 연결 리스트(SLL) 퀴즈풀이 (0) | 2017.07.21 |
<선택 정렬 및 이진 탐색 알고리즘> #Selection sort #Binary search (0) | 2017.07.18 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday