LeakyStack ADT: The introduction of Section 6.1 notes that stacks are often used
ID: 3587596 • Letter: L
Question
LeakyStack ADT:
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 only limited support for such an undo history, with a fixed stack capacity.
When a push is invoked on a LeakyStack at full capacity, rather than throwing an exception, accept the pushed element at the top while “leaking” the oldest element from the bottom of the stack to make room.
Write the generic interface for this LeakyStack ADT.
Give an efficient static implementation of the LeakyStack abstraction.
Provide a test of your LeakyStack that clearly shows that all of the methods work correctly.
Explanation / Answer
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)))
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.