CP164 Study Guide - Midterm Guide: Data Element, Init
The Linked Stack Implementation
The Stack Class
A linked Stack is initialized with:
class Stack:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty stack. Data is stored in a linked structure.
Use: s = Stack()
-------------------------------------------------------
Postconditions:
Initializes an empty stack.
-------------------------------------------------------
"""
self._top = None
return
The stack initialization is simple: the private attribute _top points to the first _StackNode in
the stack. Because the stack is empty, it contains no_StackNode objects, thus _top is set
to None. The real work comes in pushing a node onto or popping a node from a stack.
(Defining the empty method is trivial and left as an exercise to the student.)
An Empty Linked Stack
Push
def push(self, data):
"""
-------------------------------------------------------
Pushes a copy of data onto stack.
Use: s.push(data)
-------------------------------------------------------
Preconditions:
data - a data element (?)
Postconditions:
a copy of data is added to the top of the stack.
-------------------------------------------------------
"""
self._top = _StackNode(data, self._top)
return
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
A linked stack is initialized with: class stack: def __init__(self): Initializes an empty stack. self. _top = none return. The stack initialization is simple: the private attribute _top points to the first _stacknode in the stack. Because the stack is empty, it contains no_stacknode objects, thus _top is set to none. The real work comes in pushing a node onto or popping a node from a stack. (defining the empty method is trivial and left as an exercise to the student. ) Postconditions: a copy of data is added to the top of the stack. self. _top = _stacknode(data, self. _top) return push creates a new _stacknode object and adds a value to it. The _next link of the _stacknode object is set to point to the "old" top of the stack, which in this case is none - there was no node already stored in the stack. The "new" top of the stack is set to point to this new node.