See All Titles |
![]() ![]() Special Features of ListsCreating Other DataStructures 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. The two code samples in this section use the pop() method which became reality in Python 1.5.2. If you are using an older system, this function is easily duplicated in Python. (See Exercise 6-17.) StackA stack is a last-in-first-out (LIFO) data structure which works similar 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. The following example shows a menu-driven program which implements a simple stack used to store strings: Example 6.2. 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. <$nopage> 001 1 #!/usr/bin/env python 002 2 003 3 stack = [] 004 4 005 5 def pushit(): 006 6 stack.append(raw_input('Enter new string: ')) 007 7 008 8 def popit(): 009 9 if len(stack) == 0: 010 10 print 'Cannot pop from an empty stack!' 011 11 else: <$nopage> 012 12 print 'Removed [', stack.pop(), ']' 013 13 014 14 def viewstack(): 015 15 print str(stack) 016 16 017 17 def showmenu(): 018 18 prompt = """ 019 19 p(U)sh 020 20 p(O)p 021 21 (V)iew 022 22 (Q)uit 023 23 024 24 Enter choice: """ 025 25 026 26 done = 0 027 27 while not done: 028 28 029 29 chosen = 0 030 30 while not chosen: 031 31 try: <$nopage> 032 32 choice = raw_input(prompt)[0] 033 33 except (EOFError, KeyboardInterrupt): 034 34 choice = 'q' 035 35 print 'nYou picked: [%s]' % choice 036 36 if choice not in 'uovq': 037 37 print 'invalid option, try again' 038 38 else: 039 39 chosen = 1 040 40 041 41 if choice == 'q': done = 1 042 42 if choice == 'u': pushit() 043 43 if choice == 'o': popit() 044 44 if choice == 'v': viewstack() 045 45 046 46 if __name__ == '__main__': 047 47 showmenu() 048 <$nopage> Lines 1–3In addition to the Unix startup line, we take this opportunity to clear the stack (a list). Lines 5–6The pushit() function adds an element (a string prompted from the user) to the stack. Lines 8–12The 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. Lines 14–15The viewstack() function displays a printable string representation of the list. Lines 17–44The 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. Lines 46–47This part of the code starts up the program if invoked directly. If this script was 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 46 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.3. 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. <$nopage> 001 1 #!/usr/bin/env python 002 2 003 3 queue = [] 004 4 005 5 def enQ(): 006 6 queue.append(raw_input('Enter new string: ')) 007 7 008 8 def deQ(): 009 9 if len(queue) == 0: 010 10 print 'Cannot dequeue from empty queue!' 011 11 else: <$nopage> 012 12 print 'Removed [', queue.pop(0), ']' 013 13 014 14 def viewQ(): 015 15 print str(queue) 016 16 017 17 def showmenu(): 018 18 prompt = """ 019 19 (E)nqueue 020 20 (D)equeue 021 21 (V)iew 022 22 (Q)uit 023 23 024 24 Enter choice: """ 025 25 026 26 done = 0 027 27 while not done: 028 28 029 29 chosen = 0 030 30 while not chosen: 031 31 try: <$nopage> 032 32 choice = raw_input(prompt)[0] 033 33 except (EOFError, KeyboardInterrupt): 034 34 choice = 'q' 035 35 print '\nYou picked: [%s]' % choice 036 36 if choice not in 'devq': 037 37 print 'invalid option, try again' 038 38 else: <$nopage> 039 39 chosen = 1 040 40 041 41 if choice == 'q': done = 1 042 42 if choice == 'e': enQ() 043 43 if choice == 'd': deQ() 044 44 if choice == 'v': viewQ() 045 45 046 46 if __name__ == '__main__': 047 47 showmenu() 048 <$nopage> Because of the similarities of this script with the stack.py script, we will describe only in detail the lines which have changed significantly: Lines 5–6The enQ() function works exactly like pushit(), only the name has been changed. Lines 8–12The key difference between the two scripts lies here. The deQ() function, rather than taking the most recent item as popitem() did, takes the oldest item on the list, the first element. 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] Subclassing from "Lists"Earlier in this text, we described how types are not classes in Python, so you cannot derive subclasses from them (see the Core Note in Section 4.2). As a proxy, the Python standard library includes two modules containing class wrappers around two types, lists and dictionaries, from which you can subclass. These are the UserList and UserDict modules. Once you are familiar with classes, you can take these already-implemented classes to create your own subclasses from lists and dictionaries and add whatever functionality you wish. These modules are part of the Python standard library. See Section 6.18 for more information.
|
© 2002, O'Reilly & Associates, Inc. |