Learning Objectives

• Practice using the stack and the queue data structures

Assignment Description

The stack and the queue data structures are used in a wide range of applications throughout the world. A number of programming languages are built on operand stacks and call stacks as a means of organizing inputs and determining the order of operations of function calls. Likewise, queues can do many things like helping schedule tasks for a computer or managing user priority based on a FIFO (first in, first out) principle. You will also find both useful in traversing a graph later in the semester. These data structures are very versatile and useful throughout the software world. A visualization of them can be found here.

Submission Instructions

Using the Prairielearn workspace, test and save your solution to the following exercises. (You are welcome to download and work on the files locally but they must be re-uploaded or copied over to the workspace for submission).

Provided queue and stacks

Python provides many ways to set up these data structures in real life, list, deque, task queue which all have different tradeoffs and use cases. However, we want to focus on understanding the use of such structures, so for this lab we have provided class definitions for the queue and stack data structures for you to use which the test cases will assume you’re using. Here is what all you have available:

Stack:

• __init__() - sets up an empty stack
• push(val) - adds an item to the top of the stack
• pop() - removes the item from the top of the stack and returns it
• __len__() - returns the length of all the items in the stack
• __str__() - prints the stack as though it was a list (‘top’ is the last element)
• top() - returns the item from the top of the stack
• empty() - returns if the stack is empty

Queue:

• __init__() - sets up an empty queue
• enqueue(val) - adds an item to the back of the queue
• dequeue() - removes an item from the front of the queue
• __len__() - returns the size of the queue
• __str__() - prints the queue as though it was a list (‘front’ is the first element)
• front() - returns the item in front of the queue
• empty() - returns if the queue is empty

Warning: To get credit you must use these given structure and you must not edit utils.py (It is not a submitted file so your changes wont effect the autograder!)

Balancing Brackets: the isBalanced Function

# INPUT:
# q, an input queue containing a sequence of characters
# OUTPUT: 
# a bool value indicating whether the input sequence is 'balanced'
# A balanced string contains an equal amount of '[' and ']' brackets
# organized such that there is a matching closed bracket for every open bracket.
def isBalanced(q):

For this exercise, you must write a function called isBalanced that takes one argument, a queue, and returns a bool (true or false) based on whether the string represented by the queue has balanced brackets. The queue may contain any characters, although you should only consider square bracket characters, ‘[’ and ‘]’, when considering whether a string is balanced. To be balanced, a string must not have any unmatched, extra, or hanging brackets. For example, the string [hello][] is balanced, [[][[]a]] is balanced, []] is unbalanced, ][ is unbalanced, and ))))[beepboop] is balanced. It’s possible to solve this problem without using a stack, but in the spirit of this lab, you should use one in your solution!

NOTE: Order matters! ][ is unbalanced because although it contains an equal number of opening and closing brackets, the open bracket must come first. Stated another way, a closing bracket with nothing to close is unbalanced as is an open bracket which is not closed.

leftRotateQueue()

# INPUT:
# q, an input queue containing a sequence of values (type doesnt matter)
# offset, a positive integer describing how many left rotations to perform
# OUTPUT: 
# None
# The function should directly modify the input queue to contain the rotated
# version of the same input values.
def leftRotateQueue(q, offset):

Given an ordered list (or stack or queue), a ‘rotation’ shifts the order of each item by moving either the front item to the end (we will call this a ‘left’ rotation) or the end to the front (we will call this a ‘right’ rotation), and shuffling the position of every other item to match.

For example:

[1, 2, 3] # Original list
[2, 3, 1] # Rotate original to left by one
[3, 1, 2] # Rotate original to left by two
[1, 2, 3] # Rotate original to left by three (is also original!)

The queue in particular is good for creating rotations. Why?

removeOdds()

# INPUT:
# s, an input stack containing a sequence of values (type doesnt matter)
# OUTPUT: 
# None
# The function should directly modify the input stack to contain all items
# in the same order except all odds are removed
def removeOdds(s):

Given an ordered list as a stack, remove all odd values while otherwise preserving the order of the original stack. To look at every item in a stack, you will have to remove them one at a time deciding after each removal whether to keep or discard the item.

You are strongly encouraged to use a second stack to help preserve the order of items which are valid but make sure the original list (passed in as ‘s’) contains the correct values in the correct order at the end!

mergeSortedQueues()

# INPUT:
# q1, an input queue of sorted integers
# q2, an input queue of sorted integers
# OUTPUT: 
# a queue object containing the contents of both original queues (but sorted)
# Your code should be able to handle duplicate values and ties
def mergeSortedQueues(q1, q2):

Given two queues which each contain a different sorted list of numbers, merge the two queues into a third (new) queue containing every number in order. To get the most out of this exercise, you are encouraged to solve this problem using just the two input queues and your third output.

reverseStack()

# INPUT:
# s, an input stack containing a sequence of values (type doesnt matter)
# OUTPUT: 
# None
# The function should directly modify the input stack to contain all items in reverse order
# You will need to store every item in the stack in another data structure. 
# HINT: A queue might be a great data structure for storage!
def reverseStack(s):

Given a stack as input, modify that stack to contain all the same values in reverse order. Like most of the other stack and queue problems, you will have to empty the stack first before rebuilding it with the correct values.

A queue might be a great data structure to help you keep your stack’s information while emptying it!