Circular Queue using python..!

Queue is similar to stack but it follows F.I.F.O method.

Queue can developed by using normal python list and also with linked-list.Here,Queue with linked-list is preferred because time-complexity and space-complexity is good compared to Queue with normal python list.

In Queue with python list, the enqueue and dequeue will end in worst case with increase in inputs.So,the better version of this is circular queue.

Circular Queue is used in Traffic System,Memory Management,CPU Scheduling But here with increase in data’s the time-complexity will become worst but space complexity can be reduced with fixed size.So it’s always good to implement Queue using linked list if time-complexity is preferred.

We can look into the implementation of Circular Queue in python:
Here we go,

<span>#we need Queue class to initialize fixed empty list with start and top </span><span>class</span> <span>CircularQ</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span><span>maxSize</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>maxSize</span> <span>*</span><span>[</span><span>None</span><span>]</span>
        <span>self</span><span>.</span><span>maxSize</span> <span>=</span> <span>maxSize</span>
        <span>self</span><span>.</span><span>start</span> <span>=</span> <span>-</span><span>1</span>
        <span>self</span><span>.</span><span>top</span> <span>=</span> <span>-</span><span>1</span>
    <span>def</span> <span>__str__</span><span>(</span><span>self</span><span>):</span>
        <span>return</span> <span>str</span><span>(</span><span>self</span><span>.</span><span>data</span><span>)</span>
    <span>def</span> <span>isEmpty</span><span>(</span><span>self</span><span>,</span><span>value</span><span>):</span>
        <span>if</span> <span>self</span><span>.</span><span>top</span> <span>and</span> <span>self</span><span>.</span><span>star</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
            <span>return</span> <span>True</span>
        <span>else</span><span>:</span>
            <span>return</span> <span>False</span>
    <span>def</span> <span>isFull</span><span>(</span><span>self</span><span>):</span>
        <span>if</span> <span>self</span><span>.</span><span>top</span><span>+</span><span>1</span> <span>==</span> <span>self</span><span>.</span><span>maxSize</span> <span>and</span> <span>self</span><span>.</span><span>start</span> <span>==</span> <span>0</span><span>:</span>
            <span>return</span> <span>True</span>
        <span>elif</span> <span>self</span><span>.</span><span>start</span><span>+</span><span>1</span> <span>==</span> <span>self</span><span>.</span><span>top</span><span>:</span>
            <span>return</span> <span>True</span>
        <span>else</span><span>:</span>
            <span>return</span> <span>False</span>
    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span><span>value</span><span>):</span>
        <span>self</span><span>.</span><span>top</span><span>+=</span><span>1</span>
        <span>self</span><span>.</span><span>data</span><span>[</span><span>self</span><span>.</span><span>top</span><span>]</span> <span>=</span> <span>value</span>
        <span>self</span><span>.</span><span>start</span><span>=</span><span>0</span>
    <span>def</span> <span>delete</span><span>(</span><span>self</span><span>):</span>
        <span>first</span> <span>=</span> <span>self</span><span>.</span><span>data</span><span>[</span><span>self</span><span>.</span><span>start</span><span>]</span>
        <span>start</span> <span>=</span> <span>self</span><span>.</span><span>start</span>
        <span>if</span> <span>self</span><span>.</span><span>start</span> <span>==</span> <span>self</span><span>.</span><span>top</span><span>:</span>
            <span>self</span><span>.</span><span>start</span> <span>=-</span><span>1</span>
            <span>self</span><span>.</span><span>top</span><span>=-</span><span>1</span>
        <span>elif</span> <span>self</span><span>.</span><span>start</span><span>+</span><span>1</span> <span>==</span> <span>self</span><span>.</span><span>maxSize</span><span>:</span>
            <span>self</span><span>.</span><span>start</span> <span>=</span> <span>0</span>
        <span>else</span><span>:</span>
            <span>self</span><span>.</span><span>start</span><span>+=</span><span>1</span>
        <span>self</span><span>.</span><span>data</span><span>[</span><span>start</span><span>]</span> <span>=</span> <span>None</span>
        <span>return</span> <span>first</span>
