Chapter06-스택-live.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 꼭 알아둬야 할 자료 구조: 스택 (Stack)\n",
    "* 데이터를 제한적으로 접근할 수 있는 구조\n",
    "  - 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조\n",
    "* 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조\n",
    "  - 큐: FIFO 정책\n",
    "  - 스택: LIFO 정책"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. 스택 구조\n",
    "* 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름\n",
    "  - LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책\n",
    "  - FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책\n",
    "\n",
    "* 대표적인 스택의 활용\n",
    "  - 컴퓨터 내부의 프로세스 구조의 함수 동작 방식\n",
    "\n",
    "* 주요 기능\n",
    "  - push(): 데이터를 스택에 넣기\n",
    "  - pop(): 데이터를 스택에서 꺼내기\n",
    "  \n",
    "* <font color='#BF360C'>Visualgo 사이트에서 시연해보며 이해하기 (push/pop 만 클릭해보며): https://visualgo.net/en/list\n",
    "<br>\n",
    "<img src=\"http://www.fun-coding.org/00_Images/stack.png\" />\n",
    "\n",
    "> 엑셀로 이해해보기"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. 스택 구조와 프로세스 스택\n",
    "- 스택 구조는 프로세스 실행 구조의 가장 기본\n",
    "  - 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해 필요\n",
    "  \n",
    "> 엑셀로 이해해보기"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 재귀 함수\n",
    "def recursive(data):\n",
    "    if data < 0:\n",
    "        print (\"ended\")\n",
    "    else:\n",
    "        print(data)\n",
    "        recursive(data - 1)\n",
    "        print(\"returned\", data)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n",
      "ended\n",
      "returned 0\n",
      "returned 1\n",
      "returned 2\n",
      "returned 3\n",
      "returned 4\n"
     ]
    }
   ],
   "source": [
    "recursive(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. 자료 구조 스택의 장단점\n",
    "- 장점\n",
    "  - 구조가 단순해서, 구현이 쉽다.\n",
    "  - 데이터 저장/읽기 속도가 빠르다.\n",
    "- 단점 (일반적인 스택 구현시) \n",
    "  - 데이터 최대 갯수를 미리 정해야 한다. \n",
    "    - 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함\n",
    "  - 저장 공간의 낭비가 발생할 수 있음\n",
    "    - 미리 최대 갯수만큼 저장 공간을 확보해야 함\n",
    "\n",
    "> 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적임.\n",
    "> 이 경우, 위에서 열거한 단점이 있을 수 있음"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. 파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기\n",
    "* append(push), pop 메서드 제공"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_stack = list()\n",
    "\n",
    "data_stack.append(1)\n",
    "data_stack.append(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data_stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data_stack.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. 프로그래밍 연습 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "<strong><font color=\"blue\" size=\"3em\">연습1: 리스트 변수로 스택을 다루는 pop, push 기능 구현해보기 (pop, push 함수 사용하지 않고 직접 구현해보기)</font></strong><br>\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "stack_list = list()\n",
    "\n",
    "def push(data):\n",
    "    stack_list.append(data)\n",
    "\n",
    "def pop():\n",
    "    data = stack_list[-1]\n",
    "    del stack_list[-1]\n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "for index in range(10):\n",
    "    push(index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 쉬어가기: [stacks are everywhere](https://youtu.be/I--rJx8cpMY)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "nbTranslate": {
   "displayLangs": [
    "*"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": true,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}