2020. 3. 10. 21:06ㆍStudy/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

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' 카테고리의 다른 글
Data Structure - Trees (1) (1) | 2020.03.11 |
---|---|
Java 프로그래밍 기초 7 (0) | 2020.03.11 |
Java 프로그래밍 기초 6 (0) | 2020.03.10 |
Data Structure - stacks (0) | 2020.03.09 |
Java 프로그래밍 기초 5 - 조건문, 반복문 (0) | 2020.03.09 |