[Data Structure] Stack vs. Queue?

filoscoderยท2019๋…„ 11์›” 23์ผ
1

Data structure

๋ชฉ๋ก ๋ณด๊ธฐ
2/2
post-thumbnail

์„ ํ˜•๊ตฌ์กฐ? (Linear Structure) ๐Ÿง

์„ ํ˜•๊ตฌ์กฐ (Linear structure)๋Š” ๋ฐ์ดํ„ฐ๋“ค์ด ์ผ๋ ฌ๋กœ ์ €์žฅ๋˜์–ด ์žˆ๋Š” ํ˜•ํƒœ๋ฅผ ๊ฐ€์ง„๋‹ค.
์ผ๋ ฌ๋กœ ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹์€ ๋ฆฌ์ŠคํŠธ์™€ ๊ฐ ๋ฐ์ดํ„ฐ๊ฐ€ ๋‹ค์Œ ๋ฐ์ดํ„ฐ์˜ ์œ„์น˜๋ฅผ ๊ฐ€์ง€๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๋‘ ๊ฐ€์ง€ ๋ฐฉ์‹์ด ์žˆ๋‹ค. ์ผ๋ ฌ๋กœ ์ญ‰ ์ €์žฅ๋˜์–ด ์žˆ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ๋ฆฌ์ŠคํŠธ์™€ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ์™ธ์— ์‚ฌ์šฉ ๋ฐฉ๋ฒ•์— ๋”ฐ๋ผ ์Šคํƒ(Stack), ํ(Queue) ๋ฐํฌ๊ฐ€ ์ถ”๊ฐ€๋œ๋‹ค.

๐Ÿ ๋ณธ ํฌ์ŠคํŒ…์—์„œ๋Š” ๊ฐ„๋‹จํ•˜๊ฒŒ Stack๊ณผ Queue ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์†Œ๊ฐœํ•˜๊ณ ์ž ํ•œ๋‹ค.

# Stack

์Šคํƒ(Stack)์€ ๋ฐ์ดํ„ฐ๊ฐ€ ์ž…๋ ฅ๋˜๋ฉด ์ž…๋ ฅ๋˜๋Š” ์ˆœ์„œ๋Œ€๋กœ ์Œ“๊ณ , ๋‚˜์ค‘์— ๋“ค์–ด์˜จ ๊ฒƒ๋ถ€ํ„ฐ ๋จผ์ € ์‚ฌ์šฉํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋‹ค.

์Šคํƒ ํ˜•ํƒœ์˜ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋ฅผ LIFO(Last In First Out)ํ˜•์ด๋ผ๊ณ  ํ•œ๋‹ค. ์Šคํƒ์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š” ๊ฒƒ์„ PUSH, ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋Š” ๊ฒƒ์„ POP์ด๋ผ๊ณ  ํ•œ๋‹ค.

  • ์Šคํƒ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ๊ตฌํ˜„์€ ๋ฐฐ์—ด(Array)๋ฅผ ์ด์šฉํ•ด๋„ ๋˜๊ณ  ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)๋ฅผ ์ด์šฉํ•ด๋„ ๋œ๋‹ค. ๐Ÿ˜‰

๐Ÿ”Ž Stack ์–ธ์ œ ์‚ฌ์šฉํ• ๊นŒ?

์Šคํƒ์€ ๋Œ€ํ‘œ์ ์œผ๋กœ ํ”„๋กœ๊ทธ๋žจ์„ ์ˆ˜ํ–‰ํ• ๋•Œ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.
Main ํ”„๋กœ๊ทธ๋žจ์—์„œ ํ•จ์ˆ˜ A๋ฅผ ํ˜ธ์ถœํ•˜๋ฉด Main ํ”„๋กœ๊ทธ๋žจ ์œ„์— ํ•จ์ˆ˜ A๊ฐ€ ์Œ“์ด๊ณ , ํ•จ์ˆ˜ A์˜ ์ˆ˜ํ–‰ ์ค‘์— ํ•จ์ˆ˜ B๊ฐ€ ํ˜ธ์ถœ๋˜๋ฉด, ํ•จ์ˆ˜ A์œ„์— ํ•จ์ˆ˜ B๊ฐ€ ์Šคํƒ์ฒ˜๋Ÿผ ์Œ“์ด๊ฒŒ ๋œ๋‹ค.
ํ•จ์ˆ˜ B์˜ ์‹คํ–‰์ด ์™„๋ฃŒ๋˜๋ฉด ํ•จ์ˆ˜ A๊ฐ€ ์‹คํ–‰๋˜๊ณ , ํ•จ์ˆ˜ A์˜ ์‹คํ–‰์ด ์™„๋ฃŒ๋˜๋ฉด ์ฃผ ํ”„๋กœ๊ทธ๋žจ์˜ ์‹คํ–‰์ด ์‹œ์ž‘๋ฉ๋‹ˆ๋‹ค (LIFO)