<span>circular</span> <span>=</span> <span>CircularQ</span><span>(</span><span>5</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>1</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>2</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>3</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>4</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>5</span><span>)</span>
<span>circular</span><span>.</span><span>delete</span><span>()</span>
<span>circular</span><span>.</span><span>delete</span><span>()</span>
<span>print</span><span>(</span><span>circular</span><span>)</span>
<span>#we need Queue class to initialize fixed empty list with start and top </span><span>class</span> <span>CircularQ</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span><span>maxSize</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>maxSize</span> <span>*</span><span>[</span><span>None</span><span>]</span>
        <span>self</span><span>.</span><span>maxSize</span> <span>=</span> <span>maxSize</span>
        <span>self</span><span>.</span><span>start</span> <span>=</span> <span>-</span><span>1</span>
        <span>self</span><span>.</span><span>top</span> <span>=</span> <span>-</span><span>1</span>
    <span>def</span> <span>__str__</span><span>(</span><span>self</span><span>):</span>
        <span>return</span> <span>str</span><span>(</span><span>self</span><span>.</span><span>data</span><span>)</span>

    <span>def</span> <span>isEmpty</span><span>(</span><span>self</span><span>,</span><span>value</span><span>):</span>
        <span>if</span> <span>self</span><span>.</span><span>top</span> <span>and</span> <span>self</span><span>.</span><span>star</span> <span>==</span> <span>-</span><span>1</span><span>:</span>
            <span>return</span> <span>True</span>
        <span>else</span><span>:</span>
            <span>return</span> <span>False</span>

    <span>def</span> <span>isFull</span><span>(</span><span>self</span><span>):</span>
        <span>if</span> <span>self</span><span>.</span><span>top</span><span>+</span><span>1</span> <span>==</span> <span>self</span><span>.</span><span>maxSize</span> <span>and</span> <span>self</span><span>.</span><span>start</span> <span>==</span> <span>0</span><span>:</span>
            <span>return</span> <span>True</span>
        <span>elif</span> <span>self</span><span>.</span><span>start</span><span>+</span><span>1</span> <span>==</span> <span>self</span><span>.</span><span>top</span><span>:</span>
            <span>return</span> <span>True</span>
        <span>else</span><span>:</span>
            <span>return</span> <span>False</span>

    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span><span>value</span><span>):</span>
        <span>self</span><span>.</span><span>top</span><span>+=</span><span>1</span>
        <span>self</span><span>.</span><span>data</span><span>[</span><span>self</span><span>.</span><span>top</span><span>]</span> <span>=</span> <span>value</span>
        <span>self</span><span>.</span><span>start</span><span>=</span><span>0</span>

    <span>def</span> <span>delete</span><span>(</span><span>self</span><span>):</span>
        <span>first</span> <span>=</span> <span>self</span><span>.</span><span>data</span><span>[</span><span>self</span><span>.</span><span>start</span><span>]</span>
        <span>start</span> <span>=</span> <span>self</span><span>.</span><span>start</span>

        <span>if</span> <span>self</span><span>.</span><span>start</span> <span>==</span> <span>self</span><span>.</span><span>top</span><span>:</span>
            <span>self</span><span>.</span><span>start</span> <span>=-</span><span>1</span>
            <span>self</span><span>.</span><span>top</span><span>=-</span><span>1</span>

        <span>elif</span> <span>self</span><span>.</span><span>start</span><span>+</span><span>1</span> <span>==</span> <span>self</span><span>.</span><span>maxSize</span><span>:</span>
            <span>self</span><span>.</span><span>start</span> <span>=</span> <span>0</span>

        <span>else</span><span>:</span>
            <span>self</span><span>.</span><span>start</span><span>+=</span><span>1</span>
        <span>self</span><span>.</span><span>data</span><span>[</span><span>start</span><span>]</span> <span>=</span> <span>None</span>
        <span>return</span> <span>first</span>



<span>circular</span> <span>=</span> <span>CircularQ</span><span>(</span><span>5</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>1</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>2</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>3</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>4</span><span>)</span>
<span>circular</span><span>.</span><span>insert</span><span>(</span><span>5</span><span>)</span>
<span>circular</span><span>.</span><span>delete</span><span>()</span>
<span>circular</span><span>.</span><span>delete</span><span>()</span>
<span>print</span><span>(</span><span>circular</span><span>)</span>
#we need Queue class to initialize fixed empty list with start and top class CircularQ:
    def __init__(self,maxSize):
        self.data = maxSize *[None]
        self.maxSize = maxSize
        self.start = -1
        self.top = -1
    def __str__(self):
        return str(self.data)

    def isEmpty(self,value):
        if self.top and self.star == -1:
            return True
        else:
            return False

    def isFull(self):
        if self.top+1 == self.maxSize and self.start == 0:
            return True
        elif self.start+1 == self.top:
            return True
        else:
            return False

    def insert(self,value):
        self.top+=1
        self.data[self.top] = value
        self.start=0

    def delete(self):
        first = self.data[self.start]
        start = self.start

        if self.start == self.top:
            self.start =-1
            self.top=-1

        elif self.start+1 == self.maxSize:
            self.start = 0

        else:
            self.start+=1
        self.data[start] = None
        return first



circular = CircularQ(5)
circular.insert(1)
circular.insert(2)
circular.insert(3)
circular.insert(4)
circular.insert(5)
circular.delete()
circular.delete()
print(circular)

Enter fullscreen mode Exit fullscreen mode

Thank You,
I hope everyone will have a good health and a better future…!!

You Can Support Me..

原文链接：Circular Queue using python..!