6.14. Special Features of Lists

6.14.1. 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:

Listing 6.2. Using Lists as a Stack (stack.py)

1  #!/usr/bin/env python
2  
3  stack = []
4  
5  def pushit():
6      stack.append(raw_input('Enter new string: '))
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 str(stack)
16 
17 def showmenu():
18     prompt = """
19 p(U)sh
20 p(O)p
21 (V)iew
22 (Q)uit
23 
24 Enter choice: """
25 
26     done = 0
27     while not done:
28 
29          chosen = 0
30          while not chosen:
31             try:
32                  choice = raw_input(prompt)[0]
33             except (EOFError, KeyboardInterrupt):
34                  choice = 'q'
35             print 'nYou picked: [%s]' % choice
36             if choice not in 'uovq':
37                 print 'invalid option, try again'
38              else:
39                chosen = 1
40 
41        if choice == 'q': done = 1
42        if choice == 'u': pushit()
43        if choice == 'o': popit()
44        if choice == 'v': viewstack()
45 
46     if __name__ == '__main__':
47     showmenu()

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.

Listing 6.3. Using Lists as a Queue (queue.py)

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

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]

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