[알고리즘] 스택과 큐 구현 및 최적화

스택

스택은 가장 최근에 삽입된 원소가 삭제되는 LIFO구조이다. 스택의 top에서 원소의 삽입과 삭제가 일어난다. 스택에서 필수적으로 지원해야 할 메서드를 보자.

​

Stack-Empty

Stack-Empty(S){
  if(S.top==-1) return 1;
  else return 0;
}

Push

Push(S, x){
  S.top++;
  S[S.top] = x;
}

Pop

Pop(S){
  S.top--;
  return S[S.top+1];
}

---

큐

큐는 가장 먼저 삽입된 원소가 먼저 삭제되는 FIFO구조이다. 큐의 front에서 삭제가 일어나고 rear에서 삽입이 일어난다.

큐를 그냥 배열로 사용하게 되면 큐가 메모리에서 마치 빙하처럼 점점 이동한다는 문제점이 생긴다. 데이터의 삽입/삭제가 반복되면 인덱스가 감소하지는 않고 증가만 하기에 배열의 앞부분을 활용할 수 없다.

 

이 문제들을 최적화 한 큐가 원형 큐이다. 선형 큐는 데이터의 삽입이 지속되면 점점 길어지고 앞부분은 사용하지 않는 반면, 원형 큐는 큐가 가득 찼을 때 데이터의 삭제 후 삽입이 다시 0번 인덱스로 돌아와서 삽입하는 방식으로 작동한다. 

 

큐에서 필수적으로 지원해야할 메서드를 보자. front에서 삭제가 일어나고 rear에서 삽입이 일어나며 둘의 초기값은 0으로 구현했다. 주의할 점은 큐가 가득 찼을 때와 큐가 비었을 때 front와 rear의 값이 똑같은 조건으로 구분하기 쉽지 않다. 따라서 원형 큐의 마지막 칸은 사용하지 않는 것으로 구현했다.

​

isEmpty

isEmpty(Q){
  if(Q.front == Q.rear) return 1;
  else return 0;
}

isFull

isFull(Q){
  if(Q.front == (Q.rear+1) % Q.size) return 1;
  else return 0;
}

enQueue

enQueue(Q, x){
  if(isFull(Q)) resize(Q);
  Q[rear] = x;
  rear = ++rear % Q.size;
}

resize 큐가 가득 차있는 상태에서 큐에 데이터를 삽입하려면 크기가 더 큰 큐를 생성하고 기존의 값을 복사한다. 

resize(Q){
  oldQ = Q;
  new Q.size = 2*oldQ.size;
  for(i =0 ~ oldQ.size-1)
    Q.enQueue(oldQ[i]);
}

deQueue

deQueue(Q){
  if(!isEmpty(Q)){
    returnVal = Q[front];
    front = ++front % Q.size();
    return returnVal;
  }
}