let's get IT with DAVINA ๐ป
[์๋ฃ๊ตฌ์กฐ/์ ํ๊ตฌ์กฐ]ํ ๋ณธ๋ฌธ
Queue๋?
- Definition
- ์ค์ ์์ ๊ธฐ๋ค๋ฆฌ๋ค, ๋๊ธฐํ๋ ฌ
๊ฐ์ฅ ๋จผ์ ์ง์ ํ ์๋์ฐจ๊ฐ ๊ฐ์ฅ ๋จผ์ ํจ๊ฒ์ดํธ๋ฅผ ํต๊ณผํฉ๋๋ค. ๊ฐ์ฅ ๋์ค์ ์ง์ ํ ์๋์ฐจ๋ ๋จผ์ ๋์ฐฉํ ์๋์ฐจ๊ฐ ๋ชจ๋ ๋น ์ ธ๋๊ฐ๊ธฐ ์ ๊น์ง๋ ํจ๊ฒ์ดํธ๋ฅผ ๋น ์ ธ๋๊ฐ ์ ์์ต๋๋ค.
- Stack๊ณผ ๋ฐ๋๋๋ ๊ฐ๋ ์ผ๋ก, FIFO(First In First Out)/LILO(Last In Last Out)์ ํน์ง์ ๊ฐ์ง
- ํฐ์ผ์ ์ฌ๋ ค๊ณ ์ค์ ์์ ๊ธฐ๋ค๋ฆฌ๋ ๋ชจ์ต๊ณผ ํก์ฌํ ์ด ์๋ฃ๊ตฌ์กฐ๋ ์ ๋ ฅ๊ณผ ์ถ๋ ฅ์ ๋ฐฉํฅ์ด ๊ณ ์ ๋์ด ์์ผ๋ฉฐ, ๋ ๊ณณ์ผ๋ก ์ ๊ทผ์ด ๊ฐ๋ฅํฉ๋๋ค.
- Queue์ ๋ฐ์ดํฐ๋ฅผ ๋ฃ๋ ๊ฒ์ ‘enqueue’, ๋ฐ์ดํฐ๋ฅผ ๊บผ๋ด๋ ๊ฒ์ ‘dequeue’๋ผ๊ณ ํฉ๋๋ค.
- ๋ฐ์ดํฐ๊ฐ ์ ๋ ฅ๋ ์์๋๋ก ์ฒ๋ฆฌํ ๋ ์ฃผ๋ก ์ฌ์ฉ!
ํ์ ์ฑ์ง
- ์์์ ์ถ๊ฐ → O(1)
- ์์์ ์ ๊ฑฐ → O(1)
- ์ ์ผ ์/๋ค์ ์์ ํ์ธ → O(1)
- ์ ์ผ ์/๋ค๊ฐ ์๋ ๋๋จธ์ง ์์๋ค์ ํ์ธ/๋ณ๊ฒฝ์ด ์์น์ ์ผ๋ก ๋ถ๊ฐ๋ฅ
๊ตฌํ
const int MX=1000005;
int dat[MX];
int head=0, tail=0; //head๋ ๊ฐ์ฅ ์์ ์๋ ์์์ ์ธ๋ฑ์ค, tail์ ๊ฐ์ฅ ๋ค์ ์๋ ์์์ ์ธ๋ฑ์ค +1
//์ด ๋ ํ์ ํฌ๊ธฐ๋ tail-head
- Push ํจ์
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๋ฅผ ์ฌ์ฉํฉ๋๋ค. ์ด๊ฒ์ ํตํ์ด ๋ฒํผ(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]
'DEV_IN > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์๊ณ ๋ฆฌ์ฆ์ด๋? (2) | 2023.02.24 |
---|---|
์๋ฃ๊ตฌ์กฐ/๋น์ ํ๊ตฌ์กฐ/๊ทธ๋ํ (2) | 2023.02.23 |
์๋ฃ๊ตฌ์กฐ/๋น์ ํ๊ตฌ์กฐ/ํธ๋ฆฌ (0) | 2023.02.23 |
[์๋ฃ๊ตฌ์กฐ/์ ํ๊ตฌ์กฐ]์คํ (0) | 2023.02.22 |
์๋ฃ๊ตฌ์กฐ๋? (0) | 2023.02.22 |