본문으로 바로가기

[자료구조]Queue 큐 구현(C++)

category Algorithm 2018. 7. 4. 17:30

오늘은 Queue 큐 자료구조에 대해 알아 보겠습니다.


C++에서는 표준 템플릿 라이브러리 STL(Standard Template Library) 로 큐(queue) 를 제공해 줍니다.


때문에 헤더파일에 #include<queue> 를 명시해 큐를 사용 할 수 있습니다.



하지만 STL 을 쓰지않고 직접 C++에서 큐(queue) 를 만들어 보고~ 나서 STL 의 큐 사용법에 대해 알아 보겠습니다.


큐(Queue)


먼저 큐(queue) 란, FIFO ( First In First Out ) 선입선출 기본적인 자료구조중 하나로 스택 stack - LIFO(Last In First Out) 과 형제? 입니다.


그림과같이 먼저 들어간것이 먼저나오는 형태의 자료구조 입니다.


그럼 큐를 구현하기 위해서 여러 방법이 사용되는데요, 이번 포스팅에선 배열을 이용하여 큐를 만들어 보겠습니다.


그런데, 배열을 이용하여 큐를 만드려고 하니 한가지 문제점이 있는데요,

그림처럼 처음 들어갔던 자료가 빠졌을경우 그자리가 비게되는 현상이 발생합니다.


따라서, 자료들을 이동시켜주는 작업을 해야하는 번거로움이 있습니다.


때문에 우리는 원형큐 형태로 큐를 구현 할건데요, 원형큐는 자료의 처음과 끝을 알려주는 포인터(front, rear) 가 존재해 자료의 push 와 pop 에 따라 자료의 이동없이 관리 할 수 있습니다.



원형큐


처음 비어있을때느 front 와 rear 가 0번째 인덱스를 가리킵니다.


push가 되면 rear 는 push 되는 인덱스를 가리킵니다.


pop를하여 front 의 자료를 빼내게 된다면 front 는 한칸 움직입니다.


이런식으로 자료의 이동없이 포인터로 큐를 관리 할 수 있는게 원형 큐 입니다.



이제 코드를 보며 알아보겠습니다.


queue.cpp 전체소스

결과:

front [ 3 ] rear
front [ 3 | 103 ] rear
front [ 3 | 103 | 57 ] rear
front [ 103 | 57 ] rear
front [ 103 | 57 | 22 ] rear
front [ 57 | 22 ] rear
front [ 22 ] rear
front [  ] rear
Queue is Empty
front [  ] rear
계속하려면 아무 키나 누르십시오 . . .

push, pop, empty, isFull 네가지 함수로 구성되어있는 queue 입니다.


push 는 큐에 자료를 삽입하는 함수, pop 는 front 를 한칸 옮깁니다, empty 는 큐가 비어있는지 bool 값으로 반환하는 함수, isFull 은 큐에 자료가 가득 찻는지 확인하는 함수입니다.


간단히 만들어본 큐입니다. 다음번엔 STL 에서 제공되는 큐에대해 알아보겠습니다.

'Algorithm' 카테고리의 다른 글

[자료구조]Stack 스택 구현(C++)  (1) 2018.07.05
[Algorithm]동적계획법(다이나믹 프로그래밍)  (2) 2018.06.15
[C++]별 찍기(for문)  (0) 2018.06.09