Circular Array Code

class CircularArray(object):

    def __init__(self, MAX_SIZE):
        self.MAX_SIZE = MAX_SIZE
        self.size = 0
        self.array = [None] * MAX_SIZE
        self.front = 0
        self.back = 0

    def push(self, value):
        """Push the value to the back of the circular array
        """
        if self.size == self.MAX_SIZE:
            raise IndexError('Array is full')
        self.array[self.back] = value
        self.back += 1
        self.size += 1

        # wrap around
        if self.back == self.MAX_SIZE:
            self.back = 0

    def pop(self):
        """Pop a value from the front of the circular array
        """
        if self.size == 0:
            raise IndexError('Array is empty')
        ret = self.array[self.front]
        self.front += 1
        self.size -= 1

        # wrap around
        if self.front == self.MAX_SIZE:
            self.front = 0
        return ret

    def print_array(self):
        print('Array: ', end = ' ')
        if self.size == 0:
            print('empty')
            return
        i = self.front
        while True:
            print(self.array[i], end = ' ')
            i += 1
            if i == self.MAX_SIZE:
                i = 0
            if i == self.back:
                print()
                break

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook was prepared by [Abhijeet Antin](https://github.com/abhijeet14antin). Source and license info is on [GitHub](https://github.com/ido777/system-design-primer-update)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Design a circular array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## Constraints and assumptions\n",
    "\n",
    "* What are we queueing?\n",
    "    * We are queueing integers\n",
    "* Can we assume inputs are valid or do we have to validate them?\n",
    "    * Assume they're valid\n",
    "* Can we assume this fits memory?\n",
    "    * Yes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting circular_array.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile circular_array.py\n",
    "\n",
    "class CircularArray(object):\n",
    "\n",
    "    def __init__(self, MAX_SIZE):\n",
    "        self.MAX_SIZE = MAX_SIZE\n",
    "        self.size = 0\n",
    "        self.array = [None] * MAX_SIZE\n",
    "        self.front = 0\n",
    "        self.back = 0\n",
    "\n",
    "    def push(self, value):\n",
    "        \"\"\"Push the value to the back of the circular array\n",
    "        \"\"\"\n",
    "        if self.size == self.MAX_SIZE:\n",
    "            raise IndexError('Array is full')\n",
    "        self.array[self.back] = value\n",
    "        self.back += 1\n",
    "        self.size += 1\n",
    "        \n",
    "        # wrap around\n",
    "        if self.back == self.MAX_SIZE:\n",
    "            self.back = 0\n",
    "\n",
    "    def pop(self):\n",
    "        \"\"\"Pop a value from the front of the circular array\n",
    "        \"\"\"\n",
    "        if self.size == 0:\n",
    "            raise IndexError('Array is empty')\n",
    "        ret = self.array[self.front]\n",
    "        self.front += 1\n",
    "        self.size -= 1\n",
    "\n",
    "        # wrap around\n",
    "        if self.front == self.MAX_SIZE:\n",
    "            self.front = 0\n",
    "        return ret\n",
    "        \n",
    "    def print_array(self):\n",
    "        print('Array: ', end = ' ')\n",
    "        if self.size == 0:\n",
    "            print('empty')\n",
    "            return\n",
    "        i = self.front\n",
    "        while True:\n",
    "            print(self.array[i], end = ' ')\n",
    "            i += 1\n",
    "            if i == self.MAX_SIZE:\n",
    "                i = 0\n",
    "            if i == self.back:\n",
    "                print()\n",
    "                break\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Array:  empty\n",
      "Array:  1 2 3 4 5 \n",
      "Array:  3 4 5 \n",
      "Array:  3 4 5 6 \n"
     ]
    }
   ],
   "source": [
    "from circular_array import CircularArray\n",
    "ca = CircularArray(5)\n",
    "ca.print_array()\n",
    "ca.push(1)\n",
    "ca.push(2)\n",
    "ca.push(3)\n",
    "ca.push(4)\n",
    "ca.push(5)\n",
    "ca.print_array()\n",
    "\n",
    "ca.pop()\n",
    "ca.pop()\n",
    "ca.print_array()\n",
    "\n",
    "ca.push(6)\n",
    "ca.print_array()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}

Comments