Queue Data Structure

 

 

 

 

 

 

 

 

1️⃣ Queue가 뭘까?

 

 

 

 

1. 응용프로그램에 사용되는 기본 데이터 구조

 

2. 선형 데이터 구조

 

3. FIFO 방식을 사용 (First In, First Out)

 

4. 멀티스레드 환경에서 스레드 관리에 사용될 수 있음.

 

 

에스컬레이터, 계산대, 주요소의 세차장같이 알게 모르게 실생활에서

자연스럽게 FIFO 방식을 채택하여 사용하게 됩니다. 🚋

 

 

 

 

 

 

 

 

 

 

 

 

2️⃣ FIFO 구조 이미지 

 

 

 

요소 1, 2, 3, 4, 5, 6 순서대로 들어왔으며 (In)

들어온 순서대로 먼저 나가게 됩니다. (out)

 

 

 

 

 

 

 

 

 

 

 

 

3️⃣ Queue API와 구현 방식

 

 

queue api

 

 

 

프로그래밍 언어에서 보편적으로 제공되는 Queue의 기능 3가지가 있습니다.

enqueue(삽입), dequeue(제거), peek(엑세스)

 

 

1. enqueue : queue의 제일 뒤에 요소를 하나 추가합니다.

 

 

 

 

 

 

2. dequeue : queue의 제일 앞에 요소를 하나 제거(혹은 액세스)합니다.

 

 

 

 

 

3. peek : queue의 제일 앞에 요소를 제거하지 않고, 데이터를 액세스 합니다.

 

 

 

 

 

 

 

 

 

 

프로그래밍에서 queue의 구현 방식 2가지

 

 

1. sequential allocation

 

array를 사용하는 방식입니다.

모든 요소에 대하여 index를 사용하여 접근하며

queue의 기능 "enqueue" 사용 시

"array.length - 1"개의 요소들을 shift 해야 하는 단점이 있습니다.

 

2. linked list allocation

 

node를 사용하는 방식입니다.

저는 해당 방식이 queue에서는 사람이 이해하기 직관적이라 생각하나

 

"dequeue"에서 

array를 사용하는 방식은 시간 복잡도 O(1)이 소요되나

linked list를 사용하여 구현하면 front에 접근하는데 O(n)의 시간 복잡도가

필요합니다.

 

 

 

 

 

 

 

 

4️⃣ Usage of queue data structure

 

 

 

1. cpu, disk scheduling과 같이 공유 리소스에 대한 요청 관리

2. 웹사이트 트래픽 처리

3. 키보드 같은 디바이스의 input buffer

 

 

 

 

 

queue와 개인적인 경험담

 

 

"어디서 queue의 형태가 사용되면 좋을까?"라고 생각하던 중

인턴때가 겪었던 문제가 생각이 났습니다.

 

 

 

 

끔찍했던 과거

 

다니던 회사에서 사용자들이 사용자들간에 구매, 판매기능이 있었습니다.

A사용자의 아이템을 여러 사용자가 구매할때 트랜잭션처리를

잘 못하여 아이템이 복사되고 돈이 차감되지 않는 끔찍한 일이였습니다.

transaction처리에 대하여 무지해서 오입력된 데이터에 대하여

복구하느라 애를 많이 먹었습니다.

 

포스팅을 하다보니 그때 문제에 queue를 사용하면 되지 않을까? 생각이 듭니다.

server에서는 충돌이 발생될거라고 판단되는 데이터의 접근은

모두 queue Scheduler에 요청을 하고

queue가 위임하여 DB에 요청하는 방식을 사용해도 해결 할 수 있지 않을까? 생각을 해봅니다.

 

 

 

 

 

 

 

 

 

5️⃣Queue Inheritance of Java