CSE 274 Chapter 6: Stack Implementations
4 Oct 2018
School
Department
Course
Professor
Document Summary
A linked implementation: stack implementations will implement fastest if first node in chain references the top entry in stack. Outline of class: topnode field is head reference to chain of nodes, set to null by default constructor, just linked the linked bag, the private class node will be defined within linkedstack. Adding to the top: first allocate new node that references stack"s existing chain, then, the topnode entry is set to the newnode. Retrieving the top: access the data portion that is in the first node in the chain, this is an o(1) operation, if the stack is empty, peek() throws exception. And if it needs to grow past the size of the array, you will have to copy and create more. Outline: data: array of stack entries, index to topentry, constructor: default creates array with default capacity, other lets client choose capacity, topindex is set to -1 so that when you add a value, you can simply increment it.
