Operation Top is end-of-list Top is front-of-list Top is front-of-list
Pop top = stack[-1];
del stack[-1]top = stack[0];
del stack[0]top = stack[0];
stack[:1] = []Even more conveniently, Python grew a list pop method later in its life designed to be
used in conjunction with append to implement stacks and other common structures
such as queues, yielding the even simpler coding options listed in Table 18-2.
Table 18-2. Stacks as lists, coding alternatives
Operation Top is end-of-list Top is front-of-list
New stack=['a', 'b'] stack=['b', 'a']
Push stack.append('c') stack.insert(0,'c')
Pop top = stack.pop() top = stack.pop(0)By default, pop is equivalent to fetching, and then deleting, the last item at offset −1.
With an argument, pop deletes and returns the item at that offset—list.pop(-1) is the
same as list.pop(). For in-place change operations like append, insert, del, and pop,
no new list is created in memory, so execution is quick (performance may further de-
pend upon which end is the “top,” but this in turn depends on Python’s current list
implementation, as well as measurement concepts we’ll explore later). Queues can be
coded similarly, but they pop at the other end of the list.
Other built-in coding schemes are possible as well. For instance, del stack[:1] is yet
another way to delete the first item in a list-based stack in-place. Depending on which
end is interpreted as the top of the stack, the following sequence assignment statement
forms can be used to fetch and remove the top item as well, albeit at the cost of making
a new list object each time:
# top is front of list
top, stack = stack[0], stack[1:] # Python 1.X+
top, *stack = stack # Python 3.X# top is end of list
stack, top = stack[:-1], stack[-1] # Python 1.X+
*stack, top = stack # Python 3.XWith so many built-in stack options, why bother implementing others? For one thing,
they serve as a simple and familiar context for exploring data structure concepts in this
book. More importantly, though, there is a practical programming motive here. List
representations work and will be relatively fast, but they also bind stack-based pro-
grams to the stack representation chosen: all stack operations will be hardcoded
throughout a program. If we later want to change how a stack is represented or extend
its basic operation set, we’re stuck—every stack-based program will have to be updated,
and in every place where it accesses the stack.
Implementing Stacks| 1361