큐

스택, 큐

• 리스트 작업은 시간과 무관하게 정의
• 스택과 큐의 작업은 시간을 기준으로 정의
• 큐는 가장 먼저 삽입된 데이터가 먼저 삭제되는 특성의 자료형을 추상화

용어

• 맨 앞 : Queue Front
• 맨 뒤 : Queue Rear
• Queue Rear에 데이터를 삽입하는 작업 : Add 
• Queue Front의 데이터를 삭제하는 작업 : Remove

	삽입	삭제	검색
ADT 리스트	Insert	Delete	Retrieve
ADT 스택	Push	Pop	GetTop
ADT 큐	Add(= Enqueue)	Remove(= Dequeue)	GetFront

작업

• Create : 새로운 큐를 만들기
• Destory : 사용되던 큐를 파기하기
• Add : 현재의 리어 바로 뒤에 새로운 데이터를 삽입하기
• Remove : 프런트에 있는 데이터를 가져오기
• GetFront : 현재 큐 프런트에 있는 데이터를 검색하기(읽기)
• IsEmpty : 현재 큐가 비어있는지 확인하기
• IsFull : 현재 큐가 꽉 차 있는지 확인하기
• GetSize : 현재 큐에 들어가 있는 데이터 개수를 알려주기

C++ 연결 리스트에 의한 큐 구현

typedef struct nodeRecord

{ int Data;                               큐 데이터를 정수 형으로 가정 

  nodeRecord* Next;                      다음 노드를 가리키는 포인터 변수 

} node;                                   노드는 구조체 타입 

typedef node* Nptr;                      Nptr 타입이 가리키는 것은 노드 타입 

const int MAX = 100; 

class queueClass

{ public: 

        queueClass( );                   생성자 함수 

        queueClass(const queueClass& Q);   복사 생성자 함수 

        ~queueClass( );                   소멸자 함수 

        void Add(int Item);               Item 값을 큐에 삽입 

        void Remove( );                   큐 프런트를 삭제, 리턴 값 없음 

        boolean IsEmpty( );              비어 있는지 확인 

        boolean IsFull( );                 꽉 차 있는지 확인 

   private: 

        Nptr Rear;                       마지막 노드를 가리키는 포인터    

} 

 

큐의 삽입 삭제

• 양 쪽 끝에서 일어남(삽입은 Rear에, 삭제는 Front에서)
• 연결 리스트의 첫 노드를 Front로, 마지막을 Rear로 간주
• 스택은 삽입 삭제 모두 한 쪽 끝에서 일어남

Rear 포인터 하나로 구현한 큐

• 원형 연결 리스트
• 첫 요소는 Rear->Next에 의해 접근 가능
• Front 포인터 하나로만 구현하면 삽입을 위해 끝까지 순회해야 함.

원형 연결리스트에 의한 큐

원형 연결 리스트 큐의 삽입

void queueClass::Add(int Item) 

{ if (! IsEmpty( ))                현재 하나 이상의 노드가 있다면 

  {   Nptr p = new node;            포인터 p가 공간의 새 노드의 시작주소를 가리키게 

      p->Data = Item;           새 노드의 데이터 필드를 채우고 

      p->Next = Rear->Next;          이 노드가 결국 마지막 노드가 될 것이니 

                                  이 노드가 현재의 Front 노드를 가리키게 

      Rear->Next = p;           현재의 마지막 노드가 새 노드를 가리키게 

      Rear = p;                   새 노드를 마지막 노드로 

  }

  else                             현재 비어있는 큐 이라면 

  {   p = new node;             포인터 p가 공간의 새 노드의 시작주소를 가리키게 

      p->Data = Item;           새 노드의 데이터 필드를 채우고 

      p->Next = p;              자기 자신을 가리키게 

      Rear = p;                   새 노드를 마지막 노드로 

  }

}

원형 연결 리스트 큐의 삭제

void queueClass::Remove( )

{ Nptr Front = Rear->Next;          편의상 Front 포인터를 별도로 생성 

  if (GetSize( ) >= 2)                    노드 두 개 이상일 때 

  {    Rear->Next = Front->Next;        마지막 노드가 두 번째 노드를 가리키게 

       delete Front;                     첫 노드가 사용하던 공간을 반납 

  }

  else if (GetSize( ) == 1)              노드 하나일 때 

  {    Rear = NULL;                    삭제하면 빈 큐가 되므로 빈 큐를 표시 

       delete Front;                     첫 노드이자 마지막 노드의 공간 반납 

  }

  else if (GetSize( ) == 0)               빈 큐에 삭제명령은 오류로 처리 

  {    cout << "Deletion on Empty Queue";  

  } 

} 

 

