[자료구조] 큐(Queue)에 대해서 알아보자

주요 특징

1. FIFO(First-in, First-out)

더운 여름날 아마X빈에서 버블티를 사서 먹는 상상을 해보자.

 

 

빨대로 빨려 들어오는 타피오카 펄을 먹으며 우리는 큐를 생각해 낼 수 있다.

그것은 바로 선입선출의 과정을 진행하는 큐이다.

선입선출이란 우리가 빨대로 먹는 펄처럼 먼저 빨대에 들어온 녀석이 먼저 내 입에 들어온다는 법칙이다.

이 법칙은 판매업을 하는 가게에서 철칙으로 사용될 정도로 널리 사용되고 있으며 장점은 명확하다.

바로 제품의 신선도. 즉, 경우에 따라서 순환이 이루어 지지 못하는 스택과는 다르게 큐는 선착순으로 이루어진 공평한 순환을 겪게 된다.

또 다른 예시를 보면 은행을 예로 들 수 있다.

은행은 들어온 순서대로 번호표를 뽑고 기다리다가 번호 순서대로 작업을 처리하게 된다.

 

컴퓨터도 똑같다.

이런 방법이 쓰여야 하는 환경이 존재한다.

바로 운영체제가 프로세스를 처리하는 과정과 네트워크 통신시의 데이터 버퍼 같은 경우이다.

이 예시들은 글 뒤에 언급하기록 하겠다.

 

 

2. DataNode

Queue의 data node는 연결리스트 방식으로 구성되어 있다.

단일 Linked list 라고도 하는 녀석을 사용한다.

 

연결 리스트

연결 리스트란 위의 그림과 같은 구성으로 1개의 data와 1개의 링크로 구성되어 있다.

데이터 공간에 값이 들어가고 링크에는 자신의 앞에 존재하는 node의 주소 값을 갖고 있다.

이러한 방식을 Queue에서 사용을 하고 있다.

 

3. Rear & Front

큐는 연결 리스트로 이루어진 노드를 사용하며 rear와 front로 구성이 되어 있다.

 

Rear : 삽입이 이루어지는 쪽

Front : 삭제가 이루어지는 쪽

 

스택에는 1개의 top이 위치를 가리키지만 큐에서는 Enqueue(push) 할 곳을 가리키는 rear, Dequeue(pop) 할 곳을 가리키는 front가 존재한다.

rear는 마지막 노드를 가르키고 front는 가장 앞에 있는 노드를 가르킨다.

 

 

4. Push, Data 삽입

 

1. 새로운 node를 생성하여 data를 넣고 link에는 rear가 가르키는 node의 주소값이 포인터 형태로 저장된다.

 

 

 

1. rear가 가르키는 포인터값 은 새로 추가된 node의 주소로 변경된다.

 

 

이렇게 data 삽입 과정이 끝이난다.

 

 

 

5. Pop, Data 삭제(추출)

 

1. Front가 가르키고 있는 node를 추출한다.

 

 

1. 추출한 node를 가리키던 link를 갖고 있는 node의 link의 포인터 값을 지운다.

 

 

1. front가 가르키던 포인터값을 아까 link를 지운 node로 옴긴다.

 

 

rear가 가르키는 node를 시작하여 link를 따라서 탐색하면 방금 link 값을 초기화 시킨 node에까지 다다르게 된다.

그렇게되면 그 node가 현재 큐의 맨 앞을 의미한다는 뜻이므로 이 node의 주소값으로 front의 포인터 값을 수정해주면 된다.

 

 

 

활용 예시

CPU 스케줄링

프로세스 스케줄링에는 두가지 방식이 있다.

 

선점 스케줄링(Preemptive)

 

선점 스케줄링은 실행 중인 다른 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 기법이다.

종류 : RR(Round-Robin), SRT(Shortest-Remaining-Time), MLQ(MultiLevel Queue), MFQ(Multilevel Feedback Queue)

 

 

비선점 스케줄링(Nonpreemptive)

 

선점과는 반대되는 개념으로 이미 다른 프로세스가 CPU에 할당되어 있다면 CPU를 가져오지 못하게 막아둔 기법이다.

종류 : FIFO(First-In-First-Out), SJF(Shortest-Job-First), HRN(Highest Response-ratio Next)

 

종류만 보아도 알 수 있을 것이다. 다양한 Queue들이 스케줄링 방식에 사용된 다는 것을.

자세한 내용은 지금은 휴지통에 넣어둔 내 블로그 글을 통해서 알아볼 수 있다.

 

2019/07/18 - [휴지통] - [정보보안기사] 운영체제 이해 및 관리(5) - 프로세스 스케줄링

[정보보안기사] 운영체제 이해 및 관리(5) - 프로세스 스케줄링

 

네트워크 환경에서의 데이터 버퍼

네트워크 통신을 할 때에 사용하는 버퍼도 큐 방식을 사용한다.

통신에서 데이터 안정성과 효율성을 위해 만들어진 버퍼는 큐 형식으로 이루어져서 FIFO 방식의 순서처리를 진행한다.