자료구조(큐 -개념,구현)

큐(Queue)

개념:

큐도 스택과 같이 아주 단순한 규칙을 가지고 있는 리스트입니다.

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식

Queue 구조

ex)마트 줄(계산 순서)

예시1 (FIFO)

ex)운영체제

예시2(FIFO)

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

이를 운영체제에서는 FIFO 스케줄링이라고 합니다.

 

tail변수를 주어 O(1)으로 처리 가능

 

1. 삭제 진행시 '1'부터 삭제해야 하는데 tail변수를 주어 바로 처리를 할 수있다.
2. but 마지막을  tail로 만들려면 '2'를 tail로 다시 변경해야 하는데 그 방식은 
3. 다시 처음(head)부터 타고 들어가야 한다. 결국! O(n)되므로 이중 연결리스트를 구현한다. 
4. 이중 연결리스트 를 구현하면 O(1)으로 가능 하다.

이중 연결리스트

 

---

 

구현:

 

추상자료형

• enqueue -데이터삽입
• dequeue -데이터제거
• front - 데이터참조

큐(Queue)는 연결리스트 로 구현할 수 있다. head에서 삽입하고tail에서 제거한다.