백준알고리즘 10845번, 큐

큐를 구현하는 문제이다. push,pop,empty,size,front,back 함수를 구현해야 한다. 배열을 이용해 구현하였다.

고려해야 할 것은 앞과 끝을 가르키는 위치를 갖고 있어야 된다는 정도이다. 정해진 배열의 크기에서 큐가 원형으로 자라나고 줄어들게 만들었다.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106


#include <stdio.h>
#include <string.h>

#define MAX_QUEUE_SIZE 100000

using namespace std;

class Queue {
private:
 unsigned int first;
 unsigned int last;
 unsigned int size;
 int queue[MAX_QUEUE_SIZE];
public:
 Queue() {
  first = 0;
  last = 0;
  size = 0;
  memset(queue, 0, sizeof queue);
 }
 int Size() {
  return size;
 }
 bool Empty() {
  return size == 0;
 }
 int Front() {
  if (size == 0)
   return -1;
  return queue[first];
 }
 int Back() {
  if (size == 0)
   return -1;
  return queue[(last-1)%MAX_QUEUE_SIZE];
 }

 void Push(int item)
 {
  size++;
  queue[last++] = item;
  if (last == MAX_QUEUE_SIZE)
   last %= MAX_QUEUE_SIZE;
 }

 int Pop() {
  if (size == 0)
   return -1;
  int temp = queue[first];
  size--;
  first++;
  if (first == MAX_QUEUE_SIZE)
   first %= MAX_QUEUE_SIZE;
  return temp;
 }
};

int main(void) {
 Queue q1;
 char sign[6] = { 0 };
 int n = 0;
 int item = 0;

#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
#endif

 scanf("%d", &n);
 for (int i = 0; i < n; i++)
 {
  scanf("%s", sign);
  if (strstr(sign, "push"))
  {
   scanf("%d", &item);
   q1.Push(item);
  }
  else if (strstr(sign, "pop"))
  {
   printf("%d\n", q1.Pop());
  }
  else if (strstr(sign, "front"))
  {
   printf("%d\n", q1.Front());
  }
  else if (strstr(sign, "back"))
  {
   printf("%d\n", q1.Back());
  }
  else if (strstr(sign, "size"))
  {
   printf("%d\n", q1.Size());
  }
  else
  {
   printf("%d\n", q1.Empty());
  }  
 }

#ifndef ONLINE_JUDGE
 fclose(stdin);
 fclose(stdout);
#endif

 return 0;
}

Contents