let's get IT with DAVINA ๐Ÿ’ป

[์ž๋ฃŒ๊ตฌ์กฐ/์„ ํ˜•๊ตฌ์กฐ]ํ ๋ณธ๋ฌธ

DEV_IN/Algorithm

[์ž๋ฃŒ๊ตฌ์กฐ/์„ ํ˜•๊ตฌ์กฐ]ํ

๋‹ค๋นˆ์น˜์ฝ”๋“œ๐Ÿ’Ž 2023. 2. 22. 21:58

Queue๋ž€?

  • Definition
    • ์ค„์„ ์„œ์„œ ๊ธฐ๋‹ค๋ฆฌ๋‹ค, ๋Œ€๊ธฐํ–‰๋ ฌ

ํ†จ๊ฒŒ์ดํŠธ๋Š” Queue ์ž๋ฃŒ๊ตฌ์กฐ / ์ž๋™์ฐจ๋Š” Data

๊ฐ€์žฅ ๋จผ์ € ์ง„์ž…ํ•œ ์ž๋™์ฐจ๊ฐ€ ๊ฐ€์žฅ ๋จผ์ € ํ†จ๊ฒŒ์ดํŠธ๋ฅผ ํ†ต๊ณผํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€์žฅ ๋‚˜์ค‘์— ์ง„์ž…ํ•œ ์ž๋™์ฐจ๋Š” ๋จผ์ € ๋„์ฐฉํ•œ ์ž๋™์ฐจ๊ฐ€ ๋ชจ๋‘ ๋น ์ ธ๋‚˜๊ฐ€๊ธฐ ์ „๊นŒ์ง€๋Š” ํ†จ๊ฒŒ์ดํŠธ๋ฅผ ๋น ์ ธ๋‚˜๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

  • Stack๊ณผ ๋ฐ˜๋Œ€๋˜๋Š” ๊ฐœ๋…์œผ๋กœ, FIFO(First In First Out)/LILO(Last In Last Out)์˜ ํŠน์ง•์„ ๊ฐ€์ง
  • ํ‹ฐ์ผ“์„ ์‚ฌ๋ ค๊ณ  ์ค„์„ ์„œ์„œ ๊ธฐ๋‹ค๋ฆฌ๋Š” ๋ชจ์Šต๊ณผ ํก์‚ฌํ•œ ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์ž…๋ ฅ๊ณผ ์ถœ๋ ฅ์˜ ๋ฐฉํ–ฅ์ด ๊ณ ์ •๋˜์–ด ์žˆ์œผ๋ฉฐ, ๋‘ ๊ณณ์œผ๋กœ ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
  • Queue์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š” ๊ฒƒ์„ ‘enqueue’, ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋‚ด๋Š” ๊ฒƒ์„ ‘dequeue’๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
  • ๋ฐ์ดํ„ฐ๊ฐ€ ์ž…๋ ฅ๋œ ์ˆœ์„œ๋Œ€๋กœ ์ฒ˜๋ฆฌํ•  ๋•Œ ์ฃผ๋กœ ์‚ฌ์šฉ!

ํ์˜ ์„ฑ์งˆ

  1. ์›์†Œ์˜ ์ถ”๊ฐ€ → O(1)
  2. ์›์†Œ์˜ ์ œ๊ฑฐ → O(1)
  3. ์ œ์ผ ์•ž/๋’ค์˜ ์›์†Œ ํ™•์ธ → O(1)
  4. ์ œ์ผ ์•ž/๋’ค๊ฐ€ ์•„๋‹Œ ๋‚˜๋จธ์ง€ ์›์†Œ๋“ค์˜ ํ™•์ธ/๋ณ€๊ฒฝ์ด ์›์น™์ ์œผ๋กœ ๋ถˆ๊ฐ€๋Šฅ

๊ตฌํ˜„

const int MX=1000005;
int dat[MX];
int head=0, tail=0; //head๋Š” ๊ฐ€์žฅ ์•ž์— ์žˆ๋Š” ์›์†Œ์˜ ์ธ๋ฑ์Šค, tail์€ ๊ฐ€์žฅ ๋’ค์— ์žˆ๋Š” ์›์†Œ์˜ ์ธ๋ฑ์Šค +1
//์ด ๋•Œ ํ์˜ ํฌ๊ธฐ๋Š” tail-head
  • Push ํ•จ์ˆ˜

front()๋Š” ์ œ์ผ ์•ž์— ์œ„์น˜ํ•œ ์›์†Œ ๋ฐ˜ํ™˜, back()์€ ์ œ์ผ ๋’ค์— ์œ„์น˜ํ•œ ์›์†Œ ๋ฐ˜ํ™˜

 


Queue์˜ ํŠน์ง•

  • FIFO (First In First Out)
    • ๋จผ์ € ๋“ค์–ด๊ฐ„ ๋ฐ์ดํ„ฐ๊ฐ€ ์ œ์ผ ์ฒ˜์Œ์— ๋‚˜์˜ค๋Š” ์„ ์ž…์„ ์ถœ์˜ ๊ตฌ์กฐ
