[자료구조] 4주차 - 스택(Stack)과 큐(Queue)

Stack

원소와 그 도착한 시간을 반대순서로 저장한 리스트

원소의 추가와 제거가 탑(top)이라 불리는 한 끝에서만 일어나는 리스트

Last-In First-Out (LIFO 또는FILO)

push와 pop

스택의 자료구조

class Stack  { int size; DataType *Items; int TOP; }

스택의 연산

1. 생성 (CreateStack)

   void Stack::CreateStack( int_size ) {
       size = _size ; 
       tItem= new Datatype[size];
       TOP = 0; 
   }

2. 엠티 (IsEmpty)

   int Stack::is_Empty(  ) { return ( TOP == 0 ); }

3. 풀 (IsFull)

   int Stack::is_Full (  ) { return ( TOP == size ); }

4. 추가(Push)

   void Stack::push( Datatype DataItem) {
       Items[TOP] = DataItem; 
       TOP++; 
   }

   예외 적인 경우 : Overflow - Full인 스택에 원소를 추가하는 경우

5. 제거(Pop)

   Datatype Stack::pop( ) { 
       TOP--;
       return Items[TOP];
   }

6. 탑(Top)

   Datatype Stack::Top( ) { return Items[TOP –1]; }

스택의 모든 연산의 시간 복잡도는 O(1)

스택의 응용

• 중위 표기 수식을 후위 표기 수식으로 변환
• 미로 찾기
• 괄호 검사
• 깊이 우선 탐색

Queue

원소와 그 도착 시간을 순서로 저장한 리스트

원소의 추가와 제거가 양 끝에서 일어나는 리스트

First-In First-Out(FIFO)

큐의 자료구조

class queue{ int size; DataType *Items; int rear, front; };

큐의 연산

1. 생성(CreateQueue)

   void queue::CreateQueue( int_size ) {
       size = int_size ;
       Items = new Datatype[size];
       front = rear = -1; 
   }

2. 엠티(IsEmpty)

   intqueue::IsEmpty( ) { return (front == rear); }

3. 풀(IsFull)

   int queue::IsFull ( ) { return (rear == size-1); }

4. 추가(Enqueue)

   void queue::Enqueue( element item ) {
       if ( isFull( ) )
           printf(“Cannot add an element to a full queue);
       rear = rear + 1; 
       Items[ rear] = item;
   }

5. 제거(Dequeue)

   element queue::Dequeue( ) {
       if ( isEmpty( ) ) 
           printf(“You cannot delete from an empty queue);         front = front + 1; 
       return Items[ front];
   }

큐의 모든 연산의 시간 복잡도는 O(1)

특수한 큐

큐의 문제 점 : 큐에 빈 공간이 있어도 REAR == size이면 풀이라고 판단

• 원형 큐 : 큐의 마지막 원소와 첫 번째 원소를 연결함\

  • 장점 : 스택과 같이 무한한 추가와 제거 가능
  • 단점 : 풀과 엠티의 상태가 동일해짐
    • 큐에 저장된 원소를 나타내는 새로운 변수 count가 필요함

  void queue::Enqueue ( ) { 
      if ( isFull ( ) )
          printf(“Cannot add an element to a full queue);
      rear = (rear+1)%size; 
      Items[rear] = item;
      count++; 
  }
  
  element queue::Dequeue ( ) {
      if ( isEmptyQ ( ) ) 
          printf(“You cannot delete from an empty queue);
      count--;
      front = (front + 1)%size; 
      return Items[front];
  }

• DEQ(Doubley-Ended Queue) : En큐와 De큐가 큐의 양 끝에서 일어나는 큐

  • Enqueue_FRONT(); Enqueue_REAR();
  • Dequeue_FRONT(); Dequeue_REAR();
  • 장점 : 스택과 큐를 동시에 지원함

• 우선 순위 큐(Priority queue) : 우선 순위에 따라 원소를 추가하거나 제거하는 큐

  • 큐의 첫 번째 원소는 가장 우선 순위가 높은 원소 유지
  • 트리 형태의 구현(Heap)
  • 추가 O(n), 제거 O(n), 탑 O(1)

큐의 응용

• Josepus Problem : 다음 세번째 사람을 죽일 때, 생존자 구하기

  • 큐에 모든 인원을 넣음
  • 사는 사람은 De큐하고 다시 En큐
  • 죽는 사람은 De큐하고 다시 추가하지 않음

  //Execute <kill every k-th person> algorithm until
  //(k-1) persons remain in the queue
  int Item; 
  int turns = 0; 
  while ( myQ.Count ( ) >= k ) {
      turns++;
      Item = myQ.DeleteQ ( );
      if ( turns%k != 0 ) 
          myQ.AddQ ( Item );
  }