Two fundamental data structures in computer science are the stack and the queue.

A queue$$like the checkout line in the grocery store$$is a $$first in$,$ first out$($FIFO$)$ data structure. The first one in line is the first one to get checked out.

A stack is a $$last in$,$ first out$($LIFO$)$ data structure$$like a stack of cafeteria trays. The most recently added tray is at the top of the stack, and thus will be the next one removed.

Both of these data structures are easily implemented in Python using a list.

If we add items at one end of the list and remove them from the other end, we have a queue.

If we add and remove items from the same end of the list, we have a stack.

Using a list as a queue

Here$$s an example of a queue in Python.

$"""$ Demonstration of a queue $"""$ if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$: queue $=[]$ while True: name $=$ input$("$Enter the name of someone entering the queue, $""$or enter 'next' to help the next customer: $")$ if name $==$ "next" and queue: print$($f$"$Now serving $\{$queue$.$pop$(0)\}.")$ else: queue.append$($name$)$ if not queue: print$("$Everyone in the queue has been served."$)$ break

Here$$s a test run of this program.

Enter name of person entering the queue, or enter 'next' to serve the next customer: jane Enter name of person entering the queue, or enter 'next' to serve the next customer: fred Enter name of person entering the queue, or enter 'next' to serve the next customer: milo Enter name of person entering the queue, or enter 'next' to serve the next customer: next Now serving jane. Enter name of person entering the queue, or enter 'next' to serve the next customer: next Now serving fred. Enter name of person entering the queue, or enter 'next' to serve the next customer: bill Enter name of person entering the queue, or enter 'next' to serve the next customer: next Now serving milo. Enter name of person entering the queue, or enter 'next' to serve the next customer: next Now serving bill. Everyone in the queue has been served.

Notice that Jane was first in the queue, so Jane was first to be served. Bill was last to enter the queue, so Bill was last to be served.

Using a list as a stack

To implement a stack, we use $.$append$()$ and $.$pop$()$ rather than $.$pop$(0)$ as we did with the queue. This means that the most recently appended element will be next off the stack when we $.$pop$().$

Reverse a string using a stack $($reverse$.$py$,8$ points$)$

There are many ways to reverse a string in Python. For example:

s $=$ "rumplestiltzkin" s $=$ s$[-1$::$-1]$ # reverse using a slice print$($s$)$ # prints "nikztlitselpmur"

s $=$ "rumplestiltzkin" reverse $=\text{'}\text{'}$ for letter in s: reverse $=$ letter $+$ reverse print$($reverse$)$ # prints "nikztlitselpmur"

s $=$ "rumplestiltzkin" reverse $=\text{'}\text{'}$ for i in range$(-1,-($len$($s$)+1),-1)$: reverse $=$ reverse $+$ s$[$i$]$ print$($reverse$)$ # prints "nikztlitselpmur"

s $=$ "rumplestiltzkin" lst $=$ list$($s$)$ lst$.$reverse$()$ s $="".$join$($lst$)$ print$($s$)$ # prints "nikztlitselpmur"

For this program you will use a stack to reverse a string. It is pushing and popping that will do the work of reversing. This does not include any of the examples given. Start with an empty stack:

stack $=[]$

Then prompt the user for a string. Then use the stack to reverse the string.

Hint

The last three lines in your program should be

while stack: print$($stack$.$pop$(),$ end$=\text{'}\text{'})$ print$()$

These last three lines will pop letters off the stack and print them.

Here$$s an example of how this should work when you run it$.$

Enter a string, and I'll print it backwards! rumplestiltzkin nikztlitselpmur

If the user just presses return$/$enter at the prompt, your program should print an empty line.

Enter a string, and I'll print it backwards!