큐(queue)
큐(queue)
큐는 스택과 다르게 선입선출(FIFO), 후입후출(LILO) 의 구조를 갖는다.
큐의 구조를 간단히 그려보도록 하겠다.
|
... |
|
|
|
|
... |
|
back |
front |
이것이 기본적인 구조이다. 이해를 돕기위해 stack의 경우는 세로로 표현했고 queue는 가로로 표현하겠다.
queue의 기본적인 용어에 대해 설명을 하고 추가적으로 설명하도록 하겠다.
선입선출(FIFO) : 선입선출, 또는 후입후출이라고 하며 먼저 들어온 값이 나중에 나가거나 나중에 들어온 값이 먼저 나가는 것을 뜻하는
말로 스택에서는 중간이나 처음에 있는 값을 빼낼 수 없다. 가장 마지막에 나온 값부터 차례로 빼는 것이 가능하며 값
을 넣을 때에도 끝에만 넣을 수 있다. 이 위치를 알려주는 역할을 하는 것이 top이다.
- FIFO : First-In First-Out 을 말한다.
front : 큐의 앞을 가리키는 역할을 하며 stack의 top과 비슷한 역할을 한다. top과 다른 점이 있다면 삽입하더라도 front는 변하지 않는다.
값을 꺼내는 경우에만 한칸씩 이동하며 항상 큐의 앞을 가리킨다. head라고 말하기도 한다.
back: 큐의 뒤를 가리키는 역할을 하며 push를 하면 한칸씩 이동한다. rear나 tail이라고도 한다.
push : 현재 back이 가리키고 있는 곳 다음 위치에 값을 삽입하는 것을 말한다. full 상태인 경우 값을 넣지 못한다.(예외처리를 해주어야
함.) queue를 구현하게 되면 멤버 함수, 기능으로써 구현한다. push가 이뤄지면 back이 1 증가한다. Enqueue라고도 한다.
pop : 현재 front가 가리키고 있는 곳의 값을 가져온다. empty 상태에서는 값을 가져오지 못한다.(예외처리를 해주어야함.) push가 이루
어지면 front는 1 증가한다. Dequeue라고도 한다.
IsFull : full상태인지 체크하는 기능으로 현재 back의 값이 정해놓은 최대치보다 1작은 값과 비교한다.(인덱스이기때문에 1작은 값 비교.)
같으면 full 상태이므로 true를 반환하고 작으면 false를 반환하여 push가 가능함을 알 수 있다.
IsEmpty : empty상태인지 체크하는 기능으로 현재 front와 back의 값의 상태를 비교한다. back이 front보다 작으면(앞에 있으면) empty로
간주하고 true를 반환한다. 내부에 값이 있으면 front와 back이 같거나 back이 더 뒤에 존재한다. 이때는 false를 반환하고 pop
이 가능하다.( back과 front가 같으면 Empty인 상황으로 가정하는 방법도 있다.)
위의 내용이 기본적인 queue의 용어이다. 그럼 이제 queue에 값이 들어가는 모습을 표현하도록 하겠다.
1. push 7
|
... |
7 |
... | |||
|
|
front, back |
IsFull인지 체크를 하고 back의 뒤에 7을 넣고 back을 1 증가시킨다.
2. push 13
|
... |
7 |
13 |
... | ||
|
front |
back |
1.과 동일하게 체크하고 back의 뒤에 13을 넣고 back이 증가한다.
3. pop
|
... |
7 |
13 |
... | ||
|
7 출력. |
|
front, back |
IsEmpty를 체크하고 7이 출력되고 front가 한칸 이동한다. 7이 남아있는 것에 이해가 안갈 수도있는데 7이 남아있는 것은 중요하지 않다.
front가 이동하므로써 7은 이 queue로서는 접근할 수 없는 영역이며 이 말은 7이라는 값을 가지고 있다가 잃었다는 뜻이된다. 한마디로 pop을 하는 경우 내부에 들어있던 값을 다른 값으로 대체해서 비어있다는 표시를 하거나 따로 처리를 하지 않아도 상관이 없다는 뜻이다. 구현은 자유다.
4. pop
|
... |
7 |
13 |
... | ||
|
13 출력. |
back |
front |
3.과 마찬가지로 IsEmpty를 체크하고 13을 출력하고 front가 한칸 이동한다. 지금 이상태가 바로 Empty상태다.
그럼 선입선출의 모습을 표현해보겠다. 비어있는 큐에서 차례로 1, 2, 3, 4를 넣었다가 꺼내보겠다.
push
|
... |
1 |
2 |
3 |
4 |
... |
|
|
front |
|
|
back |
pop
|
... |
1 |
2 |
3 |
4 |
... |
|
|
back | front |
1, 2, 3, 4 출력.
차례로 들어가고 차례로 나온다. 이것이 선입선출 queue다.