1. 스택
- 입출력 창구가 한개임
- 가장 마지막에 들어간 데이터가 가장 먼저 나오고 가장 먼저 들어가면 가장 늦게 나오는 자료구조
- 스택의 사용 용도: 자동 메모리, 프로토콜 등이 대부분 스택을 기반으로 구성되어 있음
1-1. 스택의 연산
- 삽입(push): 새로운노드를 쌓음
- 제거(pop): 최상위 노드를 걷어냄
1-2. 배열로 구현한 스택
- ArrayStack.h
#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H
#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);
void AS_DestroyStack(ArrayStack *Stack);
void AS_Push(ArrayStack *Stack, ElementType Data);
ElementType AS_Pop(ArrayStack *Stack);
ElementType AS_Top(ArrayStack *Stack);
int AS_GetSize(ArrayStack *Stack);
int AS_IsEmpty(ArrayStack *Stack);
- ArrayStack.c
#include "ArrayStack.h"
//스택 생성
void AS_CreateStack(ArrayStack **Stack, int Capacity) {
//스택을 자유 저장소에 생성
(*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
//입력된 capacity만큼의 노드를 자유 저장소에 생성
(*Stack)->Nodes = (Node*)mallocc(sizeof(Node)*Capacity);
//초기화
(*Stack)->Capacity = Capacity;
(*Stack)->Top = -1;
}
//제거
void AS_DestroyStack(ArrayStack *Stack) {
free(Stack->Nodes);
free(Stack);
}
//push
void AS_Push(ArrayStack *Stack, ElementType Data) {
//최상위 노드의 인덱스에서 1을 더한 곳에
Stack->Top++;
//새 노드를 입력하도록 구성
Stack->Nodes[Stack->Top].Data = Data;
}
//pop
ElementType AS_Pop(ArrayStack *Stack) {
//최상위 노드에서 1만큼 낮춤
int Position = Stack->Top--;
//pop연산은 최상위 값을 반환하므로 리턴값 존재
return Stack->Nodes[Position].Data;
}
ElementType AS_Top(ArrayStack *Stack) {
//pop연산처럼 빼내는 것이 아니라 최상위 값만 반환
return Stack->Nodes[Stack->Top].Data;
}
int AS_GetSize(ArrayStack *Stack) {
return Stack->Top+1;
}
2. 큐
- 입력, 출력 창구가 따로 존재
- 먼저 들어간 게 먼저 나옴
- 구성: 가장 앞 요소(전단), 가장 마지막 요소(후단)
- 스택의 연산은 모두 Top에서만 이루어지지만 큐의 삽입 연산은 후단, 제거 연산은 전단에서 수행됨.
2-1. 큐의 연산
- 스택과 유사하게 삽입과 제거 연산
- Enqueue(삽입), Dequeue(제거)로 표현
2-2. 순환 큐
삽입과 제거 연산이 후단과 전단 각각 다른 위치에서 일어남 -> 전단을 제거하고 나머지 앞 요소들을 한칸식 옮겨와야 하는 비효율 발생
전단의 위치를 하나씩 밀어도 되지만, 그러면 가용 용량이 줄어듦 -> 끝과 시작을 이어버리면 해결
- 순환 큐: 시작과 끝을 연결해서 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐
- 포화 상태: 빈칸 없이 큐가 꽉찬 상태
- 공백 상태: 빈칸이 존재함
큐가 포화 상태가 아니라 공백 상태일때도 전단과 후단이 같은 위치에 있어서 구분할 필요가 있음.
-> 큐 배열 생성 시 1만큼 더 크게 만들어서 전단과 후단 사이를 비우면 됨
2-3. 구현
- CircularQueue.h
#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct tagNode {
ElementType Data;
} Node;
typedef struct tagCircularQueue {
int Capacity;
int Front;
int Real;
Node *Nodes;
} CircularQueue;
void CQ_CreateQueue(CircularQueue **Queue, int Capacity);
void CQ_DestroyQueue(CircularQueue *Queue);
void CQ_Enqueue(CircularQueue *Queue, ElementType Data);
ElementType CQ_Dequeue(CircularQueue *Queue);
int CQ_GetSize(CircularQueue *Queue);
int CQ_IsEmpty(CircularQueue *Queue);
int CQ_IsFull(CircularQueue *Queue);
- CircularQueue.c
void CQ_CreateQueue(Circular **Queue, int Capacity) {
//큐를 자유 저장소에 생성
(*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
//입력된 capacity+1 만큼의 노드를 자유 저장소에 생성
(*Queue)->Nodes = (Node*)malloc(sizeof(Node)*(Capacity+1));
(*Queue)->Capacity = Capacity;
(*Queue)->Front = 0;
(*Queue)->Rear = 0;
}
void CQ_DestroyQueue(CircularQueue *Queue) {
free(Queue->Nodes);
free(Queue);
}
void CQ_Enqueue(CircularQueue *Queue, ElementType Data) {
int Position = 0;
if (Queue->Rear == Queue->Capacity) {
Position = Queue->Rear;
Queue->Rear = 0;
}
else Position = Queue->Rear++;
Queue->Nodes[Position].Data = Dta;
}
ElementType CQ_Dequeue(CircularQueue *Queue) {
int Position = Queue->Front;
if (Queue->Front == Queue->Capacity) Queue->Front = 0;
else Queue->Front++;
return Queue->Nodes[Position].Data;
}
int CQ_GetSize(CircularQueue *Queue) {
return (Queue->Front == Queue->Rear);
}
int CQ_IsFull(CircularQueue *Queue) {
if (Queue->Front < Queue->Rear)
return (Queue->Rear - Queue->Front) == Queue->Capacity;
else
return (Queue->rear + 1) == Queue->Front;
}
'knockon' 카테고리의 다른 글
[2주차 TIL] KnockOn Bootcamp 탐색 알고리즘 (0) | 2024.08.13 |
---|---|
[2주차 TIL] KnockOn Bootcamp 정렬 알고리즘 (0) | 2024.08.13 |
[1주차 TIL] KnockOn Bootcamp 헤더파일 (0) | 2024.08.06 |
[1주차 TIL] KnockOn Bootcamp 트리 (0) | 2024.08.06 |
[1주차 TIL] KnockOn Bootcamp 연결리스트 (0) | 2024.08.06 |