์˜ˆ1) 1, 2, 3, 4๋ฅผ ํ์— ์ฐจ๋ก€๋Œ€๋กœ ๋„ฃ์Šต๋‹ˆ๋‹ค.

						queue.enqueue(๋ฐ์ดํ„ฐ)
์ถœ๋ ฅ ๋ฐฉํ–ฅ <---------------------------< ์ž…๋ ฅ ๋ฐฉํ–ฅ
			 1 <- 2 <- 3 <- 4
๋“ค์–ด๊ฐ„ ์ˆœ์„œ๋Œ€๋กœ, 1๋ฒˆ์ด ์ œ์ผ ๋จผ์ € ๋“ค์–ด๊ฐ€๊ณ  4๋ฒˆ์ด ๋งˆ์ง€๋ง‰์œผ๋กœ ๋“ค์–ด๊ฐ€๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

์˜ˆ2) ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๋ฐ์ดํ„ฐ๋ฅผ ์ „๋ถ€ ๋นผ๋ƒ…๋‹ˆ๋‹ค.

						queue.dequeue(๋ฐ์ดํ„ฐ)
์ถœ๋ ฅ ๋ฐฉํ–ฅ <---------------------------< ์ž…๋ ฅ ๋ฐฉํ–ฅ
		1, 2, 3, 4
์ œ์ผ ์ฒซ ๋ฒˆ์งธ ์žˆ๋Š” ๋ฐ์ดํ„ฐ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ๋‚˜์˜ค๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
  • ๋ฐ์ดํ„ฐ๋Š” ํ•˜๋‚˜์”ฉ ๋„ฃ๊ณ  ๋บ„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • Queue ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ์•„๋ฌด๋ฆฌ ๋งŽ์ด ์žˆ์–ด๋„ ํ•˜๋‚˜์”ฉ ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ  & ๋บ๋‹ˆ๋‹ค.
    • ํ•œ๊บผ๋ฒˆ์— ์—ฌ๋Ÿฌ ๊ฐœ๋ฅผ ๋„ฃ๊ฑฐ๋‚˜ ๋บ„ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.
  • ๋‘ ๊ฐœ์˜ ์ž…์ถœ๋ ฅ ๋ฐฉํ–ฅ์„ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.
    • Queue ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฐ์ดํ„ฐ์˜ ์ž…๋ ฅ, ์ถœ๋ ฅ ๋ฐฉํ–ฅ์ด ๋‹ค๋ฆ…๋‹ˆ๋‹ค.
    • ๋งŒ์•ฝ ์ž…์ถœ๋ ฅ ๋ฐฉํ–ฅ์ด ๊ฐ™๋‹ค๋ฉด Queue ์ž๋ฃŒ๊ตฌ์กฐ๋ผ๊ณ  ๋ณผ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

Queue์˜ ์‹ค์‚ฌ์šฉ ์˜ˆ์ œ

์ปดํ“จํ„ฐ์™€ ์—ฐ๊ฒฐ๋œ ํ”„๋ฆฐํ„ฐ์—์„œ ์—ฌ๋Ÿฌ ๋ฌธ์„œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ธ์‡„ํ•  ๋•Œ
1. ์šฐ๋ฆฌ๊ฐ€ ๋ฌธ์„œ๋ฅผ ์ž‘์„ฑํ•˜๊ณ  ์ถœ๋ ฅ ๋ฒ„ํŠผ์„ ๋ˆ„๋ฅด๋ฉด ํ•ด๋‹น ๋ฌธ์„œ๋Š” ์ธ์‡„ ์ž‘์—…(์ž„์‹œ ๊ธฐ์–ต ์žฅ์น˜์˜) Queue์— ๋“ค์–ด๊ฐ‘๋‹ˆ๋‹ค.
2. ํ”„๋ฆฐํ„ฐ๋Š” ์ธ์‡„ ์ž‘์—… Queue์— ๋“ค์–ด์˜จ ๋ฌธ์„œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ธ์‡„ํ•ฉ๋‹ˆ๋‹ค.

์ปดํ“จํ„ฐ(์ถœ๋ ฅ ๋ฒ„ํŠผ) - (์ž„์‹œ ๊ธฐ์–ต ์žฅ์น˜์˜)Queue์— ํ•˜๋‚˜์”ฉ ๋“ค์–ด์˜ด - Queue์— ๋“ค์–ด์˜จ ๋ฌธ์„œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ธ์‡„

์ปดํ“จํ„ฐ ์žฅ์น˜๋“ค ์‚ฌ์ด์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ฃผ๊ณ ๋ฐ›์„ ๋•Œ, ๊ฐ ์žฅ์น˜ ์‚ฌ์ด์— ์กด์žฌํ•˜๋Š” ์†๋„์˜ ์ฐจ์ด๋‚˜ ์‹œ๊ฐ„ ์ฐจ์ด๋ฅผ ๊ทน๋ณตํ•˜๊ธฐ ์œ„ํ•ด ์ž„์‹œ ๊ธฐ์–ต ์žฅ์น˜์˜ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ Queue๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ์ด๊ฒƒ์„ ํ†ตํ‹€์–ด ๋ฒ„ํผ(buffer)๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.


