Section 6.15. Special Features of Lists

6.15. Special Features of Lists

6.15.1. Creating Other Data Structures Using Lists

Because 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.

Stack

A 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)

This simple script uses lists as a stack to store and retrieve strings entered through this menu-driven text application using only the append() and pop() list methods.

1  #!/usr/bin/env python 2 3  stack = [] 4 5  def pushit(): 6      stack.append(raw_input('Enter new string: ').strip()) 7 8  def popit(): 9      if len(stack) == 0: 10         print 'Cannot pop from an empty stack!' 11     else: 12         print 'Removed [', 'stack.pop()', ']' 13 14 def viewstack(): 15     print stack      # calls str() internally 16 17 CMDs = {'u': pushit, 'o': popit, 'v': viewstack} 18 19 def showmenu(): 20     pr = """ 21 p(U)sh 22 p(O)p 23 (V)iew 24 (Q)uit 25 26 Enter choice: """ 27 28     while True: 29         while True: 30             try: 31                 choice = raw_input(pr).strip()[0].lower() 32             except (EOFError,KeyboardInterrupt,IndexError): 33                 choice = 'q' 34 35             print '\nYou picked: [%s]' % choice 36             if choice not in 'uovq': 37                 print 'Invalid option, try again' 38             else: 39                 break 40 41         if choice == 'q': 42             break 43         CMDs[choice]() 44 45 if __name__ == '__main__': 46     showmenu()

Line-by-Line Explanation

Lines 13

In addition to the Unix startup line, we take this opportunity to clear the stack (a list).

Lines 56

The pushit() function adds an element (a string prompted from the user) to the stack.

Lines 812

The 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 1415

The viewstack() function displays the current contents of the stack.

Line 17

Although 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 1943

The 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 4546

This 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]

Queue

A 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)

This simple script uses lists as a queue to store and retrieve strings entered through this menu-driven text application, using only the append() and pop() list methods.

1  #!/usr/bin/env python 2 3  queue = [] 4 5  def enQ(): 6      queue.append(raw_input('Enter new string: ').strip()) 7 8  def deQ(): 9      if len(queue) == 0: 10          print 'Cannot pop from an empty queue!' 11     else: 12         print 'Removed [', 'queue.pop(0)', ']' 13 14 def viewQ(): 15     print queue       # calls str() internally 16 17 CMDs = {'e': enQ, 'd': deQ, 'v': viewQ} 18 19 def showmenu(): 20     pr = """ 21 (E)nqueue 22 (D)equeue 23 (V)iew 24 (Q)uit 25 26 Enter choice: """ 27 28     while True: 29         while True: 30              try: 31                  choice = raw_input(pr).strip()[0].lower() 32              except (EOFError,KeyboardInterrupt,IndexError): 33                  choice = 'q' 34 35             print '\nYou picked: [%s]' % choice 36             if choice not in 'devq': 37                print 'Invalid option, try again' 38             else: 39                 break 40 41        if choice == 'q': 42            break 43        CMDs[choice]() 44 45 if __name__ == '__main__': 46     showmenu()

Line-by-Line Explanation

Because of the similarities of this script with the stack.py script, we will describe in detail only the lines which have changed significantly:

Lines 17

The usual setup plus some constants for the rest of the script to use.

Lines 56

The enQ() function works exactly like pushit(), only the name has been changed.

Lines 812

The 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, 36

The 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]