삼성 SW 역량테스트 B형/Pro 대비 - C, C++ 큐 만들기

삼성 SW 역량테스트 B형/Pro 대비 - C, C++ 큐 만들기 

 

1. 큐

  큐는 First In, First Out 자료 구조로, 입력된 순서대로 출력되는 자료구조이다. 역량테스트 (Certi) B형(Pro)에서는 STL 사용이 불가능하고 최적화하는 단계가 필요하기 때문에 동적 할당 없이 전역으로 처리해야한다.

 

2. 기본 구조

함수	동작
Push	큐에 넣기(push back)
Pop	큐에서 빼기 (pop front)
Size	크기 반환
Empty	비어있는지 여부 반환

 일반적으로 Pro(B형)에서는 속도에 따른 제한을 많이 두기 때문에 활용할 수 있는 최대한의 크기를 잡고, 큐가 오버플로우 되지 않음을 가정하고 작성한다.

 

3. 소스코드

#include <cstdio>

#define Q_SIZE 5
int st, en;

typedef struct item {
  int data;
};
item queue[Q_SIZE];

inline int empty() {
  return st == en;
}
inline int size() {
  return en - st;
}
inline void push(int value) {
  if(en != Q_SIZE)
    queue[en++].data=value;
}
inline item* pop() {
  if (!empty()) return &queue[st++];
  return NULL;
}

int main() {

  item *ptr = NULL;
  for (int i = 0; i < 10; i += 2)
    push(i);
  for (int i = 0; i < 6; i++) {
    ptr = pop();
    if (ptr) printf("POP : %d\n", ptr->data);
    else printf("EMPTY!!");
  }
  // 가득차서 안들어감
  for (int i = 10; i < 20; i += 2)
    push(i);
  while (!empty()) {
    printf("%d\n", pop()->data);
  }
  getchar();
}