๐Ÿ‘‰Goal

์ž๋ฃŒ๊ตฌ์กฐ ๋™์ž‘ ์›๋ฆฌ๋ฅผ ์ดํ•ด, ์žฅ๋‹จ์  ํŒŒ์•…

์ž๋ฃŒ๊ตฌ์กฐ๋ž€?

๋‹ค์–‘ํ•˜๊ณ  ์ˆ˜ ๋งŽ์€ ๋ฐ์ดํ„ฐ๋“ค์„ ์–ด๋–ป๊ฒŒ ํšจ์œจ์ ์œผ๋กœ ๊ด€๋ฆฌ ํ•  ๊ฒƒ์ธ์ง€ ํ‘œํ˜„ํ•˜๋Š” ๊ฒƒ. ex) ๋„์„œ๊ด€์—์„œ์˜ ์ฑ… ๋ถ„๋ฅ˜

์ž๋ฃŒ๊ตฌ์กฐ๋Š” ํฌ๊ฒŒ ๋‘๊ฐ€์ง€๋กœ ๋ถ„๋ฅ˜

์„ ํ˜• ๊ตฌ์กฐ(1๋Œ€1 ์ž๋ฃŒ๊ฐ„ ๊ด€๊ณ„) - Array, Stack, Queue, Dequeue, List

๋น„์„ ํ˜• ๊ตฌ์กฐ(1๋Œ€N ๋˜๋Š” N๋Œ€M์˜ ์ž๋ฃŒ๊ฐ„์˜ ๊ด€๊ณ„) - Tree, Graph, Binary Tree, Heap

๐Ÿ‘‰Stack(์Šคํƒ)

Stack์€ ํ›„์ž…์„ ์ถœ(Last In First Out: LIFO)์˜ ์ž๋ฃŒ๊ตฌ์กฐ

๋จผ์ € ์ž…๋ ฅ๋œ ๊ฐ’์ด ์ œ์ผ ๋งˆ์ง€๋ง‰์— ์ถœ๋ ฅ ๊ฐ€๋Šฅํ•œ ์ž๋ฃŒ๊ตฌ์กฐ

stack.PNG

์Šคํƒ์ด ์‹คํ–‰๋  ๋•Œ ์ถ”์ƒ์  ์ด๋ฏธ์ง€

< ๋งŒ์•ฝ Stack์— ๋ชจ๋“  ์›์†Œ๋ฅผ ์ง‘์–ด๋„ฃ์—ˆ๋‹ค๊ฐ€ ์ถœ๋ ฅํ•˜๋ฉด ์ถœ๋ ฅ๋œ ๋ฆฌ์ŠคํŠธ๋Š” ์ฒ˜์Œ ๋ฆฌ์ŠคํŠธ์˜ ์—ญ์ˆœ์ด ๋œ๋‹ค. >

Stack์˜ ๊ฒฝ์šฐ Array ๋ฉ”์„œ๋“œ์˜ Push, Pop์„ ์ƒ๊ฐํ•˜๋ฉด ์‰ฝ๋‹ค.

Stack์„ ์Œ“๋Š”๊ฒƒ์€ Push / Stack์—์„œ ๋นผ๋‚ด๋Š” ๊ฒƒ์€ Pop

Stack ๊ตฌํ˜„์‹œ ํ•„์š” ๋ณ€์ˆ˜

MAX_SIZE : Stack์˜ ์‚ฌ์ด์ฆˆ, Array : ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด์„ ๋ฐฐ์—ด, top : Stack์˜ ํฌ์ธํ„ฐ, ์ดˆ๊ธฐ๊ฐ’ = -1

top์€ ํ˜„์žฌ stack์•ˆ์— ์Œ“์—ฌ์ง„ ๋ฐ์ดํ„ฐ ์ค‘์— ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๋ฐ์ดํ„ฐ ์œ„์น˜๋ฅผ ๋œปํ•œ๋‹ค. ๋งŒ์•ฝ Stack ์•ˆ์— ์•„๋ฌด๊ฒƒ๋„ ์—†์„ ์‹œ๋ฅผ ์ƒ๊ฐํ•ด์„œ top์˜ ์ดˆ๊ธฐ๊ฐ’์„ -1๋กœ ์„ค์ •ํ•˜๊ณ , ํ•˜๋‚˜์˜ ๋ฐ์ดํ„ฐ๊ฐ€ Stack์•ˆ์— ์Œ“์ธ๋‹ค๋ฉด stack์˜ index = 0 ์ด๋ฏ€๋กœ top์˜ ๊ฐ’๋„ 0์œผ๋กœ ์„ค์ • ๋  ์ˆ˜ ์žˆ๋„๋ก ํ•œ๋‹ค.

Stack ์˜ค๋ฅ˜

stack overflow / stack underflow

์ฃผ์–ด์ง„ stack๋ฉ”๋ชจ๋ฆฌ๋ณด๋‹ค ๋ฐ์ดํ„ฐ๋ฅผ ๋” ๋„ฃ์—ˆ๊ฑฐ๋‚˜, stack์ด ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ๋น„์–ด์žˆ๋Š”๋ฐ ๊ฑฐ๊ธฐ์„œ ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋‚ด๋ ค๊ณ  ํ•  ๋•Œ ๋ฐœ์ƒํ•˜๋Š” ๋Œ€ํ‘œ์ ์ธ ์—๋Ÿฌ ex) ์žฌ๊ท€ํ•จ์ˆ˜ ๋ฌดํ•œ ํ˜ธ์ถœ์‹œ

์žฅ์ : ๊ฐ„๋‹จํ•˜๊ฒŒ ๊ตฌํ˜„ ๊ฐ€๋Šฅ ๋‹จ์  : ์Šคํƒ์˜ ํฌ๊ธฐ๊ฐ€ ๋ถˆํ™•์‹ค ํ• ๋•Œ์—๋Š” ํ™•์žฅ์‹œ ํ™•์žฅ์—ฐ์‚ฐ์ด ์˜ค๋ž˜ ๊ฑธ๋ฆฐ๋‹ค.

๐Ÿ‘‰Stack(Pseudo Code)

var stackArr = [];            // ๋นˆ๋ฐฐ์—ด ์ƒ์„ฑ
var element1 = 'air';        // ์ถ”๊ฐ€ํ•  ์š”์†Œ1
var element2 = 'fire';        // ์ถ”๊ฐ€ํ•  ์š”์†Œ2
stackArr.push(element1);    // ๋ฐฐ์—ด์— ์š”์†Œ1 ์ถ”๊ฐ€
stackArr.push(element2);    // ๋ฐฐ์—ด์— ์š”์†Œ2 ์ถ”๊ฐ€
console.log(stackArr);        //    ['air','fire'];
stackArr.pop();                // ์š”์†Œ 2๋ฒˆ์งธ ์ œ๊ฑฐ

๐Ÿ‘‰Stack(functional)

const Stack = function() {
  const someInstance = {};

  // Use an object with numeric keys to store values
  const storage = {};
  var count = 0;

  // Implement the methods below
  someInstance.push = function(value) {
    storage[count] = value;
    count++;
  };

  someInstance.pop = function() {
    if (count > 0) {
      var popValue = storage[count - 1];
      delete storage[count - 1];
      count--;
      return popValue;
    }
  };

  someInstance.size = function() {
    return count;
  };

  return someInstance;
};