Course navigation & on this page
Fixed-capacity string stack
Use an array and an item count to implement the stack discipline.
Overview
Use an array and an item count to implement the stack discipline. Each operation accesses a constant number of entries and updates the count. The allocated array size is fixed independently of the number of occupied entries.
Step-by-step walkthrough
- Allocate the requested array capacity.
- Push stores an item at the next free index.
- Pop returns the last occupied item.
- Keep the count consistent with the occupied prefix.
Complexity analysis
| Best case | Θ(1) push/pop |
|---|---|
| Average / aggregate | Θ(1) push/pop |
| Worst case | Θ(1) valid push/pop |
| Space | Θ(capacity) |
Each operation accesses a constant number of entries and updates the count. The allocated array size is fixed independently of the number of occupied entries.
A worked example
With capacity 3, pushing A then B leaves two occupied entries; popping returns B.
Common mistake / implementation note
Capacity and current size are different. Inspect the original code’s behavior at overflow and underflow rather than assuming it resizes.
Capacity and current size are different. Inspect the original code’s behavior at overflow and underflow rather than assuming it resizes.
Original course code
Source: code/FixedCapacityStackOfStrings.java. Original logic, comments, variable names and attribution are retained.
Download FixedCapacityStackOfStrings.javaFixedCapacityStackOfStrings.javaJAVA
/****************************************************************************** * Compilation: javac FixedCapacityStackOfStrings.java * Execution: java FixedCapacityStackOfStrings * Dependencies: StdIn.java StdOut.java * * Stack of strings implementation with a fixed-size array. * * % more tobe.txt * to be or not to - be - - that - - - is * * % java FixedCapacityStackOfStrings 5 < tobe.txt * to be not that or be * * Remark: bare-bones implementation. Does not do repeated * doubling or null out empty array entries to avoid loitering. * ******************************************************************************/ import java.util.Iterator;import java.util.NoSuchElementException; public class FixedCapacityStackOfStrings implements Iterable<String> { private String[] a; // holds the items private int n; // number of items in stack // create an empty stack with given capacity public FixedCapacityStackOfStrings(int capacity) { a = new String[capacity]; n = 0; } public boolean isEmpty() { return n == 0; } public boolean isFull() { return n == a.length; } public void push(String item) { a[n++] = item; } public String pop() { return a[--n]; } public String peek() { return a[n-1]; } public Iterator<String> iterator() { return new ReverseArrayIterator(); } // an array iterator, in reverse order public class ReverseArrayIterator implements Iterator<String> { private int i = n-1; public boolean hasNext() { return i >= 0; } public String next() { if (!hasNext()) throw new NoSuchElementException(); return a[i--]; } } public static void main(String[] args) { int max = Integer.parseInt(args[0]); FixedCapacityStackOfStrings stack = new FixedCapacityStackOfStrings(max); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) stack.push(item); else if (stack.isEmpty()) StdOut.println("BAD INPUT"); else StdOut.print(stack.pop() + " "); } StdOut.println(); // print what's left on the stack StdOut.print("Left on stack: "); for (String s : stack) { StdOut.print(s + " "); } StdOut.println(); }}