Pointers malfunctioning in the implementation of double ended queues
I learnt the below implemented logic from a book but it seems as though my front pointer isn't where it should be once I start to add elements from rear and front. The order of elements does not become as expected.
Suggestions on how I might fix my logic in the add_first and add_last method?
class Deque():
DEFAULT_CAPACITY = 10
def __init__(self):
self._data = [None]*Deque.DEFAULT_CAPACITY
self._size = 0
self._front = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def first(self):
if self.is_empty():
raise Exception('Queue is empty')
return self._data[self._front]
def last(self):
if self.is_empty():
raise Exception('Queue is empty')
back = (self._front + self._size - 1) % len(self._data)
return self._data[back]
def delete_first(self):
if self.is_empty():
raise Exception('Queue is empty')
answer = self._data[self._front]
self._data[self._front] = None
self._front = (self._front + 1) % len(self._data)
self._size -= 1
return answer
def delete_last(self):
if self.is_empty():
raise Exception('Queue is empty')
back = (self._front + self._size - 1) % len(self._data)
answer = self._data[back]
self._data[back] = None
self._size -= 1
return answer
def add_first(self, e):
if self._size == len(self._data):
self._resize(2*len(self.data))
self._front = (self._front - 1) % len(self._data)
self._data[self._front] = e
self._size += 1
def add_last(self, e):
if self._size == len(self._data):
self._resize(2*len(self.data))
avail = (self._front + self._size) % len(self._data)
self._data[avail] = e
self._size += 1
def _resize(self, cap):
old = self._data
self._data = [None]*cap
walk = self._front
for k in range(self._size):
self._data[k] = old[walk]
walk = (1 + walk) % len(old)
self._front = 0
The problem with your class method add_first is that if front pointer points 0 it changes to the last element. I changed as minimum as I could and added comments hope it helps.
def add_first(self, e):
if self._size == len(self._data) or self._front==0: #if front is atfirst element we need resize
self._resize(2 * len(self._data))
self._front = (self._front - 1) % len(self._data)
self._data[self._front] = e
self._size += 1
def add_last(self, e):
if self._front+self._size == len(self._data):#As there might be Nones at the beginning
self._resize(2 * len(self._data))
avail = (self._front + self._size) % len(self._data)
self._data[avail] = e
self._size += 1
def _resize(self, cap):
##adding cap//4 Nones at the beginning and cap//4 Nones at the end. This shifts front by cap//4
self._front = cap//4+self._front
old = self._data
self._data = [None] * (cap//4)+old+[None] * (cap//4)