7. Circular Double Ended Queue using Doubly Linked List

Circular Double ended Queue using Doubly Linked List¶

In [1]:

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
    
    def __repr__(self):
        return "<Node: %s>" % self.data

class Node: def __init__(self, data): self.data = data self.prev = None self.next = None def __repr__(self): return "" % self.data

In [2]:

Node(10)

Node(10)

Out[2]:

<Node: 10>

In [3]:

class CircularDequeue:

    def __init__(self, k: int):
        self.capacity = k
        self.front = None
        self.rear = None
        self.count = 0
    
    def __repr__(self):
        nodes = []
        ptr = self.front
        cycle = 0
        first = True
        
        while ptr:
            if ptr == self.front:
                if cycle >= 1:
                    break
                if first:
                    cycle += 1
                first = False
                nodes.append("[Front: %s]" % ptr.data)
            elif ptr == self.rear:
                nodes.append("[Rear: %s]" % ptr.data)
            else:
                nodes.append("[%s]" % ptr.data)
            ptr = ptr.next
            
        return "<-".join(nodes)
    
    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        
        node = Node(value)
        
        if self.front == self.rear == None:
            self.front = self.rear = node
            node.prev = node
            node.next = node
            
        else:
            node.prev = self.rear
            node.next = self.front
            self.front.prev = node
            self.rear.next = node
            self.front = node
            
        self.count += 1
    
        return True
    
    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        
        node = Node(value)
        
        if self.front == self.rear == None:
            self.front = self.rear = node
            node.next = node
            node.prev = node
        else:
            node.prev = self.rear
            node.next = self.front
            self.rear.next = node
            self.front.prev = node
            self.rear = node
        
        self.count += 1
        
        return True
        
    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        
        temp = self.front
        data = self.front.data
        
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
            self.front.prev = self.rear
            self.rear.next = self.front
        
        self.count -= 1
        del temp
        return True
        

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        
        temp = self.rear
        data = self.rear.data
        
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.rear = self.rear.prev
            self.rear.next = self.front
            self.front.prev = self.rear
        
        self.count -= 1
        del temp
        return True
    
    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.front.data

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.rear.data

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.capacity

class CircularDequeue: def __init__(self, k: int): self.capacity = k self.front = None self.rear = None self.count = 0 def __repr__(self): nodes = [] ptr = self.front cycle = 0 first = True while ptr: if ptr == self.front: if cycle >= 1: break if first: cycle += 1 first = False nodes.append("[Front: %s]" % ptr.data) elif ptr == self.rear: nodes.append("[Rear: %s]" % ptr.data) else: nodes.append("[%s]" % ptr.data) ptr = ptr.next return "<-".join(nodes) def insertFront(self, value: int) -> bool: if self.isFull(): return False node = Node(value) if self.front == self.rear == None: self.front = self.rear = node node.prev = node node.next = node else: node.prev = self.rear node.next = self.front self.front.prev = node self.rear.next = node self.front = node self.count += 1 return True def insertLast(self, value: int) -> bool: if self.isFull(): return False node = Node(value) if self.front == self.rear == None: self.front = self.rear = node node.next = node node.prev = node else: node.prev = self.rear node.next = self.front self.rear.next = node self.front.prev = node self.rear = node self.count += 1 return True def deleteFront(self) -> bool: if self.isEmpty(): return False temp = self.front data = self.front.data if self.front == self.rear: self.front = self.rear = None else: self.front = self.front.next self.front.prev = self.rear self.rear.next = self.front self.count -= 1 del temp return True def deleteLast(self) -> bool: if self.isEmpty(): return False temp = self.rear data = self.rear.data if self.front == self.rear: self.front = self.rear = None else: self.rear = self.rear.prev self.rear.next = self.front self.front.prev = self.rear self.count -= 1 del temp return True def getFront(self) -> int: if self.isEmpty(): return -1 return self.front.data def getRear(self) -> int: if self.isEmpty(): return -1 return self.rear.data def isEmpty(self) -> bool: return self.count == 0 def isFull(self) -> bool: return self.count == self.capacity

In [4]:

queue = CircularDequeue(4)

for i in range(10):
    print(queue.insertFront(i))

queue = CircularDequeue(4) for i in range(10): print(queue.insertFront(i))

True
True
True
True
False
False
False
False
False
False

In [5]:

queue

queue

Out[5]:

[Front: 3]<-[2]<-[1]<-[Rear: 0]

In [6]:

for _ in range(10):
    print(queue.deleteLast())

for _ in range(10): print(queue.deleteLast())

True
True
True
True
False
False
False
False
False
False

In [7]:

queue = CircularDequeue(4)

for i in range(10):
    print(queue.insertLast(i))

queue = CircularDequeue(4) for i in range(10): print(queue.insertLast(i))

True
True
True
True
False
False
False
False
False
False

In [8]:

queue

queue

Out[8]:

[Front: 0]<-[1]<-[2]<-[Rear: 3]

In [9]:

for _ in range(10):
    print(queue.deleteFront())

for _ in range(10): print(queue.deleteFront())

True
True
True
True
False
False
False
False
False
False

In [10]:

queue

queue

Out[10]:

In [11]:

myCircularDeque = CircularDequeue(3);

print(myCircularDeque.insertLast(1)) # return True

print(myCircularDeque.insertLast(2)) # return True

print(myCircularDeque.insertFront(3)) # return True

print(myCircularDeque.insertFront(4)) # return False, the queue is full.

print(myCircularDeque.getRear())     # return 2

print(myCircularDeque.isFull())     # return True

print(myCircularDeque.deleteLast())   # return True

print(myCircularDeque.insertFront(4)) # return True

print(myCircularDeque.getFront())     # return 4

myCircularDeque = CircularDequeue(3); print(myCircularDeque.insertLast(1)) # return True print(myCircularDeque.insertLast(2)) # return True print(myCircularDeque.insertFront(3)) # return True print(myCircularDeque.insertFront(4)) # return False, the queue is full. print(myCircularDeque.getRear()) # return 2 print(myCircularDeque.isFull()) # return True print(myCircularDeque.deleteLast()) # return True print(myCircularDeque.insertFront(4)) # return True print(myCircularDeque.getFront()) # return 4

True
True
True
False
2
True
True
True
4

In [12]:

myCircularDeque

myCircularDeque

Out[12]:

[Front: 4]<-[3]<-[Rear: 1]

In [13]:

queue = CircularDequeue(3)
print(queue.insertLast(1))
print(queue.insertLast(2))
print(queue.insertFront(3))
print(queue.insertFront(4))

queue = CircularDequeue(3) print(queue.insertLast(1)) print(queue.insertLast(2)) print(queue.insertFront(3)) print(queue.insertFront(4))

True
True
True
False

In [ ]: