[1주차 TIL] KnockOn Bootcamp 스택&&큐

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;
}