3. Double Ended Queue using Python List

Double Ended Queue using List¶

In [1]:

class Dequeue:
    
    def __init__(self, max_size):
        self.items = [None]*max_size
        self.capacity = max_size
        self.front = -1
        self.rear = 0
        self.count = 0
    
    def __repr__(self):
        nodes = []
        counter = 0
        ptr = self.front
        hit_rear = True
        while counter < self.count:
            if ptr == self.front and hit_rear:
                nodes.append("[Front: %s]" % self.items[ptr])
                hit_rear = False
            elif ptr == self.rear:
                nodes.append("[Rear: %s]" % self.items[ptr])
            else:
                nodes.append("[%s]" % self.items[ptr])
            ptr = (ptr+1) % self.capacity
            counter += 1
            
        return "<-".join(nodes)
        
    
    def __len__(self):
        return self.count
    
    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):
        position = position.lower()
        
        if self.is_full():
            print("Cannot insert any item, queue is full")
            return
        
        if isinstance(position, str):
            if position == "front":
                
                if self.front == -1 and self.rear == 0:
                    print("Inserting first element in the queue")
                    print(f"Inserting: {data} from front")
                    self.front = self.rear = 0
                    self.items[self.front] = data
    
                else:
                    self.front = (self.front - 1) % self.capacity
                    print(f"Inserting: {data} from front")
                    self.items[self.front] = data
                    
                self.count += 1    
                
            elif position == "rear":
                
                if self.front == -1 and self.rear == 0:
                    print("Inserting first element in the queue")
                    print(f"Inserting: {data} at rear")
                    self.front = self.rear = 0
                    self.items[self.rear] = data
                else:
                    self.rear = (self.rear + 1) %  self.capacity
                    print(f"Inserting: {data} at rear")
                    self.items[self.rear] = data
                
                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):
        position = position.lower()
        
        if self.is_empty():
            print("Queue is empty, nothing to dequeue")
            return
        
        if isinstance(position, str):
            if position == "front":
                data = self.items[self.front]
                self.items[self.front] = None
                print(f"Removing: {data} from front of the queue")
                
                self.front = (self.front + 1) % self.capacity
                self.count -= 1
            
            elif position == "rear":
                data = self.items[self.rear]
                self.items[self.rear] = None
                print(f"Removing: {data} from rear")
                self.rear = (self.rear - 1) % self.capacity
                self.count -= 1
                
            else:
                print("Incorrect string. Enter either 'front' or 'rear' to dequeue")
                return
        else:
            print("Not a string. Enter either front or rear to dequeue")
            return

class Dequeue: def __init__(self, max_size): self.items = [None]*max_size self.capacity = max_size self.front = -1 self.rear = 0 self.count = 0 def __repr__(self): nodes = [] counter = 0 ptr = self.front hit_rear = True while counter < self.count: if ptr == self.front and hit_rear: nodes.append("[Front: %s]" % self.items[ptr]) hit_rear = False elif ptr == self.rear: nodes.append("[Rear: %s]" % self.items[ptr]) else: nodes.append("[%s]" % self.items[ptr]) ptr = (ptr+1) % self.capacity counter += 1 return "<-".join(nodes) def __len__(self): return self.count 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): position = position.lower() if self.is_full(): print("Cannot insert any item, queue is full") return if isinstance(position, str): if position == "front": if self.front == -1 and self.rear == 0: print("Inserting first element in the queue") print(f"Inserting: {data} from front") self.front = self.rear = 0 self.items[self.front] = data else: self.front = (self.front - 1) % self.capacity print(f"Inserting: {data} from front") self.items[self.front] = data self.count += 1 elif position == "rear": if self.front == -1 and self.rear == 0: print("Inserting first element in the queue") print(f"Inserting: {data} at rear") self.front = self.rear = 0 self.items[self.rear] = data else: self.rear = (self.rear + 1) % self.capacity print(f"Inserting: {data} at rear") self.items[self.rear] = data 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): position = position.lower() if self.is_empty(): print("Queue is empty, nothing to dequeue") return if isinstance(position, str): if position == "front": data = self.items[self.front] self.items[self.front] = None print(f"Removing: {data} from front of the queue") self.front = (self.front + 1) % self.capacity self.count -= 1 elif position == "rear": data = self.items[self.rear] self.items[self.rear] = None print(f"Removing: {data} from rear") self.rear = (self.rear - 1) % self.capacity self.count -= 1 else: print("Incorrect string. Enter either 'front' or 'rear' to dequeue") return else: print("Not a string. Enter either front or rear to dequeue") return

test insert at front¶

In [2]:

dequeue = Dequeue(5)

dequeue = Dequeue(5)

In [3]:

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

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

Inserting first element in the queue
Inserting: 10 from front
[10, None, None, None, None]
0
0

