Example: Stack

The stack is a list-like structure in which elements may be inserted or removed from only one end. Therefore, it enforces last-in–first-out (LIFO) behavior on the list. Think of a stack of dishes at the salad bar. When you put a dish on the stack, it goes onto the top of the stack. When you remove a dish from the stack, it comes from the top of the stack.

Image From Java, Java, Java: Object-Oriented Problem Solving, 2022E

The stack operations are conventionally called push, for insert, and pop, for remove, respectively. Thus, the stack ADT stores a list of data and supports the following operations:

• Push—inserts an object onto the top of the stack.
• Pop—removes the top object from the stack.
• Empty—returns true if the stack is empty.
• Peek—retrieves the top object without removing it.

Stacks are useful for a number of important computing tasks. For example, during program execution, method call and return happens in a LIFO fashion. When a program is executed, the runtime system uses a call stack to execute its functions or methods. Roughly speaking, the call stack maintains all the active methods awaiting execution. The method at the top of the stack is the next one to execute. When a method (the caller) in execution calls another method (the callee), the caller has to suspend its execution until the callee returns. Therefore, the runtime system pushes the caller to the top of the stack and executes the callee. When the callee returns, the system pops the stack and resumes the execution of the caller. The Exception.printStackTrace() method uses the run-time stack to print a trace of the method calls that led to an exception.

While the restrictions on how elements are added to and removed from stacks makes them less flexible than lists, it also makes stacks both efficient (for those operations they can do) and easy to implement. Many applications require only the limited form of insert and remove operations that stacks provide. In such cases, it is more efficient to use the simpler stack data structure rather than the generic list.

Java’s Stack Class

The Stack class is much simpler than the LinkedList or the ArrayList class. You can find a detailed description of

the Stack<E> class in the javadocs. Below we summarize the important methods of the class.

• E push(E e). Adds the specified element to the top of the stack and returns the added element.
• E pop(E e). Removes and returns the element at the top of the stack. The method throws an EmptyStackException if the stack is empty.
• E peek(E e). Returns the element at the top of the stack without removing it. The method throws an EmptyStackException if the stack is empty.
• boolean addAll(Collection<? extends E> c). Adds all the elements of the specified collection to the stack in the order defined by the collection’s iterator, and returns true if all the elements are successfully added. The method throws a NullPointerException if the specified collection is null.
• int size(). Returns the size of the stack, i.e. the number of elements in the stack.
• boolean empty(). Returns true if and only if the stack is empty (i.e. size() == 0).
• void clear(). Clears the stack.

The very simple code below shows how to create a Stack object and use its methods.

public class StackDemo {
	public static void main(String[] args) {
    	// Create a new stack
    	Stack<Integer> stack = new Stack();


    	// Add elements to the stack
    	for (int i = 1; i <= 6; i++) {
        	System.out.println("Pushing " + i);
        	stack.push(i);
    	}


    	System.out.println("Stack after elements are pushed: ");
    	System.out.println(stack);
    	System.out.println();


    	System.out.println("Popping the stack: ");
    	while (!stack.isEmpty()) {
        	System.out.print(stack.pop() + " ");
    	}
    	System.out.println();


    	System.out.println("Stack after popping: ");
    	System.out.println(stack);
    	System.out.println();
	}
}

The following is the output of the program, which demonstrates the LIFO nature of a stack

Integers 1 to 6 are added to the stack in this order. They come out in the reverse order due to the LIFO nature of

the stack. The following image from Wikipedia (https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) demonstrates the steps in the execution of the program.

Image attribution: By Vectorization: Alhadis – Own work based on: Lifo stack.png by Maxtremus, CC0, https://commons.wikimedia.org/w/index.php?curid=115938639

More Applications of Stacks

A curious reader may ask at this point why we care about the LIFO property and what nontrivial tasks we can accomplish with a stack. It turns out that stacks are surprisingly useful and powerful in programming despite their simplicity. Here we very briefly mention some important applications of stacks in nontechnical terms.

A stack is used to implement the undo function of applications such as Microsoft Word. The app pushes all the actions to a stack as they occur. When the user presses the undo button, the app pops the stack to undo the most recent action.

Stacks are commonly used to implement a fundamental algorithm known as Depth First Search (DFS) that you will learn in a future class. Among many other applications, DFS is crucial for uncovering important properties and structures of large, sophisticated computer or social networks. It is used, for example, by search engines to crawl the Web.

Yet another application is parsing in program compilation. When the source code of a program is compiled, the parser of the compiler uses a stack to parse the expressions and statements in the code for syntax errors.