์กฐ๊ธˆ ๋” ํ˜„์‹ค์ ์ธ ์˜ˆ: "๋ง›์žˆ๋Š” ์ƒŒ๋“œ์œ„์น˜ ์‹์‚ฌ" ๐Ÿฅ™

  • ์š”๋ฆฌํ•˜๊ธฐ ๊ท€์ฐฎ์„ ๋•Œ๋Š” ์ง‘์— ์žˆ๋Š” ์‹๋นต+ํ–„+์น˜์ฆˆ๋กœ ๊ฐ„๋‹จํžˆ ์ƒŒ์œ„์น˜๋ฅผ ๋งŒ๋“ค๋ฉด ํŽธํ•˜๊ณ  ๋ง›๋„ ์ข‹๋‹ค.
  • ์ƒŒ๋“œ์œ„์น˜๋ฅผ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด์„œ ๋นต => ํ–„ || ์น˜์ฆˆ || ์ƒ์ถ”(?) => ๋นต ์ˆœ์„œ๋กœ ์Œ“๊ณ  ์ ‘์‹œ์— ๋†“์€๋‹ค.
  • ๋จน์„ฑ์ด ์ข‹์•„์„œ ํ•œ 5๊ฐœ๋กœ ํƒ‘์„ ์Œ“์•„ ์˜ฌ๋ฆฐ๋‹ค.
  • ์ž๋ฆฌ๋ฅผ ์žก๊ณ  ๋จน์„๋•Œ๋Š” ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰์œผ๋กœ ์˜ฌ๋ฆฐ ์ƒŒ๋“œ์œ„์น˜๋ฅผ ์ œ์ผ ๋จผ์ € ๋จน๋Š”๋‹ค.
  • ์ฆ‰, ์ œ์ผ ๋จผ์ € ๋งŒ๋“  ์ƒŒ๋“œ์œ„์น˜๋ฅผ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰์œผ๋กœ ๋จน๊ฒŒ ๋  ๊ฒƒ์ด๋‹ค.
  • ์—ฌ๊ธฐ์„œ ํ›„์ž…-์„ ์ถœ (LIFO)์ด ์ ์šฉ๋œ๋‹ค.

# Queue

ํ(Queue)๋Š” ๋ฐ์ดํ„ฐ๊ฐ€ ์ž…๋ ฅ๋˜๋ฉด ์ž…๋ ฅ๋˜๋Š” ์ˆœ์„œ๋Œ€๋กœ ์Œ“๊ณ , ๋จผ์ € ๋“ค์–ด์˜จ ๊ฒƒ๋ถ€ํ„ฐ ๋จผ์ € ์‚ฌ์šฉํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋‹ค.

ํ ํ˜•ํƒœ์˜ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋ฅผ FIFO (First In First Out)ํ˜•์ด๋ผ๊ณ  ํ•œ๋‹ค. ํ์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š” ๊ฒƒ์„ ENQUEUE, ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋Š” ๊ฒƒ์„ DEQUEUE์ด๋ผ๊ณ  ํ•œ๋‹ค.

  • ํ์˜ ๊ตฌํ˜„์€ ๋ฐฐ์—ด(Array)์„ ์ด์šฉํ•˜๊ฑฐ๋‚˜ (์ˆœํ™˜ ํ), ๋˜๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)๋ฅผ ์ด์šฉํ•ด๋„ ๋œ๋‹ค. ๐Ÿ˜‰

๐Ÿ”Ž Queue ์–ธ์ œ ์‚ฌ์šฉํ• ๊นŒ?