In [4]:

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

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

Inserting: 20 from front
[10, None, None, None, 20]
4
0

In [5]:

dequeue

dequeue

Out[5]:

[Front: 20]<-[Rear: 10]

In [6]:

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

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

Inserting: 30 from front
[10, None, None, 30, 20]
3
0

In [7]:

dequeue

dequeue

Out[7]:

[Front: 30]<-[20]<-[Rear: 10]

In [8]:

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

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

Inserting: 40 from front
[10, None, 40, 30, 20]
2
0

In [9]:

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

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

Inserting: 50 from front
[10, 50, 40, 30, 20]
1
0

In [10]:

dequeue

dequeue

Out[10]:

[Front: 50]<-[40]<-[30]<-[20]<-[Rear: 10]

In [11]:

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

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

Cannot insert any item, queue is full
[10, 50, 40, 30, 20]
1
0

test insert at rear¶

In [12]:

dequeue = Dequeue(5)

dequeue = Dequeue(5)

In [13]:

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

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

Inserting first element in the queue
Inserting: 10 at rear
[10, None, None, None, None]
0
0

In [14]:

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

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

Inserting: 20 at rear
[10, 20, None, None, None]
0
1

In [15]:

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

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

Inserting: 30 at rear
[10, 20, 30, None, None]
0
2

In [16]:

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

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

Inserting: 40 at rear
[10, 20, 30, 40, None]
0
3

In [17]:

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

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

Inserting: 50 at rear
[10, 20, 30, 40, 50]
0
4

In [18]:

dequeue

dequeue

Out[18]:

[Front: 10]<-[20]<-[30]<-[40]<-[Rear: 50]

In [19]:

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

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

Cannot insert any item, queue is full
[10, 20, 30, 40, 50]
0
4

test - 1¶

In [20]:

dequeue = Dequeue(max_size=5)

dequeue = Dequeue(max_size=5)

In [21]:

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

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

Inserting first element in the queue
Inserting: 10 from front
[10, None, None, None, None]
0
0

In [22]:

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

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

Inserting: 20 from front
[10, None, None, None, 20]
4
0

In [23]:

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

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

Inserting: 1 at rear
[10, 1, None, None, 20]
4
1

In [24]:

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

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

Inserting: 2 at rear
[10, 1, 2, None, 20]
4
2

In [25]:

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

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

Inserting: 30 from front
[10, 1, 2, 30, 20]
3
2

In [26]:

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

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

Cannot insert any item, queue is full
[10, 1, 2, 30, 20]
3
2

In [27]:

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

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

Cannot insert any item, queue is full
[10, 1, 2, 30, 20]
3
2

In [28]:

dequeue

dequeue

Out[28]:

[Front: 30]<-[20]<-[10]<-[1]<-[Rear: 2]

test - 2¶

In [29]:

dequeue = Dequeue(max_size=5)

dequeue = Dequeue(max_size=5)

In [30]:

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

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

Inserting first element in the queue
Inserting: 100 at rear
[100, None, None, None, None]
0
0

In [31]:

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

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

Inserting: 1 from front
[100, None, None, None, 1]
4
0

In [32]:

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

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

Inserting: 200 at rear
[100, 200, None, None, 1]
4
1

In [33]:

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

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

Inserting: 2 from front
[100, 200, None, 2, 1]
3
1

In [34]:

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

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

Inserting: 300 at rear
[100, 200, 300, 2, 1]
3
2

In [35]:

dequeue

dequeue

Out[35]:

[Front: 2]<-[1]<-[100]<-[200]<-[Rear: 300]

In [36]:

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

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

Removing: 2 from front of the queue
[100, 200, 300, None, 1]
4
2

In [37]:

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

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

Removing: 300 from rear
[100, 200, None, None, 1]
4
1

In [38]:

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

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

Removing: 1 from front of the queue
[100, 200, None, None, None]
0
1

In [39]:

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

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

Removing: 100 from front of the queue
[None, 200, None, None, None]
1
1

In [40]:

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

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

Removing: 200 from rear
[None, None, None, None, None]
1
0

In [41]:

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

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

Queue is empty, nothing to dequeue
[None, None, None, None, None]
1
0

In [42]:

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

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

Inserting: 100 at rear
[None, 100, None, None, None]
1
1

In [43]:

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

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

Inserting: 1 from front
[1, 100, None, None, None]
0
1

In [44]:

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

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

Inserting: 200 at rear
[1, 100, 200, None, None]
0
2

In [45]:

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

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

Inserting: 2 from front
[1, 100, 200, None, 2]
4
2

In [46]:

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

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

Inserting: 3 from front
[1, 100, 200, 3, 2]
3
2

In [47]:

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

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

Cannot insert any item, queue is full
[1, 100, 200, 3, 2]
3
2

In [ ]: