1. 큐의 개념
스택이란 선입선출(FIFO - First In First Out) 형태의 자료구조이다. 가장 먼저 들어온 자료가, 가장 먼저 나가게 된다.
2. 큐의 구현
큐를 구현하는 방법은 많지만, 이 글에서는 연결 리스트로 큐을 만드는 방법만을 다룬다. 큐을 구성하는 연결 리스트의 노드 구조체는 두 개의 멤버변수를 가진다. 하나는 노드의 자료를 저장 할 변수이고, 하나는 자신 바로 다음에 저장된 노드를 가리키는 링크이다. 가장 마지막으로 저장된 노드는 자신보다 나중에 저장된 노드가 없으므로, 링크가 NULL이다.
3. 큐의 연산
1) 삽입(PUSH)
큐에서 삽입은 항상 마지막에서 일어난다. 가장 마지막에 저장된 노드의 링크를 삽입할 노드로 설정해 주기만 하면 된다.
2) 삭제(POP)
큐의 삭제는 항상 앞에서 일어난다. 맨 앞에 있는 노드를 삭제하기만 하면 된다.
4. 데크(deque)
데크는 Double-Ended Queue의 줄임말이다. 즉, 끝이 두 개라는 뜻으로 양 쪽 모두에서 push와 pop이 가능한 자료구조를 말한다.