์ปดํ“จํ„ฐ ์•ˆ์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ˆ˜ํ–‰ ์ค‘์ธ๋ฐ, ์ƒˆ๋กœ์šด ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ˆ˜ํ–‰๋˜์–ด์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ ๊ธฐ์กด์— ์ˆ˜ํ–‰๋˜๋˜ ํ”„๋กœ์„ธ์Šค ์ค‘์—์„œ ๊ฐ€์žฅ ๋จผ์ € ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์˜จ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์•„์›ƒ๋˜๊ณ (์‹คํ–‰), ์ƒˆ๋กœ์šด ํ”„๋กœ์„ธ์Šค๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ฆฌ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ด ๊ฒฝ์šฐ์— ์šด์˜์ฒด์ œ๋Š” ํ˜„์žฌ ์ˆ˜ํ–‰ ์ค‘์ธ ํ”„๋กœ์„ธ์†Œ๋ฅผ ํ์˜ ํ˜•ํƒœ๋กœ ๊ด€๋ฆฌํ•ฉ๋‹ˆ๋‹ค.

Windows ์šด์˜์ฒด์ œ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ์ปดํ“จํ„ฐ์—์„œ ์ˆ˜ํ–‰ ์ค‘์ธ ํ”„๋กœ๊ทธ๋žจ์— ์ด๋ฒคํŠธ (๋ฒ„ํŠผ ๋ˆ„๋ฅด๊ธฐ, ์œˆ๋„์šฐ ํฌ๊ธฐ ์กฐ์ •, ๋ฉ”๋‰ด ์„ ํƒํ•˜๊ธฐ ๋“ฑ)๊ฐ€ ๋ฐœ์ƒํ•˜๋ฉด ๋ฐœ์ƒํ•œ ์ด๋ฒคํŠธ๊ฐ€ ํ์— ์ €์žฅ๋˜๊ณ , ์ˆ˜ํ–‰์ค‘์ธ ํ”„๋กœ๊ทธ๋žจ์ด ํ์— ์ €์žฅ๋œ ๊ฒƒ์„ ์•ž์—์„œ๋ถ€ํ„ฐ ์ฝ์–ด ์™€์„œ ์ฒ˜๋ฆฌํ•œ๋‹ค (์„ ์ž…์„ ์ถœ - FIFO).

์กฐ๊ธˆ ๋” ํ˜„์‹ค์ ์ธ ์˜ˆ: "์˜ํ™”๊ด€ ๋งคํ‘œ์†Œ ์ค„" ๐ŸŽฌ

  • ์˜ํ™”๊ด€์—์„œ ์˜ํ™”๋ฅผ ๋ณด๋ ค๋ฉด ํ•„์ˆ˜์ ์œผ๋กœ ์˜ํ™”ํ‘œ๋ฅผ ๊ตฌ๋งคํ•ด์•ผ ํ•œ๋‹ค.
  • ๊ทธ๋Ÿฌ๊ธฐ ์œ„ํ•ด์„œ ๋งคํ‘œ์†Œ๋กœ ํ–ฅํ•ด (๋‹ค๋ฅธ ๊ณ ๊ฐ๋“ค์ด ์žˆ๋‹ค๋ฉด),
  • ์ค„์„ ์„œ๋“  ๋ฒˆํ˜ธํ‘œ๋ฅผ ๋ฐ›์•„ ๋‚˜์˜ ์ˆœ์„œ๊ฐ€ ๋ ๋•Œ๊นŒ์ง€ (Linear structure),
  • ์ฆ‰ ์•ž์— ์žˆ๋Š” ์†๋‹˜๋ถ€ํ„ฐ ์˜ํ™”ํ‘œ๋ฅผ ๊ตฌ๋งคํ•˜๊ณ  ๋‚œ ๋’ค ๋‚˜์˜ ์ˆœ์„œ๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค.
  • ์—ฌ๊ธฐ์„œ๋„ ๋˜‘๊ฐ™์ด ์„ ์ž…-์„ ์ถœ(FIFO)๊ฐ€ ์ ์šฉ๋œ๋‹ค. ์„ ์ฐฉ์ˆœ!
profile
Never gets bored of making mistakes and wonder why is that

0๊ฐœ์˜ ๋Œ“๊ธ€