Stacks, Queues, and Deques

Exercise 1: LIFO and FIFO (4 points)

Explain the difference between LIFO and FIFO. How does this link to stacks and queues?

Exercise 2: Empty stacks (2 points)

What happens if your program calls pop() for an empty stack?

Exercise 3: Fun with stacks (10 points)

What does the following code fragment print when n is 50? Give a high-level description of what it does when presented with a positive integer n.

stack = Stack()
while n > 0:
    stack.push(n % 2)
    n = n // 2
size = stack.size()
for i in range(size):
    print(stack.pop(), end="")
print("")

Exercise 4: Understanding stacks and queues (10 points)

What does the following code fragment do to the queue q?

stack = Stack()
while not q.isEmpty():
    stack.push(q.dequeue())
while not stack.isEmpty():
    q.enqueue(stack.pop())

Exercise 5: Implementation of a resizable stack with new features (20 points)

In this exercise you should implement a resizable stack (array-based) with two new features: top (returns the first element without removing it) and usedSpace (returns a percentage indicating the array space used by the contained elements). The necessary starter code is available here: Material.zip.

Executing your program should result in the following console output.

## testing push and pop ##

S
T
A
C
K

## testing top and empty ##

Elements on this stack: 3
Is this stack empty? False
What is the TOP element: C
Elements on this stack: 3
Is this stack empty: False

## testing resize ##

Used array space: 78 %
Used array space: 53 %
Used array space: 29 %

Exercise 6: Deque (20 points)

A double-ended queue, or deque (pronounced "deck"), is like a normal queue but supports adding and removing items at both ends. A deque stores a collection of items and supports the following API:

class Deque

    Deque()                    create an empty deque
    bool isEmpty()             is the deque empty?
    int size()                 number of items in the deque
    void pushLeft(obj: item)   add an item to the left end
    void pushRight(obj: item)  add an item to the right end
    item popLeft()             remove an item from the left end
    item popRight()            remove an item from the right end

Write a class Deque that uses a doubly linked list to implement this API. A Python test snippet is available here: Material.zip. Executing your program should result in the following console output.

## testing push: ##

Elements in Deque: 0
Elements in Deque: 9

## testing pop: ##

YOUR DEQUE WORKS.