6.15. Special Features of Lists6.15.1. Creating Other Data Structures Using ListsBecause of their container and mutable features, lists are fairly flexible and it is not very difficult to build other kinds of data structures using lists. Two that we can come up with rather quickly are stacks and queues. StackA stack is a last-in-first-out (LIFO) data structure that works similarly to a cafeteria dining plate spring-loading mechanism. Consider the plates as objects. The first object off the stack is the last one you put in. Every new object gets "stacked" on top of the newest objects. To "push" an item on a stack is the terminology used to mean you are adding onto a stack. Likewise, to remove an element, you "pop" it off the stack. Example 6.3 shows a menu-driven program that implements a simple stack used to store strings. Example 6.3. Using Lists as a Stack (stack.py)
Line-by-Line ExplanationLines 13In addition to the Unix startup line, we take this opportunity to clear the stack (a list). Lines 56The pushit() function adds an element (a string prompted from the user) to the stack. Lines 812The popit() function removes an element from the stack (the more recent one). An error occurs when trying to remove an element from an empty stack. In this case, a warning is sent back to the user. When an object is popped from the stack, the user sees which element was removed. We use single backquotes or backticks ( ' ) to symbolize the repr() command, showing the string complete with quotes, not just the contents of the string. Lines 1415The viewstack() function displays the current contents of the stack. Line 17Although we cover dictionaries formally in the next chapter, we wanted to give you a really small example of one here, a command vector (CMDs). The contents of the dictionary are the three "action" functions defined above, and they are accessed through the letter that the user must type to execute that command. For example, to push a string onto the stack, the user must enter 'u', so 'u' is how access the pushit() from the dictionary. The chosen function is then executed on line 43. Lines 1943The entire menu-driven application is controlled from the showmenu() function. Here, the user is prompted with the menu options. Once the user makes a valid choice, the proper function is called. We have not covered exceptions and try-except statement in detail yet, but basically that section of the code allows a user to type ^D (EOF, which generates an EOFError) or ^C (interrupt to quit, which generates a KeyboardInterrupt error), both of which will be processed by our script in the same manner as if the user had typed the 'q' to quit the application. This is one place where the exception-handling feature of Python comes in extremely handy. The outer while loop lets the user continue to execute commands until they quit the application while the inner one prompts the user until they enter a valid command option. Lines 4546This part of the code starts up the program if invoked directly. If this script were imported as a module, only the functions and variables would have been defined, but the menu would not show up. For more information regarding line 45 and the __name__ variable, see Section 3.4.1. Here is a sample execution of our script: $ stack.py p(U)sh p(O)p (V)iew (Q)uit Enter choice: u You picked: [u] Enter new string: Python p(U)sh p(O)p (V)iew (Q)uit Enter choice: u You picked: [u] Enter new string: is p(U)sh p(O)p (V)iew (Q)uit Enter choice: u You picked: [u] Enter new string: cool! p(U)sh p(O)p (V)iew (Q)uit Enter choice: v You picked: [v] ['Python', 'is', 'cool!'] p(U)sh p(O)p (V)iew (Q)uit Enter choice: o You picked: [o] Removed [ 'cool!' ] p(U)sh p(O)p (V)iew (Q)uit Enter choice: o You picked: [o] Removed [ 'is' ] p(U)sh p(O)p (V)iew (Q)uit Enter choice: o You picked: [o] Removed [ 'Python' ] p(U)sh p(O)p (V)iew (Q)uit Enter choice: o You picked: [o] Cannot pop from an empty stack! p(U)sh p(O)p (V)iew (Q)uit Enter choice: ^D You picked: [q] QueueA queue is a first-in-first-out (FIFO) data structure, which works like a single-file supermarket or bank teller line. The first person in line is the first one served (and hopefully the first one to exit). New elements join by being "enqueued" at the end of the line, and elements are removed from the front by being "dequeued." The following code shows how, with a little modification from our stack script, we can implement a simple queue using lists. Example 6.4. Using Lists as a Queue (queue.py)
Line-by-Line ExplanationBecause of the similarities of this script with the stack.py script, we will describe in detail only the lines which have changed significantly: Lines 17The usual setup plus some constants for the rest of the script to use. Lines 56The enQ() function works exactly like pushit(), only the name has been changed. Lines 812The key difference between the two scripts lies here. The deQ() function, rather than taking the most recent item as popit() did, takes the oldest item on the list, the first element. Lines 17, 21-24, 36The options have been changed, so we need to reflect that in the prompt string and our validator. We present some output here as well: $ queue.py (E)nqueue (D)equeue (V)iew (Q)uit Enter choice: e You picked: [e] Enter new queue element: Bring out (E)nqueue (D)equeue (V)iew (Q)uit Enter choice: e You picked: [e] Enter new queue element: your dead! (E)nqueue (D)equeue (V)iew (Q)uit Enter choice: v You picked: [v] ['Bring out', 'your dead!'] (E)nqueue (D)equeue (V)iew (Q)uit Enter choice: d You picked: [d] Removed [ 'Bring out' ] (E)nqueue (D)equeue (V)iew (Q)uit Enter choice: d You picked: [d] Removed [ 'your dead!' ] (E)nqueue (D)equeue (V)iew (Q)uit Enter choice: d You picked: [d] Cannot dequeue from empty queue! (E)nqueue (D)equeue (V)iew (Q)uit Enter choice: ^D You picked: [q] |