< BACKMake Note | BookmarkCONTINUE >
156135250194107072078175030179198180024228156016206217188240240204175201138160122254082110

Special Features of Lists

Creating Other DataStructures 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.

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

Stack

A 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–3

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

Lines 5–6

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

Lines 8–12

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.

Lines 14–15

The viewstack() function displays a printable string representation of the list.

Lines 17–44

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.

Lines 46–47

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

							
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.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–6

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

Lines 8–12

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


Last updated on 9/14/2001
Core Python Programming, © 2002 Prentice Hall PTR

< BACKMake Note | BookmarkCONTINUE >

© 2002, O'Reilly & Associates, Inc.