CP164 Study Guide - Final Guide: Popping
Linked Stack Implementation
Pop
Popping an item from a linked stack means extracting the value from the top node then removing
that node. The stack's _top pointer must now point to the next node in the stack. This is easy: get
the current top node's link to its next node by referring to its _next attribute, then making that
node the new top. This is the reverse of push.
Popping a Node
def pop(self):
"""
-------------------------------------------------------
Pops and returns the top of stack.
Use: data = s.pop()
-------------------------------------------------------
Postconditions:
returns
data - the data at the top of the stack - the data is
removed from the stack (?)
-------------------------------------------------------
"""
assert self._top is not None, "Cannot pop from an empty stack"
data = self._top._data
self._top = self._top._next
return data
Is there a special case for when the last node is removed? No. The _top attribute is set to the
value of the _next attribute of the last node in the stack, which is None, and the stack becomes
empty again.
Moving Nodes
Combine
You were asked to write two different ways to combine two stacks into one. One version
required a function that used the ADT methods to combine the stacks. Because the ADT
methods look identical from the outside for both the array-based and linked
implementations of the stack, that version could use the linked stack representation
without change - you would simply import the linked implementation of the stack rather
than the array-based implementation.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Popping an item from a linked stack means extracting the value from the top node then removing that node. The stack"s _top pointer must now point to the next node in the stack. This is easy: get the current top node"s link to its next node by referring to its _next attribute, then making that node the new top. The _top attribute is set to the value of the _next attribute of the last node in the stack, which is none, and the stack becomes empty again. You were asked to write two different ways to combine two stacks into one. One version required a function that used the adt methods to combine the stacks. The second approach involved extending the adt by adding an method the worked at the class level to combine two stacks into one. Although the method signatures (the def lines of the methods) are identical, the implementation details of the two stacks are radically different.
