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 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 front of the queue
• dequeue() - removes an item from the end 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!)

Part 1: Balancing Brackets: the isBalanced Function

bool isBalanced(queue<char> input)
# 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

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.

Part 2: spyCode Functions

None spyEncode(queue<int> q)
# INPUT:
# q, an input queue containing a sequence of values (type doesnt matter)
# OUTPUT: 
# None
# The function should directly modify the input queue to contain a re-arranged
# version of the same input sequence. Successful implementations will require
# reading and replacing the values in the queue in the appropriate order.

None spyDecode(queue<int> q)
# INPUT:
# q, an input queue containing a sequence of values (type doesnt matter)
# OUTPUT: 
# None
# The function should directly modify the input queue to contain a re-arranged
# version of the same input sequence. Successful implementations will require
# reading and replacing the values in the queue in the appropriate order.

Your task is to write a pair of functions called spyEncode and spyDecode that each take in one argument: a queue and either scrambles the elements in the queue or reverses the scramble. Note that you are adjusting the values in the input queue, not making (or returning) a new queue!

You may use whatever local variables you need. The encode function should reverse the order of SOME of the elements in the queue, and maintain the order of others, according to the following pattern:

1. The first three elements stay on the front of the queue.
2. After the first three elements, each of the following occurs to the next set of three elements in sequence.
   • The next three elements are rotated. So the first element becomes second, the second element becomes the third, and the third element becomes the first.
   • Then the next three elements are reversed. So the first element becomes third, the second stays the same, and the third becomes the first.
   • Then the next three elements are placed on the queue in their original order.
   • The next three elements are rotated (the pattern repeats)

NOTE: You are not allowed to directly edit the underlying data structure to re-arrange elements. Your solution must use the built-in functions (enqueue and dequeue for queues and push and pop for stacks) to perform the re-arrangements.

Hint: You’ll want to make a local stack variable.

For example, given the following queue,

front                             back
0 1 2   3 4 5   6 7 8   9 10 11   12 13 14   

we get the following result:

front                             back
0 1 2   5 3 4   8 7 6   9 10 11   14 12 13

You can assume that the that you’ll always be given blocks of three numbers.

Hint: Think about what will be identical in both encode and decode, and what will be different.

If you want a challenge, consider what adjustments will need to be made to both encode and decode to allow input queues of any size. There’s three levels to this difficulty:

1. What happens if you need to rotate or reverse a block but there’s not three numbers left?
2. What happens if I want to reserve or rotate blocks much larger than three?
3. What happens if I want to account for both?