배열에 의한 스택/큐 배열 비교

스택, 큐

• 스택은 탑 변수
• 큐는 프런트, 리어 변수

배열에 의한 큐

삽입, 삭제

• Front 0, Rear -1로 초기화
• 삽입이면 Rear++ 한 후에 삽입
• 삭제이면 Front++

큐의 상태 판단

• Front > Rear 이면 빈 큐
• Front == Rear 이면 큐 아이템 하나

배열에 의한 큐의 표류

표류

• 연속된 삽입, 삭제에 의한 오른쪽 이동
• 왼쪽 빈 공간이 있음에도 오른쪽에서 막힘
• 대책 : 왼쪽 쉬프트
  - 삭제 될 때 마다
  - 오른쪽 끝에 막힐 때 몰아서 한번에

표류 현상

 

원형 배열

삽입

• 삽입 인덱스 : (Rear+1)%MAX

빈 큐와 꽉찬 큐 판정불가

• 인덱스로 봐서는 둘 다 동일 조건
• Front = Rear+1

별도의 Count 변수 유지

• 삽입 시 Count ++
• 삭제 시 Count --

큐 응용 예 - 회문 판정(회문 : 앞에서 읽으나 뒤에서 읽으나 동일한 단어, 문자열 ex) 토마토, 기러기)

Q.Create( ); S.Create( );                 큐와 스택을 생성 

for (i = 0; i < stringLength( ); i++)     문자열 끝까지 

{    Read Character into C;               하나씩 읽어서 변수 C에 저장 

     Q.Add(C); S.Push(C);                 큐에 삽입, 스택에 삽입 

} 

Matched = TRUE:                         매칭된 것으로 초기화 

while (!IsEmpty( ) && Matched)        비어 있지 않고, 미스매치 되지 않는 동안 

{    if (Q.GetFront( ) = = S.GetTop( ))   큐 프런트와 스택 탑이 일치하면 

     { Q.Remove( ); S.Pop( );             각각 삭제

     } 

    else Matched = FALSE;                일치하지 않으면 빠져나감 

} 

return MatchedSoFar;                     비어서 빠져나오면 TRUE를 리턴 

} 

 

큐 응용 예 - 시공유 시스템의 일괄처리 작업

• 사용자 ID 별로 우선순위를 분류
• queueType MultiQueue[MaxPriority]; 이면 우선순위 별로 MultiQueue[0], MultiQueue[1], MultiQueue[2]를 형성
• 배치 잡이 제출되면, 운영체제 중 디스패처(Dispatcher)는 사용자 ID를 기준으로 해당 큐에 삽입
• 먼저 실행 중이던 잡이 끝나면, 운영체제 중 스케줄러(Job Scheduler)는 사용자 ID를 기준으로 해당 큐에서 삭제

너비 우선 탐색(BFS : Breadth First Search)

• 깊이 보다는 폭을 취함
• A-B-G-C-E-H-D-F
• A에서 거리 1인 노드, 다시 각각으로부터 거리 1인 노드, ...

너비우선 탐색을 위한 큐

• 시작 노드를 삽입
• 삭제와 동시에 인접 노드를 삽입
• 소모적 탐색
• 한 번 간 노드는 다시 안감

덱(DEQUE : Double Ended Queue)

• 키보드 입력버퍼, 화면 스크롤
• 양쪽에서 삽입, 삭제의 필요성이 존재

키보드 입력

화면 스크롤

• AddLast( ), AddFirst( ), RemoveLast( ), RemoveFirst( )
• 큐 : RemoveFirest( ), AddLast( )만을 사용
• 스택 : RemoveLast( ), AddLast( )만을 사용
• 덱이 일반 클래스(General Class)라면
• 큐나 스택은 특수 클래스(Special Class, Adaptor Class)

원형배열 덱

• 양쪽에서 삽입 삭제 : 두 개의 포인터를 유지하는 것이 유리
• 고정된 한 쪽 끝에서 Add 나 Remove가 일어나면 쉬프트 필요
• 프런트 삭제 시에 Front ++; 에 의해 프런트가 전진
• 프런트 삽입 시에 Front --; 에 의해 프런트가 후진

원형 배열 덱