C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)

자, 지난 포스트에서 구현한 링크드 리스트를 기반으로 큐, 스택을 만들어보자. 링크드 리스트에서 대부분 구현이 되었기 때문에 설명할 내용은 많이 없다. 큐와 스택 둘 다 순회는 지원하지 않을 것이며 검색도 지원하지 않고 삽입과 삭제에 대한 것만이 존재한다.

 

https://pronist.tistory.com/76

C언어로 자료구조 만들기 - 링크드 리스트(Linked List)

큐(Queue)

큐는 FIFO(First In First Out) 구조를 가지며 가장 먼저 삽입된 데이터가 나올 때도 가장 먼저 나온다. 이 점이 큐의 가장 핵심이다. 우리가 게임에서 큐를 돌린다고 할 때, 먼저 큐에 진입한 플레이어가 매칭이 먼저 잡히는 것과 마찬가지다.

 

Queue

큐의 구현에서는 링크드 리스트에서 구현한 함수를 그대로 사용한다.

#include "List.h"

typedef struct __Queue__ {
  /**
   * @private
   */
  List _ls
} Queue;

Queue queue(size_t size, ...);

/**
 * Create Queue
 *
 * @public
 */
Queue queue(size_t size, ...) {
  List ls = list(0);
  Queue qu = { ._ls = ls };
  va_list ap;
  va_start(ap, size);
  for (int i = 0; i < size; i++) {
    ls_push_back(&qu._ls, va_arg(ap, void*));
  }
  va_end(ap);
  return qu;
}

qu_*

큐에서 구현할 함수는 매우 적으며, 구현 자체도 한 두줄이면 끝난다. 다만 큐의 특성에 따라 사용하는 함수를 잘 보아야한다. 가장 먼저 삽입된 데이터가 가장 먼저 나온다는 사실을 다시 한 번 기억하자.

void  qu_push(Queue*, void*);
void  qu_pop(Queue*);

void  qu_clear(Queue*);

Node* qu_front(Queue*);
Node* qu_rear(Queue*);

qu_push(Queue*, void*), qu_pop(Queue*)

큐에는 front, rear 포인터가 존재하는데, 구현에서 명시적으로 나타내지는 않았다, 그러나 링크드 리스트를 사용하여 구현 할 때 이것이 어떻게 연결되는 지는 알아야 한다. 큐를 초기화할 때 ls_push_back() 이었으므로 링크드 리스트의 가장 끝에 최신 데이터가 존재한다. 따라서 큐에 새로운 값을 넣을 때도 ls_push_back() 으로 사용한다. 즉, 큐의 rear 포인터는 링크드 리스트의 back 에 대응한다.

 

링크드 리스트를 기반으로 하였기에 일반적인 큐의 개념도와 다를 수 있다.

/**
 * Push new node at Back
 *
 * @public
 */
void qu_push(Queue* queue, void* element) {
  ls_push_back(&queue->_ls, element);
}

/**
 * Remove node at Front
 *
 * @public
 */
void qu_pop(Queue* queue) {
  ls_pop_front(&queue->_ls);
}

값을 삭제할 때 가장 먼저 들어온 값을 제거해야 한다. ls_pop_back() 은 가장 나중에 들어온 값을 의미하므로 ls_pop_front() 를 사용하며 가장 먼저들어온 값을 제거한다.

 

qu_clear(Queue*)

이 함수는 큐 내부에 있는 링크드 리스트를 날린다.

/**
 * Clear Queue
 *
 * @public
 */
void qu_clear(Queue* queue) {
  ls_clear(&queue->_ls);
}

qu_front(Queue*), qu_rear(Queue*)

이 함수는 큐에서 가장 먼저 들어온 포인터인 front, 가장 나중에 들어온 포인터인 rear 값을 반환한다. 각각 링크드 리스트에서 ls_begin(), ls_end() 에 대응한다.

/**
 * Get front element
 *
 * @public
 */
