4. Double Ended Queue using Doubly Linked List

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 [13]:

class Dequeue:
    def __init__(self, max_size):
        self.capacity = max_size
        self.front = None
        self.rear = None
        self.count = 0
    
    def __len__(self):
        return self.count
    
    def __repr__(self):
        nodes = []
        ptr = self.front
        
        while ptr:
            if ptr == self.front:
                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 __iter__(self):
        pass
    
    def is_empty(self):
        return self.count == 0
    
    def is_full(self):
        return self.count == self.capacity
    
    def enqueue(self, data, position):
        if self.is_full():
            print("Dequeue is full, nothing to queue")
            return
        
        if isinstance(position, str):
            if position == "front":
                node = Node(data)
                if self.front == self.rear == None:
                    print("Inserting first item in the dequeue")
                    print(f"Inserting: {data} in the dequeue from front")
                    self.front = self.rear = node
                    
                else:
                    print(f"Inserting: {data} in the dequeue from front")
                    node.next = self.front
                    self.front.prev = node
                    self.front = node
                    
                self.count += 1
                
            elif position == "rear":
                node = Node(data)
                if self.front == self.rear == None:
                    print("Inserting first item in the dequeue")
                    print(f"Inserting: {data} in the dequeue from front")
                    self.front = self.rear = node
                    
                else:
                    print(f"Inserting: {data} at the rear of dequeue")
                    self.rear.next = node
                    node.prev = self.rear
                    self.rear = node
                    
                self.count += 1
            else:
                print("Incorrect string. Enter either 'front' or 'rear' to enqueue")
                return
        else:
            print("Not a string. Enter either front or rear to enqeue")
            return
        
    
    def dequeue(self, position):
        if self.is_empty():
            print("Dequeue is empty, nothing to dequeue")
            return
        
        if isinstance(position, str):
            if position == "front":
                data = self.front.data
                temp = self.front
                print(f"Removing: {data} from front of the dequeue")
                
                if self.front == self.rear:
                    self.front = self.rear = None
                else:
                    self.front = self.front.next
                    self.front.prev = None
                
                self.count -= 1
                del temp
                
            elif position == "rear":
                
                temp = self.rear
                data = self.rear.data
                print(f"Removing: {data} from rear of the dequeue")
                
                if self.front == self.rear:
                    self.front = self.rear = None
                else:
                    self.rear = self.rear.prev
                    self.rear.next = None
                
                self.count -= 1
                del temp
            else:
                print("Incorrect string. Enter either 'front' or 'rear' to enqueue")
                return
        else:
            print("Not a string. Enter either front or rear to enqeue")
            return

class Dequeue: def __init__(self, max_size): self.capacity = max_size self.front = None self.rear = None self.count = 0 def __len__(self): return self.count def __repr__(self): nodes = [] ptr = self.front while ptr: if ptr == self.front: 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 __iter__(self): pass def is_empty(self): return self.count == 0 def is_full(self): return self.count == self.capacity def enqueue(self, data, position): if self.is_full(): print("Dequeue is full, nothing to queue") return if isinstance(position, str): if position == "front": node = Node(data) if self.front == self.rear == None: print("Inserting first item in the dequeue") print(f"Inserting: {data} in the dequeue from front") self.front = self.rear = node else: print(f"Inserting: {data} in the dequeue from front") node.next = self.front self.front.prev = node self.front = node self.count += 1 elif position == "rear": node = Node(data) if self.front == self.rear == None: print("Inserting first item in the dequeue") print(f"Inserting: {data} in the dequeue from front") self.front = self.rear = node else: print(f"Inserting: {data} at the rear of dequeue") self.rear.next = node node.prev = self.rear self.rear = node self.count += 1 else: print("Incorrect string. Enter either 'front' or 'rear' to enqueue") return else: print("Not a string. Enter either front or rear to enqeue") return def dequeue(self, position): if self.is_empty(): print("Dequeue is empty, nothing to dequeue") return if isinstance(position, str): if position == "front": data = self.front.data temp = self.front print(f"Removing: {data} from front of the dequeue") if self.front == self.rear: self.front = self.rear = None else: self.front = self.front.next self.front.prev = None self.count -= 1 del temp elif position == "rear": temp = self.rear data = self.rear.data print(f"Removing: {data} from rear of the dequeue") if self.front == self.rear: self.front = self.rear = None else: self.rear = self.rear.prev self.rear.next = None self.count -= 1 del temp else: print("Incorrect string. Enter either 'front' or 'rear' to enqueue") return else: print("Not a string. Enter either front or rear to enqeue") return

insert at rear¶

In [14]:

dequeue = Dequeue(max_size=5)

dequeue = Dequeue(max_size=5)

In [15]:

dequeue

dequeue

Out[15]:

In [16]:

