stacks-and-queues.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f7604a7c",
   "metadata": {
    "papermill": {
     "duration": 0.004753,
     "end_time": "2024-07-31T11:51:51.414648",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.409895",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Stacks and Queues \n",
    "\n",
    "* **Video Tutorials**: https://www.youtube.com/watch?v=vOx3vY1w4tM&list=PLKYEe2WisBTFEr6laH5bR2J19j7sl5O8R&index=6"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91653cb1",
   "metadata": {
    "papermill": {
     "duration": 0.003801,
     "end_time": "2024-07-31T11:51:51.422857",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.419056",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Stack - Last in First Out (LIFO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d96bbe02",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.432724Z",
     "iopub.status.busy": "2024-07-31T11:51:51.432353Z",
     "iopub.status.idle": "2024-07-31T11:51:51.446062Z",
     "shell.execute_reply": "2024-07-31T11:51:51.444980Z"
    },
    "papermill": {
     "duration": 0.021152,
     "end_time": "2024-07-31T11:51:51.448201",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.427049",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stk = []\n",
    "stk"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53d47912",
   "metadata": {
    "papermill": {
     "duration": 0.004062,
     "end_time": "2024-07-31T11:51:51.456576",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.452514",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Append - O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c5c652c2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.466769Z",
     "iopub.status.busy": "2024-07-31T11:51:51.466397Z",
     "iopub.status.idle": "2024-07-31T11:51:51.472950Z",
     "shell.execute_reply": "2024-07-31T11:51:51.471921Z"
    },
    "papermill": {
     "duration": 0.014094,
     "end_time": "2024-07-31T11:51:51.474960",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.460866",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stk.append(5)\n",
    "stk.append(6)\n",
    "stk"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe026fcc",
   "metadata": {
    "papermill": {
     "duration": 0.004025,
     "end_time": "2024-07-31T11:51:51.483402",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.479377",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Pop - O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e09ffb2a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.493793Z",
     "iopub.status.busy": "2024-07-31T11:51:51.492914Z",
     "iopub.status.idle": "2024-07-31T11:51:51.500210Z",
     "shell.execute_reply": "2024-07-31T11:51:51.498933Z"
    },
    "papermill": {
     "duration": 0.01502,
     "end_time": "2024-07-31T11:51:51.502573",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.487553",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[5]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = stk.pop()\n",
    "print(x)\n",
    "stk"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "460f165f",
   "metadata": {
    "papermill": {
     "duration": 0.004228,
     "end_time": "2024-07-31T11:51:51.511379",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.507151",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Top of Stack - O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7ae3603e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.521674Z",
     "iopub.status.busy": "2024-07-31T11:51:51.521275Z",
     "iopub.status.idle": "2024-07-31T11:51:51.527451Z",
     "shell.execute_reply": "2024-07-31T11:51:51.526520Z"
    },
    "papermill": {
     "duration": 0.013728,
     "end_time": "2024-07-31T11:51:51.529444",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.515716",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stk[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f85c8545",
   "metadata": {
    "papermill": {
     "duration": 0.004426,
     "end_time": "2024-07-31T11:51:51.538529",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.534103",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Queues - First in First out (FIFO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "f9b4c06b",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.549559Z",
     "iopub.status.busy": "2024-07-31T11:51:51.548799Z",
     "iopub.status.idle": "2024-07-31T11:51:51.553388Z",
     "shell.execute_reply": "2024-07-31T11:51:51.552393Z"
    },
    "papermill": {
     "duration": 0.012463,
     "end_time": "2024-07-31T11:51:51.555519",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.543056",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "37af5a70",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.566321Z",
     "iopub.status.busy": "2024-07-31T11:51:51.565971Z",
     "iopub.status.idle": "2024-07-31T11:51:51.572326Z",
     "shell.execute_reply": "2024-07-31T11:51:51.571383Z"
    },
    "papermill": {
     "duration": 0.014209,
     "end_time": "2024-07-31T11:51:51.574448",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.560239",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q = deque()\n",
    "q"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4316c457",
   "metadata": {
    "papermill": {
     "duration": 0.004475,
     "end_time": "2024-07-31T11:51:51.583699",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.579224",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Enqueue - Add element to the right - O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "dc889a98",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.594980Z",
     "iopub.status.busy": "2024-07-31T11:51:51.594130Z",
     "iopub.status.idle": "2024-07-31T11:51:51.601066Z",
     "shell.execute_reply": "2024-07-31T11:51:51.599941Z"
    },
    "papermill": {
     "duration": 0.014793,
     "end_time": "2024-07-31T11:51:51.603234",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.588441",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([3, 4, 5])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.append(3)\n",
    "q.append(4)\n",
    "q.append(5)\n",
    "q"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90be162a",
   "metadata": {
    "papermill": {
     "duration": 0.004572,
     "end_time": "2024-07-31T11:51:51.612676",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.608104",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Dequeue - Remove element from the left - O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "8ad29cf7",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.624204Z",
     "iopub.status.busy": "2024-07-31T11:51:51.623287Z",
     "iopub.status.idle": "2024-07-31T11:51:51.629682Z",
     "shell.execute_reply": "2024-07-31T11:51:51.628734Z"
    },
    "papermill": {
     "duration": 0.01438,
     "end_time": "2024-07-31T11:51:51.631746",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.617366",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.popleft()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57a77b9d",
   "metadata": {
    "papermill": {
     "duration": 0.004708,
     "end_time": "2024-07-31T11:51:51.641423",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.636715",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "### Peek from the left and right sides - O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "7f6b47ea",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-07-31T11:51:51.654660Z",
     "iopub.status.busy": "2024-07-31T11:51:51.653709Z",
     "iopub.status.idle": "2024-07-31T11:51:51.661159Z",
     "shell.execute_reply": "2024-07-31T11:51:51.659978Z"
    },
    "papermill": {
     "duration": 0.016058,
     "end_time": "2024-07-31T11:51:51.663296",
     "exception": false,
     "start_time": "2024-07-31T11:51:51.647238",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(q[0])\n",
    "q[-1]"
   ]
  }
 ],
 "metadata": {
  "kaggle": {
   "accelerator": "none",
   "dataSources": [],
   "dockerImageVersionId": 30746,
   "isGpuEnabled": false,
   "isInternetEnabled": true,
   "language": "python",
   "sourceType": "notebook"
  },
  "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.10.13"
  },
  "papermill": {
   "default_parameters": {},
   "duration": 3.291081,
   "end_time": "2024-07-31T11:51:51.987763",
   "environment_variables": {},
   "exception": null,
   "input_path": "__notebook__.ipynb",
   "output_path": "__notebook__.ipynb",
   "parameters": {},
   "start_time": "2024-07-31T11:51:48.696682",
   "version": "2.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}