Queue

선입선출의 Data Structure인 큐를 구현하는 연습을 하기 위해 풀었다. 스택도 진행할 예정이다.

array를 활용해서 구현하기 때문에 포인터를 사용하여 메모리 사용을 조금이라도 줄이기 위해 노력했다.

rear로만 input이 들어오고 front로만 출력이 나가는 것이 큐이다.

일반적인 큐의 경우, rear가 끝에 도달하게 되면 메모리를 추가적으로 할당하여 input을 제어해야하는 상황이 발생하게 되고, 이 때 데이터를 다시 다 옮기는 과정에서 불필요한 N번의 연산을 수행하게 된다.

이를 방지하고자 heurisitc하게 만든 것이 Circular Queue이다. Modular연산을 통해 원형 큐가 작동하는 것처럼 만든 것이다.

#include <stdio.h>
#include <string.h>
#define MAX 100000 
#define True 1
#define False 0

// FIFO structure. 

typedef struct Squeue{
  int size; //큐의 크기
  int front; 
  int rear;
  int arr[MAX];
} SQUEUE;

typedef SQUEUE Queue;

void Queue_init(Queue* pq){
  pq -> front = 0;
  pq -> rear = 0;
  pq -> size = 0;
}

int Empty(Queue *pq){
  if(pq->front == pq->rear){
   return True;
  }
  else{
    return False;
  }
}

int Front(Queue *pq){
  if(Empty(pq)){
    return -1;
  }
  else{
    return pq->arr[pq->front+1];
  }
}

int Back(Queue *pq){ //rear인덱스의 큐 값 반환
  if(Empty(pq)){
    return -1;
  }
  else{
    return pq->arr[pq->rear];
  }
}

int Size(Queue *pq){
  if(Empty(pq)){
    return 0;
  }
  else{
    return pq->size;
  }
}

int Next_index(int loc){
  if(loc == MAX-1){ // End of queue, go to the front. 
    return 0;
  }
  else{
    return loc = loc + 1; // retunr next index. 
  } 
}

void Push(Queue *pq, int data){
  pq->rear = Next_index(pq->rear);
  pq->arr[pq->rear] = data;
  pq->size = pq->size+1;
}

int Pop(Queue *pq){
  if(Empty(pq)){
    return -1;
  }
  else{
    pq->size = pq->size-1;
    pq->front = Next_index(pq->front);
    int rdata = pq->arr[pq->front];
    return rdata;
  }
}

int main(void) {
  Queue q;
  Queue_init(&q);
  char array[6];
  int n;
  scanf("%d",&n);

  for(int i = 0;i<n;i++){
      scanf("%s",array);
      if(strcmp(array,"push") == 0){
          int x;
          scanf("%d",&x);
          Push(&q,x);
      }

      else if(strcmp(array,"pop") == 0){
          printf("%d\n",Pop(&q));
      }

      else if(strcmp(array,"size") == 0){
          printf("%d\n",Size(&q));
      }

      else if(strcmp(array,"empty") == 0){
          printf("%d\n",Empty(&q));
      }

      else if(strcmp(array,"front") == 0){
          printf("%d\n",Front(&q));
      }

      else if(strcmp(array,"back") == 0){
          printf("%d\n",Back(&q));
      }
  }
  return 0;
}