DataStructure - 큐(Queue), 덱(Deque)

배열(Array)

배열의 이름은 포인터의 역할을 한다.

따라서 배열의 이름을 전달하면 배열의 포인터(첫 번째 항목의 주소)가 전달되는 것이나 마찬가지이다. 따라서 배열을 함수의 파라미터로 전달할 때는 항상

이것을 염두에 두어야 한다.

배열의 이름이 포인터의 역할을 하여 배열의 주소를 함수로 전달하게 된다.

---

STL(Standard Template Library)

STL은 컨테이너(container), 반복자(iterator), 알고리즘(algorithm)이라고 하는 세 종류의 컴포넌트를 사용한다.

STL의 pop()은 객체를 반환하지 않고 단지 스택 맨 위의 요소를 삭제 만 한다.

STL에서는 top()이 맨 위의 요소를 반환한다. 이것을 ADT의 peek() 연산에 해당한다.

STL은 객체지향 기법과 일반화(generic) 프로그래밍 기법을 적용하여 만들어졌으므로 어떤 자료형에 대해서도 적용할 수 있고 대부분의  C++ 컴파일러에서 지원한다는 장점이 있다.

 

---

큐(Queue)

컴퓨터 장치들 사이에서 데이터를 주고받을 때 각 장치들 사이에 존재한는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억장치로 큐가 사용되는데, 이것을 보통 버퍼(Buffer)라고 한다.

대부분의 장치에서 발생하는 이벤트는 시간에 따라 불규칙적으로 발생한다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다. 따라서 이 둘 사이의 속도 차이를 버퍼를 사용하여 해결한다.

---

덱(Deque)

덱(deque)은 double-ended-queue 의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다.(단, 중간에 삽입하거나 삭제하는 것은 여전히 허용하지 않는다.)

덱은 스택과 큐의 연산들을 모두 가지고 있다. 예를 들면 addFront와 delereFront 연산은 스택의 push 와 pop 연산과 동일하다. 또한 addRear 연산과 deleteFront 연산은 각각 큐의 enqueue 와 dequeue 연산과 같다. 추가로 덱은 getFront, GetRear, deleteRear 연산을 가지고 있다. 덱은 스텍이나 큐에 비해 더 융통성이 많은 자료구조로 볼 수 있다. 예를 들어, 덱의 전단과 관련된 연산들만을 사용하면 스택이 된다. 또한 삽입은 후단만을 허용하고 삭제는 전단만을 사용하면 큐로 동작한다.