๐งฑ ์คํ(Stack)๊ณผ ํ(Queue) ๊ธฐ๋ณธ ๊ฐ๋ ๊ณผ ํ์ฉ ์์
์คํ(Stack)๊ณผ ํ(Queue)๋ ๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ์๋ฃ๊ตฌ์กฐ๋ก ๋ ๋ค ๋ฐ์ดํฐ๋ฅผ ๋ฃ๊ณ ๊บผ๋ด๋ ๋ฐฉ์์ ๊ดํ ์๋ฃ๊ตฌ์กฐ์ด์ง๋ง ๋ฐ์ดํฐ๊ฐ ๋ค์ด๊ฐ ์์์ ๋ฐ๋ผ ๊บผ๋ด๋ ๋ฐฉ์์ด ๋ค๋ฅด๋ค. ๊ฐ๊ฐ์ ๊ธฐ๋ณธ ๊ฐ๋
๊ณผ ์ฐจ์ด์ ์ ๋ํด ์์๋ณด์.
์คํ(Stack)์ด๋?
์คํ์ โ์๋๋คโ๋ ๊ฐ๋
์ ๊ฐ์ฅ ์ ์ด์ธ๋ฆฌ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ๊ฐ์ฅ ๋์ค์ ๋ฃ์ ๋ฐ์ดํฐ๊ฐ ๊ฐ์ฅ ๋จผ์ ๋์ค๋ ๊ตฌ์กฐ๋ก์จ ํ์
์ ์ถ(LIFO, Last-In-First-Out) ๋ฐฉ์์ผ๋ก ๋์ํ๋ค.
์ฃผ์ ๊ธฐ๋ฅ
- push(item) - ์คํ์ ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ๋ค.
- pop() - ์คํ์์ ๊ฐ์ฅ ์์ ์๋ ๋ฐ์ดํฐ๋ฅผ ์ ๊ฑฐํ๊ณ ๋ฐํํ๋ค.
- peek() ๋๋ top() - ๊ฐ์ฅ ์์ ๋ฐ์ดํฐ๋ฅผ ํ์ธํ๋ค.
- isEmpty() - ์คํ์ด ๋น์ด ์๋์ง ํ์ธํ๊ณ boolean์ ๋ฐํํ๋ค.
- size() - ํ์ฌ ์คํ์ ์๋ ์์ ๊ฐ์๋ฅผ ๋ฐํํ๋ค.
๋ํ์ ์ธ ํ์ฉ ์์๋ ๋ค์๊ณผ ๊ฐ๋ค.
1. ์น ๋ธ๋ผ์ฐ์ ์ ๋ค๋ก ๊ฐ๊ธฐ ๊ธฐ๋ฅ
์ฌ์ฉ์๊ฐ ๋ฐฉ๋ฌธํ ํ์ด์ง๋ฅผ ์คํ์ ์ ์ฅํด๋๊ณ ๋ค๋ก ๊ฐ๊ธฐ๋ฅผ ๋๋ฅด๋ฉด ์ต๊ทผ ํ์ด์ง๋ถํฐ ๊บผ๋ธ๋ค.
2. ์ฌ๊ท ํจ์ ์ฒ๋ฆฌ (์ฝ ์คํ)
ํจ์๊ฐ ํธ์ถ๋ ๋๋ง๋ค ์คํ์ ์์ด๊ณ ๋ฆฌํด๋ ๋ ํ๋์ฉ ๋น ์ ธ๋์จ๋ค.
3. ๋ฌธ์์ด ๊ดํธ ์ ํจ์ฑ ๊ฒ์ฌ
์ฌ๋ ๊ดํธ๋ฅผ ์คํ์ ๋ฃ๊ณ ๋ซ๋ ๊ดํธ๊ฐ ๋์ฌ ๋๋ง๋ค ๊บผ๋ด์ ์ง์ด ๋ง๋์ง ํ์ธํ๋ค.
4. DFS(Depth-First Search, ๊น์ด ์ฐ์ ํ์)
์คํ์ ์ด์ฉํด ๊ทธ๋ํ์ ๊น์ ๋ถ๋ถ๋ถํฐ ํ์ํ๋ค.
ํ(Queue)๋?
ํ๋ ๋จผ์ ๋ค์ด์จ ๋ฐ์ดํฐ๊ฐ ๋จผ์ ๋๊ฐ๋ ๊ตฌ์กฐ๋ก ์ ์
์ ์ถ(FIFO, First-In-First-Out)๋ฐฉ์์ผ๋ก ๋์ํ๋ค.
์ฃผ์ ๊ธฐ๋ฅ
- enqueue(item) - ํ์ ๋ค์ชฝ(rear)์ ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํ๋ค.
- dequeue() - ํ์ ์์ชฝ(front)์์ ๋ฐ์ดํฐ๋ฅผ ์ ๊ฑฐํ๊ณ ๋ฐํํ๋ค.
- peek() ๋๋ front() - ๊ฐ์ฅ ์์ ์๋ ๋ฐ์ดํฐ๋ฅผ ๋ฐํํ๋ค.
- isEmpty() - ํ๊ฐ ๋น์ด ์๋์ง ํ์ธํ๊ณ boolean์ ๋ฐํํ๋ค.
size() - ํ์ฌ ํ์ ์๋ ์์ ๊ฐ์๋ฅผ ๋ฐํํ๋ค.
๋ํ์ ์ธ ํ์ฉ ์์๋ ๋ค์๊ณผ ๊ฐ๋ค.
1. ํ๋ฆฐํฐ ๋๊ธฐ์ด ์ฒ๋ฆฌ
์ธ์ ์์ฒญ์ด ๋ค์ด์จ ์์๋๋ก ๋ฌธ์๋ฅผ ์ถ๋ ฅํ๋ค. ๊ฐ์ฅ ๋จผ์ ์์ฒญํ ๋ฌธ์๊ฐ ๋จผ์ ์ฒ๋ฆฌ๋๋ค.
2. CPU ์์ ์ค์ผ์ค๋ง
์ฌ๋ฌ ๊ฐ์ ์์ ์ ์๊ฐ ์์๋๋ก ์ฒ๋ฆฌํ ๋ ํ๋ฅผ ์ด์ฉํ๋ค.
3. ์ด๋ฒคํธ ์ฒ๋ฆฌ ์์คํ
์ฌ์ฉ์ ์ด๋ฒคํธ, ๋คํธ์ํฌ ์์ฒญ ๋ฑ์ ์์ฐจ์ ์ผ๋ก ์ฒ๋ฆฌ๋๊ธฐ ๋๋ฌธ์ ํ ๊ตฌ์กฐ๊ฐ ์ ํฉํ๋ค.
4. BFS(Breadth-First Search, ๋๋น ์ฐ์ ํ์)
๊ทธ๋ํ๋ ํธ๋ฆฌ ๊ตฌ์กฐ์์ ๊ฐ๊น์ด ๋ ธ๋๋ถํฐ ํ์ํ ๋ ํ๋ฅผ ์ฌ์ฉํ๋ค.