4.10. Linked Stacks¶
4.10.1. Linked Stack Implementation¶
The linked stack implementation is quite simple. Elements are inserted and removed only from the head of the list. Here is a visual representation for the linked stack.
class LinkedStack<E> implements Stack<E> {
private Node top; // Pointer to top of stack
private int stackSize; // Size of stack
LinkedStack() {
top = null;
stackSize = 0;
}
class LinkedStack(Stack):
def __init__(self):
self._top = None # Pointer to top of stack
self._stackSize = 0 # Size of stack
Stack nodes are exactly the same as the linked list nodes we saw earlier.
private class Node {
E elem; // Value for this node
Node next; // Pointer to next node in stack
Node(E elem, Node next) {
this.elem = elem;
this.next = next;
}
}
# Python does not have internal classes, so we have to make the stack node standalone.
class LinkedStackNode:
def __init__(self, elem, next):
self.elem = elem # Value for this node
self.next = next # Pointer to next node in stack
4.10.2. Linked Stack Pop¶
public E pop() {
if (!(stackSize > 0)) throw new NoSuchElementException("pop from empty stack");
Node removed = top;
top = removed.next;
removed.next = null; // For garbage collection
stackSize--;
return removed.elem;
}
def pop(self):
if not (self._stackSize > 0): raise IndexError("pop from empty stack")
removed = self._top
self._top = removed.next
removed.next = None # For garbage collection
self._stackSize -= 1
return removed.elem
4.10.3. Linked stacks: Full implementation¶
Here is the complete linked stack implementation.
class LinkedStack<E> implements Stack<E> {
private Node top; // Pointer to top of stack
private int stackSize; // Size of stack
LinkedStack() {
top = null;
stackSize = 0;
}
private class Node {
E elem; // Value for this node
Node next; // Pointer to next node in stack
Node(E elem, Node next) {
this.elem = elem;
this.next = next;
}
}
public void push(E x) {
top = new Node(x, top);
stackSize++;
}
public E peek() {
if (!(stackSize > 0)) throw new NoSuchElementException("peek from empty stack");
return top.elem;
}
public E pop() {
if (!(stackSize > 0)) throw new NoSuchElementException("pop from empty stack");
Node removed = top;
top = removed.next;
removed.next = null; // For garbage collection
stackSize--;
return removed.elem;
}
public boolean isEmpty() {
return stackSize == 0;
}
public int size() {
return stackSize;
}
public Iterator<E> iterator() {
return new LinkedStackIterator();
}
private class LinkedStackIterator implements Iterator<E> {
private Node current;
LinkedStackIterator() {
current = top;
}
public boolean hasNext() {
return current != null;
}
public E next() {
E x = current.elem;
current = current.next;
return x;
}
}
}
class LinkedStack(Stack):
def __init__(self):
self._top = None # Pointer to top of stack
self._stackSize = 0 # Size of stack
def push(self, x):
self._top = LinkedStackNode(x, self._top)
self._stackSize += 1
def peek(self):
if not (self._stackSize > 0): raise IndexError("peek from empty stack")
return self._top.elem
def pop(self):
if not (self._stackSize > 0): raise IndexError("pop from empty stack")
removed = self._top
self._top = removed.next
removed.next = None # For garbage collection
self._stackSize -= 1
return removed.elem
def isEmpty(self):
return self._stackSize == 0
def size(self):
return self._stackSize
def __iter__(self):
current = self._top
while current is not None:
yield current.elem
current = current.next
# Python does not have internal classes, so we have to make the stack node standalone.
class LinkedStackNode:
def __init__(self, elem, next):
self.elem = elem # Value for this node
self.next = next # Pointer to next node in stack
4.10.4. Comparison of Array-Based and Linked Stacks¶
All operations for the array-based and linked stack implementations
take constant time, so from a time efficiency perspective,
neither has a significant advantage.
Another basis for comparison is the total space
required.
The analysis is similar to that done for list implementations.
The array-based stack must allocate an array with more elements than actually needed, and
some of that space is wasted whenever the stack is not full.
The linked stack can shrink and grow but requires the overhead of a
next field for every element.
4.10.4.1. Implementing two stacks using one array¶
If you need to use two stacks at the same time, you can take advantage of the one-way growth of the array-based stack by using a single array to store two stacks. One stack grows inward from each end as illustrated by the figure below, hopefully leading to less wasted space. However, this only works well when the space requirements of the two stacks are inversely correlated. In other words, ideally when one stack grows, the other will shrink. This is particularly effective when elements are taken from one stack and given to the other. If instead both stacks grow at the same time, then the free space in the middle of the array will be exhausted quickly, and the array has to be resized.
