3 minute read

1. 큐

  • 스택 : 자료의 입출력이 선입선출(FIFO)의 형태로 일어나는 자료구조
  • 후단(rear) : 큐에서 삽입이 일어나는 곳
  • 전단(front) : 큐에서 삭제가 일어나는 곳

추상 자료형

데이터 : 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모임

연산 
  - init() : 큐를 초기화한다.
  - is_empty() : 큐가 비어 있으면 TRUE를 반환하고 아니면 FALSE를 반환한다.
  - is_full() : 큐가 가득 차 있으면 TRUE를 반환하고 아니면 FALSE를 반환한다.
  - size() : 큐 내의 모든 요소들의 개수를 반환한다.
  - enqueue(e) : 주어진 요소 e를 큐의 맨 위에 추가한다.
  - dequeue() : 큐 맨 요소를 삭제하고 반환한다.
  - peek() : 큐 맨 앞 요소를 삭제하지 않고 반환한다.

2. 배열을 이용한 큐의 구현

원형 큐 : 처음과 끝이 원형으로 연결되어 있는 배열 -> front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 한다.

초기 상태, 공백 상태 : front = rear

포화 상태 : front = (rear + 1) % MAX_QUEUE_SIZE

front : 큐의 첫 번째 원소의 하나 앞

rear : 마지막에 입력된 요소

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100

typedef int Element;
Element data[MAX_QUEUE_SIZE];
int front, rear;

void error(char* str)
{
    printf("%c\n", str);
    exit(1);
}

void init_queue() {front = rear = 0;}

int is_empty() {return front == rear;}

int is_full() {return front == (rear + 1) % MAX_QUEUE_SIZE;}

int size() {return (rear - front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;}

void enque(Element val)
{
    if (is_empty())
        error("포화 상태 에러");
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    data[rear] = val;
}

Element dequeue()
{
    if (is_empty())
        error("공백 상태 에러");
    front = (front + 1) % MAX_QUEUE_SIZE;
    return data[front];
}
Element peek()
{
    if(is_empty())
        error("공백 상태 에러");
    return data[(front + 1) % MAX_QUEUE_SIZE];
}

3. 연결 리스트를 이용한 큐의 구현

#include <stdio.h>
#include <stdlib.h>
typedef int Element;
typedef struct LinkedNode
{
    Element data;
    struct LinkedNode* link;
} Node;
Node* front = NULL;
Node* rear = NULL;

void error(char str[])
{
    printf("%c", str);
    exit(1);
}

void init_queue() {front = rear = 0;}

int is_empty() {return front == rear;}

int size()
{
    Node *p;
    int count = 0;
    for (p = front; p != NULL; p = p -> link) count++;
    return count;
}


void enqueue(Element e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p -> data = e;
    p -> link = NULL;

    if (is_empty()) front = rear = p;
    else {
        rear -> link = p;
        rear = p;
    }
}

Element deque()
{
    Node* p;
    Element e;
    if (is_empty())
        error("공백 상태 에러");

    p = front;
    front = front -> link;

    if(front == NULL) rear = NULL;
    e = p -> data;
    free(p);
    return e;
}

Element peek()
{
    if (is_empty())
        error("공백 상태 에러");
    return front -> data;
}
void destory_queue()
{
    while (is_empty() == 0)
        deque();
}

1. 덱

덱 : double-ended-queue, 큐의 전단과 후단 모두에서 삽입과 삭제가 가능한 큐

추상 자료형

데이터 : 전단과 후단을 통한 접근을 허용하는 요소들의 모임

연산 
  - init() : 큐를 초기화한다.
  - is_empty() : 큐가 비어 있으면 TRUE를 반환하고 아니면 FALSE를 반환한다.
  - is_full() : 큐가 가득 차 있으면 TRUE를 반환하고 아니면 FALSE를 반환한다.
  - size() : 큐 내의 모든 요소들의 개수를 반환한다.

  - add_front(e) : 주어진 요소 e를 덱의 맨 앞에 추가한다.
  - delete_front() : 전단 요소를 삭제하고 반환한다.
  - add_rear(e) : 주어진 요소 e를 덱의 맨 뒤에 추가한다.
  - delete_rear() : 후단 요소를 삭제하고 반환한다.
  - get_front : 전단 요소를 삭제하지 않고 반환한다.
  - get_rear : 후단 요소를 삭제하지 않고 반환한다.

2. 배열을 이용한 덱의 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100

typedef int Element;
Element data[MAX_QUEUE_SIZE];
int front, rear;

void error(char* str)
{
    printf("%c\n", str);
    exit(1);
}

void init_queue() {front = rear = 0;}
int is_empty() {return front == rear;}
int is_full() {return front == (rear + 1) % MAX_QUEUE_SIZE;}
int size() {return (rear - front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;}
void enque(Element val)
{
    if (is_empty())
        error("포화 상태 에러");
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    data[rear] = val;
}
Element dequeue()
{
    if (is_empty())
        error("공백 상태 에러");
    front = (front + 1) % MAX_QUEUE_SIZE;
    return data[front];
}
Element peek()
{
    if(is_empty())
        error("공백 상태 에러");
    return data[(front + 1) % MAX_QUEUE_SIZE];
}

void init_deque() {return init_queue();}

void add_rear(Element val) { enque(val);}

Element delete_front() {return dequeue();}

Element get_front() {return peek();}

void add_front(Element val)
{
    if (is_full())
        error("포화 상태 에러");
    front = (front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    data[front] = val;
}

Element delete_rear()
{
    if (is_empty())
        error("공백 상태 에러");
    rear = (rear + 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
        
}

Element get_rear()
{
    if (is_empty())
        error("포화 상태 에러");
    return data[rear];
}

You may also enjoy