dequeue.enqueue(10, position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(10, position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting first item in the dequeue
Inserting: 10 in the dequeue from front
[Front: 10]
<Node: 10>
<Node: 10>

In [17]:

dequeue.enqueue(20, position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(20, position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 20 at the rear of dequeue
[Front: 10]<-[Rear: 20]
<Node: 10>
<Node: 20>

In [18]:

dequeue.enqueue(30, position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(30, position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 30 at the rear of dequeue
[Front: 10]<-[20]<-[Rear: 30]
<Node: 10>
<Node: 30>

In [19]:

dequeue.enqueue(40, position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(40, position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 40 at the rear of dequeue
[Front: 10]<-[20]<-[30]<-[Rear: 40]
<Node: 10>
<Node: 40>

In [20]:

dequeue.enqueue(50, position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(50, position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 50 at the rear of dequeue
[Front: 10]<-[20]<-[30]<-[40]<-[Rear: 50]
<Node: 10>
<Node: 50>

dequeue from rear¶

In [21]:

dequeue.dequeue(position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 50 from rear of the dequeue
[Front: 10]<-[20]<-[30]<-[Rear: 40]
<Node: 10>
<Node: 40>

In [22]:

dequeue.dequeue(position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 40 from rear of the dequeue
[Front: 10]<-[20]<-[Rear: 30]
<Node: 10>
<Node: 30>

In [23]:

dequeue.dequeue(position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 30 from rear of the dequeue
[Front: 10]<-[Rear: 20]
<Node: 10>
<Node: 20>

In [24]:

dequeue.dequeue(position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 20 from rear of the dequeue
[Front: 10]
<Node: 10>
<Node: 10>

In [25]:

dequeue.dequeue(position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 10 from rear of the dequeue

None
None

In [26]:

dequeue.dequeue(position="rear")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="rear") print(dequeue) print(dequeue.front) print(dequeue.rear)

Dequeue is empty, nothing to dequeue

None
None

In [27]:

dequeue

dequeue

Out[27]:

insert from front¶

In [28]:

dequeue = Dequeue(max_size=5)

dequeue = Dequeue(max_size=5)

In [29]:

dequeue

dequeue

Out[29]:

In [30]:

dequeue.enqueue(10, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(10, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting first item in the dequeue
Inserting: 10 in the dequeue from front
[Front: 10]
<Node: 10>
<Node: 10>

In [31]:

dequeue.enqueue(20, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(20, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 20 in the dequeue from front
[Front: 20]<-[Rear: 10]
<Node: 20>
<Node: 10>

In [32]:

dequeue.enqueue(30, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(30, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 30 in the dequeue from front
[Front: 30]<-[20]<-[Rear: 10]
<Node: 30>
<Node: 10>

In [33]:

dequeue.enqueue(40, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(40, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 40 in the dequeue from front
[Front: 40]<-[30]<-[20]<-[Rear: 10]
<Node: 40>
<Node: 10>

In [34]:

dequeue.enqueue(50, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(50, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Inserting: 50 in the dequeue from front
[Front: 50]<-[40]<-[30]<-[20]<-[Rear: 10]
<Node: 50>
<Node: 10>

In [ ]:

In [37]:

dequeue.enqueue(30, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(30, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Dequeue is full, nothing to queue
[Front: 50]<-[40]<-[30]<-[20]<-[Rear: 10]
<Node: 50>
<Node: 10>

In [38]:

dequeue.enqueue(40, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(40, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Dequeue is full, nothing to queue
[Front: 50]<-[40]<-[30]<-[20]<-[Rear: 10]
<Node: 50>
<Node: 10>

In [39]:

dequeue.enqueue(50, position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.enqueue(50, position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Dequeue is full, nothing to queue
[Front: 50]<-[40]<-[30]<-[20]<-[Rear: 10]
<Node: 50>
<Node: 10>

dequeue from front¶

In [40]:

dequeue.dequeue(position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 50 from front of the dequeue
[Front: 40]<-[30]<-[20]<-[Rear: 10]
<Node: 40>
<Node: 10>

In [41]:

dequeue.dequeue(position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 40 from front of the dequeue
[Front: 30]<-[20]<-[Rear: 10]
<Node: 30>
<Node: 10>

In [42]:

dequeue.dequeue(position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 30 from front of the dequeue
[Front: 20]<-[Rear: 10]
<Node: 20>
<Node: 10>

In [43]:

dequeue.dequeue(position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 20 from front of the dequeue
[Front: 10]
<Node: 10>
<Node: 10>

In [44]:

dequeue.dequeue(position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Removing: 10 from front of the dequeue

None
None

In [45]:

dequeue.dequeue(position="front")
print(dequeue)
print(dequeue.front)
print(dequeue.rear)

dequeue.dequeue(position="front") print(dequeue) print(dequeue.front) print(dequeue.rear)

Dequeue is empty, nothing to dequeue

None
None

In [46]:

dequeue

dequeue

Out[46]:

In [ ]:

In [ ]: