[Data Structure] Stack

rememberme_jhkยท2020๋…„ 10์›” 27์ผ
0

STUDY

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

๐Ÿ•ฏStack

  • Stack์ด๋ผ๋Š” ๋‹จ์–ด์˜ ์ž์ฒด ๋œป์€ '๋”๋ฏธ'
  • ๋ท”ํŽ˜์—์„œ ์ ‘์‹œ๋ฅผ ์Œ“์„๋•Œ๋ฅผ ์ƒ์ƒํ•˜๋ฉด ๊ฐ„๋‹จํ•˜๋‹ค. ์ƒˆ๋กœ์šด ์ ‘์‹œ๋ฅผ ์Œ“์„ ๋•Œ ๋งจ ์œ„์—๋‹ค๊ฐ€ ์ ‘์‹œ๋ฅผ ์Œ“๊ณ , ์ ‘์‹œ๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ๋„ ~~(๊ตฌ์ง€ ์ˆ˜๊ณ ์Šค๋Ÿฝ๊ฒŒ ์•„๋ž˜์˜ ์ ‘์‹œ๋ฅผ ๊บผ๋‚ด์“ฐ์ง€ ์•Š๊ณ  ๋ณดํ†ต์€)~~ ๋งจ ์œ„์— ์žˆ๋Š” ์ ‘์‹œ๋ฅผ ๊ฐ€์ง€๊ณ  ๊ฐ€๋Š” ๊ฒƒ๊ณผ ๊ฐ™๋‹ค. **(๋‚˜์ค‘์— ๋“ค์–ด๊ฐ„ ๊ฒƒ์„ ๋จผ์ € ์“ด๋‹ค/ Last in First out/ LIFO/ ํ›„์ž…์„ ์ถœ) **

์ด๋ฏธ์ง€์ถœ์ฒ˜: https://en.wikipedia.org/


๐ŸงฏStack method

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

  • size
    ์Šคํƒ์˜ ํ˜„์žฌ ์š”์†Œ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜, top๊ณผ ๋™์ผ
  • push(element)
    ์š”์†Œ๋ฅผ ์Šคํƒ์˜ ์ตœ์ƒ๋‹จ์— ์ถ”๊ฐ€, ์•„๋ž˜์„œ๋ถ€ํ„ฐ ์š”์†Œ๋ฅผ ์Œ“์•„๊ฐ€๋Š” ๋ฐฉ์‹์œผ๋กœ ์š”์†Œ๊ฐ€ ํ•˜๋‚˜์”ฉ push ๋  ๋•Œ๋งˆ๋‹ค top๋„ 1์”ฉ ์ฆ๊ฐ€
  • pop
    ์Šคํƒ์˜ ์ตœ์ƒ๋‹จ์—์„œ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•˜๊ณ  ๋ฐ˜ํ™˜, ์œ„์—์„œ๋ถ€ํ„ฐ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ• ๋•Œ๋งˆ๋‹ค(pop) top๋„ 1์”ฉ ๊ฐ์†Œ

๐ŸงฏStack ํ™œ์šฉ

์ž๋ฃŒ ๊ตฌ์กฐ๋ฅผ ์™œ ๋ฐฐ์›Œ์•ผํ•˜๋Š”์ง€, ์ด๊ฑธ ๋Œ€์ฒด ์–ด๋””์— ์–ด๋–ป๊ฒŒ ์จ๋จน๋Š”๋‹ค๋Š” ๊ฒƒ์ธ์ง€ ๋‘๋ฃจ๋ญ‰์ˆ ํ•ด์„œ ์ž˜ ๋ชจ๋ฅด๊ฒ ์„ ๋•Œ๋Š” ์‹ค์ œ๋กœ ํ•ด๋‹น ์ž๋ฃŒ ๊ตฌ์กฐ๊ฐ€ ์ผ์ƒ ์ƒํ™œ์—์„œ ์–ด๋–ป๊ฒŒ ์‚ฌ์šฉ๋˜๊ณ  ์žˆ๋Š”์ง€ ์ฐพ์•„๋ดค๊ณ  ์˜ˆ์‹œ๋ฅผ ๋ณด๋ฉด ์›๋ฆฌ๊ฐ€ ์กฐ๊ธˆ ๋” ๋ช…ํ™•ํ•˜๊ฒŒ ์ดํ•ด๋๋‹ค.

์Šคํƒ์˜ ๊ฒฝ์šฐ,

  1. ์›น ๋ธŒ๋ผ์šฐ์ € ๋ฐฉ๋ฌธ๊ธฐ๋ก(๋’ค๋กœ ๊ฐ€๊ธฐ): ๊ฐ€์žฅ ๋‚˜์ค‘์— ์—ด๋ฆฐ ํŽ˜์ด์ง€๋ถ€ํ„ฐ ๋‹ค์‹œ ๋ณด์—ฌ์ค€๋‹ค.
  2. ์—ญ์ˆœ ๋ฌธ์ž์—ด ๋งŒ๋“ค๊ธฐ: ๊ฐ€์žฅ ๋‚˜์ค‘์— ์ž…๋ ฅ๋œ ๋ฌธ์ž๋ถ€ํ„ฐ ์ถœ๋ ฅํ•œ๋‹ค.
  3. ์‹คํ–‰ ์ทจ์†Œ (undo) : ๊ฐ€์žฅ ๋‚˜์ค‘์— ์‹คํ–‰๋œ ๊ฒƒ๋ถ€ํ„ฐ ์‹คํ–‰์„ ์ทจ์†Œํ•œ๋‹ค.
  4. ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ• ๊ณ„์‚ฐ
  5. ์ˆ˜์‹์˜ ๊ด„ํ˜ธ ๊ฒ€์‚ฌ (์—ฐ์‚ฐ์ž ์šฐ์„ ์ˆœ์œ„ ํ‘œํ˜„์„ ์œ„ํ•œ ๊ด„ํ˜ธ ๊ฒ€์‚ฌ)

๋“ฑ์— ์‚ฌ์šฉ๋œ๋‹ค.


๐ŸงฏStack ์˜ค๋‹ต๋…ธํŠธ

  1. ์Šคํƒ์— ๋Œ€ํ•œ ์„ค๋ช… ์ค‘ ํ‹€๋ฆฐ ๊ฒƒ์„ ๋ชจ๋‘ ๊ณ ๋ฅด๋ฉด?
    A ๋จผ์ € ๋“ค์–ด๊ฐ„๊ฒŒ ๋‚˜์ค‘์— ๋‚˜์˜ค๋Š” First In Last Out ๊ตฌ์กฐ์ด๋‹ค
    B ๋จผ์ € ๋“ค์–ด๊ฐ„๊ฒŒ ๋จผ์ € ๋‚˜์˜ค๋Š” First In First Out ๊ตฌ์กฐ์ด๋‹ค.
    C top ๋ฉ”์„œ๋“œ๋Š” ์Šคํƒ์˜ ๋งจ ์œ„์— ์žˆ๋Š” ๊ฐ’์„ ๊บผ๋‚ด๊ณ , ํ•ด๋‹น ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

    D ์Šคํƒ์— ํ• ๋‹น๋œ ๊ณต๊ฐ„์ด ๊ฝ‰ ์ฐจ๋ฉด ๋”์ด์ƒ push ํ•  ์ˆ˜ ์—†๋‹ค.
    E ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ์‹คํ–‰ํ•  ๋•Œ ์‚ฌ์šฉ๋œ๋‹ค.
  • B. ๋จผ์ € ๋“ค์–ด๊ฐ„๊ฒŒ ๋‚˜์ค‘์— ๋‚˜์˜ค๋Š” First in Last out ๊ตฌ์กฐ
  • C. top์€ ๋ฉ”์„œ๋“œ๊ฐ€ ์•„๋‹ˆ๋ผ ํฌ์ธํ„ฐ์˜ ์—ญํ• ๋กœ ์†์„ฑ(property)์— ํ•ด๋‹นํ•œ๋‹ค. ์†์„ฑ๊ณผ ๋ฉ”์†Œ๋“œ๋ฅผ ๊ตฌ๋ถ„ํ•ด์„œ ๊ธฐ์–ตํ•˜๋Š” ๊ฒƒ์ด ์•ฝ๊ฐ„ ํ—ท๊ฐˆ๋ ธ๋Š”๋ฐ ๋ฉ”๋ชจํ•ด๋‘ฌ์•ผ์ง€! ์Šคํƒ์˜ ๋งจ ์œ„์— ์žˆ๋Š” ๊ฐ’์„ ๊บผ๋‚ด๊ณ , ํ•ด๋‹น ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค๋Š” ์„ค๋ช…์€ pop ๋ฉ”์„œ๋“œ์— ๊ด€ํ•œ ๊ฒƒ์ด๋‹ค. ๋ฉ”์„œ๋“œ๋Š” size, pop, push๋งŒ ํ•ด๋‹น๋œ๋‹ค.
  • D. ์Šคํƒ์— ํ• ๋‹น๋œ ๊ณต๊ฐ„์ด ๊ฝ‰ ์ฐจ๋ฉด ๋”์ด์ƒ push ํ•  ์ˆ˜ ์—†๋‹ค. (์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ์–ธ์–ด๋Š” ์‚ด์ง ๋‹ค๋ฅด๋‹ค. ์ž๋ฃŒ ๊ตฌ์กฐ๋ผ๋Š” ๊ฐœ๋…์ ์œผ๋กœ ๋ดค์„ ๋•Œ๋Š” ์Šคํƒ์— ํ• ๋‹น๋œ ๊ณต๊ฐ„์ด ์žˆ๊ณ  ๊ทธ ๊ณต๊ฐ„์ด ๊ฐ€๋“์ฐจ๋ฉด ํ‘ธ์‹œ๋ฅผ ํ•  ์ˆ˜ ์—†๋‹ค)
  • E. ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ์‹คํ–‰ํ•  ๋•Œ๋งˆ๋‹ค ์Šคํƒ์ด ์Œ“์ธ๋‹ค.(์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ์‹คํ–‰ํ•  ๋•Œ ์‚ฌ์šฉ๋œ๋‹ค.)

์ฐธ๊ณ !

  • ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ•
    ์ปดํ“จํ„ฐ๊ฐ€ ์—ฐ์‚ฐํ•˜๊ธฐ ์‰ฌ์šด ํ‘œ๊ธฐ๋ฒ•
    ํ•˜์ง€๋งŒ ์šฐ๋ฆฌ๋Š” ์ค‘์œ„ ํ‘œ๊ธฐ๋ฒ• ์‚ฌ์šฉ (9*3) + ( 15/5) -2 ์ด๋Ÿฐ ์‹์œผ๋กœ
  • stack.peek()
    ์ œ์ผ ์ƒ๋‹จ์— ์žˆ๋Š” ์š”์†Œ๋ฅผ ์–ด๋– ํ•œ ๊ฒƒ๋„ ํ•˜์ง€ ์•Š๊ณ  ๊ทธ ๊ฐ’๋งŒ ๋ฐ˜ํ™˜ํ•ด์ฃผ๋Š” ๋ฉ”์†Œ๋“œ

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