Node* qu_front(Queue* queue) {
  return ls_begin(&queue->_ls);
}

/**
 * Get rear element
 *
 * @public
 */
Node* qu_rear(Queue* queue) {
  return ls_end(&queue->_ls);
}

어떻게 사용해볼까?

큐의 특성을 잘 확인해서 반환 값을 예상해야 한다.

Queue qu = queue(1, "Hello, world!");
qu_push(&qu, "Who are you?");
qu_push(&qu, "Goodbye");

// GoodBye
printf("%s", (const char*)qu_rear(&qu)->element);
// Hello, world!
printf("%s", (const char*)qu_front(&qu)->element);

// Remove "Hello, world" Node
qu_pop(&qu);

// Who are you?
printf("%s", (const char*)qu_front(&qu)->element);

스택(Stack)

스택은 큐와는 다르게 동작한다. FILO(First In Last Out), 가장 먼저 들어온 것이 제일 나중에 나간다. 즉, 스택은 차곡 차곡 쌓이는 구조라고 볼 수 있다.

 

Stack

링크드 리스트를 기반으로 하므로 마찬가지로 ls_push_back() 을 쓰자.

#include "List.h"

typedef struct __Stack__ {
  /**
   * @private
   */
  List _ls
} Stack;

Stack stack(size_t size, ...);

/**
 * Create Stack
 *
 * @public
 */
Stack stack(size_t size, ...) {
  List ls = list(0);
  Stack st = { ._ls = ls };
  va_list ap;
  va_start(ap, size);
  for (int i = 0; i < size; i++) {
    ls_push_back(&st._ls, va_arg(ap, void*));
  }
  va_end(ap);
  return st;
}

st_*

스택은 큐 보다도 제공하는 함수가 적다. 사실 그렇게 많은 것이 필요없기 때문이다.

void  st_push(Stack*, void*);
void  st_pop(Stack*);

void  st_clear(Stack*);

Node* st_top(Stack*);

st_push(Stack*, void*), st_pop(Stack*)

스택에는 top, bottom 포인터가 존재하며, 링크드 리스트에서 top 은 back 에 해당하도록 하였다. top 은 가장 나중에 추가된 데이터가 있는 곳이므로, ls_pop_back() 을 사용하면 스택에서 값을 의도에 맞게 제거할 수 있다.

 

/**
 * Push new node at Back
 *
 * @public
 */
void st_push(Stack* stack, void* element) {
  ls_push_back(&stack->_ls, element);
}

/**
 * Remove node at Back
 *
 * @public
 */
void st_pop(Stack* stack) {
  ls_pop_back(&stack->_ls);
}

st_clear(Stack*)

큐와 구현이 똑같아서 생략할까 하지만 내용이 짧아서 넣기로 했다.

/**
 * Clear Stack
 *
 * @public
 */
void st_clear(Stack* stack) {
  ls_clear(&stack->_ls);
}

st_top(Stack*)

스택은 top, bottom 포인터 두 개가 존재하지만, 사실상 bottom 포인터에 큰 의미를 둘 필요는 없다. 중요한건 top 이다.

/**
 * Get top element
 *
 * @public
 */
Node* st_top(Stack* stack) {
  return ls_end(&stack->_ls);
}

어떻게 사용해볼까?

큐와의 차이점을 잘 살펴야 한다. 출력결과는 차이가 없을지언정 여러 번의 실험이 필요하다.

Stack st = stack(1, "Hello, world!");
st_push(&st, "Who are you?");
st_push(&st, "Goodbye");

// GoodBye
printf("%s", (const char*)st_top(&st)->element);

// Remove "GoodBye" Node
st_pop(&st);

// Who are you?
printf("%s", (const char*)st_top(&st)->element);

더 읽을거리

C언어로 자료구조 만들기 - 트리(BST, Binary Search Tree)

C언어로 자료구조 만들기 - 링크드 리스트(Linked List)

C언어로 자료구조 만들기 - 정적 배열(Fixed Array), 데크(Deque)