큐 - 개념

📌 큐란 무엇인가?

• 큐도 스택과 마찬가지로 단순한 규칙을 가지고 있는 리스트이다.

  큐는 First In First Out(FIFO) 구조로 먼저 들어간 데이터가 먼저 나오는 규칙이 있다.

먼저 들어간 것이 나중에 나오는 스택과는 반대의 특성을 가지고 있다.

큐는 운영체제에서도 쓰인다.

운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 CPU가 순서대로 꺼내서 처리한다.
이를 FIFO 스케줄링이라고 한다.

✅ 스택과 마찬가지로 연결리스트로 큐를 구현해 볼 것이다. 먼저 큐의 데이터 삽입/ 제거 과정을 알아보자

• 데이터 1, 2, 3, 4를 순서대로 삽입해보자.

• 삽입은 head로, 즉 가장 앞부분으로 했다.

🤔 1이 가장 먼저 나오려면 어디서부터 데이터를 제거해야할까?

• 가장 뒤에서 부터 데이터를 제거하면 된다.
  
• 이것이 큐의 전부 !

하지만 구현을 생각하면 약간의 문제가 있다.

• 앞서 구현한 연결리스트를 사용하면 head를 이용해 첫 번째 위치에 데이터를 삽입하는 것은 간단하다.

• 앞의 노드가 뒤의 노드를 가리키는 단방향 연결리스트다.

🤔 이런 구조면 데이터를 뒤에서 제거하기 힘들다. 왜 일까?

• 데이터 제거는 가장 뒤의 노드를 해야 하는데 가장 뒤의 노드에 접근하기 위해서는 가장 앞(head) 노드부터 순서대로 타고 가야 한다.

• O(n)의 성능이 나온다.
  

• 성능을 위해서 tail이라는 변수 하나를 더 만들어 준다.

• head는 가장 앞에 있는 노드를 가리키고, tail은 가장 뒤에 있는 노드를 가리키는 것이다.

• tail을 이용해서 데이터를 O(1)의 성능으로 제거할 수 있다.

하지만 tail 변수만 추가한다고 계속 O(1)의 성능을 가지는 것은 아니다.

• tail을 이용해서 데이터를 제거할 때 tail이 가리키던 노드는 삭제하면 그만이지만 삭제된 이전 노드를 다시 tail로 설정해줘야 한다.

• 하지만 앞서 만든 연결리스트는 다음 노드만 가리키는 단방향 연결리스트이기 때문에 tail로 이전 노드를 참조하는 것은 불가능하다.

그래서 현재 노드가 이전 노드도 가리킬 수 있는 이중연결리스트로 수정할 것이다.

• 이중연결리스트(양방향)로 이전 노드를 참조할 수 있다면 tail 변수 하나를 이용해 현재 노드를 제거하고 tail 이전 노드를 tail로 새로 할당할 수 잇게 된다.

with 그림으로 쉽게 배우는 자료구조와 알고리즘