Data Sturcture - Queue

2020. 3. 10. 21:06Study/Computer Science

1. Queue ADT란?

-   지난번에 알아본 Stack ADT와 비슷하게, arbitrary objects를 저장함

 

-   하지만 FILO였던 Stack과는 다르게 FIFO (First in first out 형식) 

 

주요 Queue Operation

enqueue(object) : 기존 Queue의 끝에 새로운 객체를 추가

 

dequeue() : 맨 앞의 객체 제거

 

부가적 Queue Operation

front() : Stack의 top()과 비슷하게 맨 앞의 요소를 제거하지 않고 리턴(object)

 

size() : Stack과 마찬가지로 저장된 요소의 수 리턴(integer)

 

empty() : 역시 마찬가지로 텅 빈지 여부 리턴(boolean)

 

예외 처리는

QueueEmpty를 throw

 

Queue Operation 실행 예시

2. Queue의 활용

직접적 활용

   - 웨이팅 순번

   - 공유된 리소스에 접근 (ex. 프린터)

   - 멀티프로그래밍 ( 프로세서가 입출력  응답 대기할동안 다른 프로그램 수행시킬 수 있도록 하는 것)

 

간접적 활용

   - 부가적 알고리즘을 위한 자료 구조

   - 다른 자료 구조의 Component

 

The STL Queue (The Standard Template Library Queue)

C++에서 기본적으로 제공하는 라이브러리 템플릿, 아래와 같이 include해서

#include <queue>
using std::queue; // 이거랑 #include <queue>랑 무슨 차이인지 모르겠음
queue<float> myQueue;

 아래와 같은 메소드(함수)를 사용가능


size() : queue에 저장된 요소들의 갯수를 return

empty() : queue가 empty면 true 그렇지 않으면 flase return

push(e) : 기존 queue 맨 뒤에 e를 enqueue

pop() : 기존 queue 맨 앞의 요소를 dequeue

front() : queue 맨 앞의 요소 return

back() : queue 맨 뒤의 요소 return


C++  Queue Interface

마찬가지로 STL Queue같은 built - in 된 queue가 아니라 직접 구현한 Data Structure

(그냥 거기서 거기고 보통 STL 씀)

 

Simple Array-Based Implementation

Queue를 배열로 구현하기 위해서는 세 가지 변수가 필요

 

f : 첫번째 요소의 인덱스

r : 마지막 요소의 인덱스

n : queue에 있는 요소의 개수

 

이 셋을 이용하면 Queue의 각 메소드는 다음과 같은 알고리즘으로 표현가능하다.

 

1. size() 와 empty() 함수

2. enqueue(o) 함수와 dequeue()함수

'Study > Computer Science' 카테고리의 다른 글