Reference no: EM132112788

PYTHON:

The introduction of Section 6.1 notes that stacks are often used to provide "undo" support in applications like a Web browser or text editor.

While support for undo can be implemented with an unbounded stack, many applications provide onlylimited support for such an undo history, with a fixed-capacity stack.

When push is invoked with the stack at full capacity, rather than throwing an exception, a more typical semantic is to accept the pushed element at the top while "leaking" the oldest element from the bottom of the stack to make room.

Give an implementation of such a LeakyStack abstraction, using a circular array.

Important:

For instance variables you may use a python list, and integers. Nothing else. Nothing. No credit if you violate this rule.

All operations except __str__ should run in constant time (assuming append on lists takes constant time).

I did this :

class LeakyStack:
def __init__(self,maxsize):
self.data = []
self.maxsize=maxsize
self.len = 0

def push(self,x):
if self.len == self.maxsize:
del self.data[0]
self.data.append(x)
else:
self.data.append(x)
self.len += 1

def pop(self):
self.len -= 1
self.data.pop()

def __len__(self):
return self.len

def is_empty(self):
return len(self.data)==0

def __str__(self):
return ' '.join(str(self.data[i]) for i in range (len(self.data)))

But with my method, I can't see where a circular array fits. What method would implement that?

Slicing is not constant runtime so based on the 'important' note I can't use that.