Stacks and Queues

Implementation

For each of the attached questions, use a List and some additional variables, implement either a Stack or a Queue in C#.

Stack

For a stack, you should include an integer variable to represent the location of the value that would be popped from the Stack. Popping should reduce this variable, pushing should increment it.

Queue

For a queue, you should have two integers, one marking the front, the other marking the back, of the queue. For this scenario, don't worry about rebasing the list. Dequeuing should fail if the two variables overlap.

Then answer the following questions:

1. Use a stack to take in a collection of strings and then to print these out in reverse order.
2. Write a program that reads in a positive integer and prints the binary representation of that integer. Hint: division by 2.
3. A letter means push and an asterisk means pop in the following sequence. Using your stack give the sequence of values returned by the pop operations when this sequence of operations is performed on an initially empty (LIFO) stack: E A S * Y * Q U E * * * S T * * * I O * N * * *
4. Ensure the stack program from the previous question issues a warning and exits if the program attempts to pop an empty stack.
5. A letter means push and an asterisk means pop in the following sequence. Using your queue give the sequence of values returned by the pop operations when this sequence of operations is performed on an initially empty (FIFO) queue: E A S * Y * Q U E * * * S T * * * I O * N * * *
6. Ensure the queue function from the previous question issues a warning and exits if the program attempts to pop an empty stack.
7. Suppose that an mixed sequence of push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequences could not occur?
   • 4 3 2 1 0 9 8 7 6 5
   • 4 6 8 7 5 3 2 9 0 1
   • 2 5 6 7 4 8 9 3 1 0
   • 4 3 2 1 0 5 6 7 8 9

Graph Search Uses

Warning: definite extension stuff ...

Breadth-First / Shortest Path

Needs a FIFO: use a queue, add all the children to the back of the queue. This means that all the paths of specific length are exhausted first, before queues of the next length.

Depth-First / Existential Proof

Needs a LIFO: use a stack, add all the children to the head item to the head of the list so as to dive deep first, then backtrack.

BIO 2018

For example, BIO 2018 Q3 can be solved using a Queue.

Extension Stack/Queue Questions

1. In the game of chess a knight can move between any two squares on the both. Use a queue to find the shortest path for a knight between two given squares.
2. Use a queue to generate all possible binary numbers as strings.
3. Implement a circular queue of size n, using integer variables to represent the front and the back. Insert more than n variables and ensure that the appropriate, i.e. oldest, values are replaced.
4. Consider a 2d array of integers, where the values represent different colour, consider how a queue might be used to 'flood fill' an area of the grid, i.e. starting from a given location with a target colour, all neighouring cells should be coloured the same colour.
5. Given a mathematical statement using parantheses, use a stack to check if the pairs balance.
6. Implement a postfix calculator using a stack.