Buffering (๋ฒ„ํผ๋ง)

๋Œ€๋ถ€๋ถ„์˜ ์ปดํ“จํ„ฐ ์žฅ์น˜์—์„œ ๋ฐœ์ƒํ•˜๋Š” ์ด๋ฒคํŠธ๋Š” ํŒŒ๋™ ๊ทธ๋ž˜ํ”„์™€ ๊ฐ™์ด ๋ถˆ๊ทœ์น™์ ์œผ๋กœ ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค.

์ด์— ๋น„ํ•ด CPU์™€ ๊ฐ™์ด ๋ฐœ์ƒํ•œ ์ด๋ฒคํŠธ๋ฅผ ์ฒ˜๋ฆฌํ•˜๋Š” ์žฅ์น˜๋Š” ์ผ์ •ํ•œ ์ฒ˜๋ฆฌ ์†๋„๋ฅผ ๊ฐ–์Šต๋‹ˆ๋‹ค.

๋ถˆ๊ทœ์น™์ ์œผ๋กœ ๋ฐœ์ƒํ•œ ์ด๋ฒคํŠธ๋ฅผ ๊ทœ์น™์ ์œผ๋กœ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ๋ฒ„ํผ(buffer)๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.

์ปดํ“จํ„ฐ์™€ ํ”„๋ฆฐํ„ฐ ์‚ฌ์ด์˜ ๋ฐ์ดํ„ฐ(data) ํ†ต์‹ ์„ ์ •๋ฆฌํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
- ์ผ๋ฐ˜์ ์œผ๋กœ ํ”„๋ฆฐํ„ฐ๋Š” ์†๋„๊ฐ€ ๋Š๋ฆฝ๋‹ˆ๋‹ค.
- CPU๋Š” ํ”„๋ฆฐํ„ฐ์™€ ๋น„๊ตํ•˜์—ฌ, ๋ฐ์ดํ„ฐ๋ฅผ ์ฒ˜๋ฆฌํ•˜๋Š” ์†๋„๊ฐ€ ๋น ๋ฆ…๋‹ˆ๋‹ค.
- ๋”ฐ๋ผ์„œ, CPU๋Š” ๋น ๋ฅธ ์†๋„๋กœ ์ธ์‡„์— ํ•„์š”ํ•œ ๋ฐ์ดํ„ฐ(data)๋ฅผ ๋งŒ๋“  ๋‹ค์Œ, ์ธ์‡„ ์ž‘์—… Queue์— ์ €์žฅํ•˜๊ณ  ๋‹ค๋ฅธ ์ž‘์—…์„ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค.
- ํ”„๋ฆฐํ„ฐ๋Š” ์ธ์‡„ ์ž‘์—… Queue์—์„œ ๋ฐ์ดํ„ฐ(data)๋ฅผ ๋ฐ›์•„ ์ผ์ •ํ•œ ์†๋„๋กœ ์ธ์‡„ํ•ฉ๋‹ˆ๋‹ค.

์œ ํŠœ๋ธŒ์™€ ๊ฐ™์€ ๋™์˜์ƒ ์ŠคํŠธ๋ฆฌ๋ฐ ์•ฑ์„ ํ†ตํ•ด ๋™์˜์ƒ์„ ์‹œ์ฒญํ•  ๋•Œ, ๋‹ค์šด๋กœ๋“œ ๋œ ๋ฐ์ดํ„ฐ(data)๊ฐ€ ์˜์ƒ์„ ์žฌ์ƒํ•˜๊ธฐ์— ์ถฉ๋ถ„ํ•˜์ง€ ์•Š์€ ๊ฒฝ์šฐ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ๋™์˜์ƒ์„ ์ •์ƒ์ ์œผ๋กœ ์žฌ์ƒํ•˜๊ธฐ ์œ„ํ•ด Queue์— ๋ชจ์•„ ๋‘์—ˆ๋‹ค๊ฐ€ ๋™์˜์ƒ์„ ์žฌ์ƒํ•˜๊ธฐ์— ์ถฉ๋ถ„ํ•œ ์–‘์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ๋ชจ์˜€์„ ๋•Œ ๋™์˜์ƒ์„ ์žฌ์ƒํ•ฉ๋‹ˆ๋‹ค.


Using Queue as JavaScript Array

// const array = new Array() ๋ฏธ๋ฆฌ ์ •์˜๋œ Array ๊ฐ์ฒด๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.
const queue = [];

queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]
queue.push(4); // [1, 2, 3, 4]
queue.push(5); // [1, 2, 3, 4, 5]

console.log(queue); // [1, 2, 3, 4, 5]

queue.shift(); // [2, 3, 4, 5]
queue.shift(); // [3, 4, 5]

console.log(queue); // [3, 4, 5]
Comments