๐Ÿงฑ ์Šคํƒ(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, ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰)
    ๊ทธ๋ž˜ํ”„๋‚˜ ํŠธ๋ฆฌ ๊ตฌ์กฐ์—์„œ ๊ฐ€๊นŒ์šด ๋…ธ๋“œ๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•  ๋•Œ ํ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. 

์žฅ์‹์šฉ ๋กœ๊ณ 
๐Ÿงฑ ์Šคํƒ(Stack)๊ณผ ํ(Queue) ๊ธฐ๋ณธ ๊ฐœ๋…๊ณผ ํ™œ์šฉ ์˜ˆ์‹œ | BlueCool