Introduction to Stack ADT

In computer science, a Stack is an abstract data type (ADT) that serves as a collection of elements, with two principal operations:

1. Push: Adds an item to the top of the stack.
2. Pop: Removes the item from the top of the stack.

A Stack follows the LIFO (Last In, First Out) principle. This means the last item inserted will be the first item removed. It is similar to a deck of cards where you can only access the top card.

Why is Stack ADT Important?

The Stack ADT is a fundamental concept in computer science because it forms the basis for many system-level functionalities, including:

1. Function call management (Call Stack)
2. Undo operations in text editors
3. Browser history management
4. Recursion handling

The Stack ADT can be implemented using:

• Array-based stack
• Linked list-based stack

Stack Operations

Push Operation

The Push operation is used to insert a new element on the top of the stack.

Example:

• Push(10)
• Push(20)
• Push(30)

Stack now looks like:

30 <- Top
20
10

Pop Operation

The Pop operation removes the topmost element from the stack.

Example:

• Pop() -> Removes 30
• Pop() -> Removes 20

Stack now looks like:

10 <- Top

Peek Operation

The Peek operation returns the topmost element without removing it from the stack.

Example:

• Peek() -> Returns 10
• Stack remains unchanged

Stack Memory vs Heap Memory

What is Stack Memory?

Stack Memory is a region in Random Access Memory (RAM) that stores local variables, method calls, and function call references.

• Fast access: Stack memory is fast because memory is allocated and deallocated automatically.
• Small size: It has a fixed small size, generally limited.
• Stores function calls and local variables.

What is Heap Memory?

Heap Memory is also a region in RAM where dynamically allocated objects are stored.

• Large size: Heap memory is larger than stack memory.
• Slow access: Accessing data from heap is slower than stack.
• Holds objects, arrays, and reference data.

Stack Frame in Stack Memory

What is a Stack Frame?

A Stack Frame is a block of memory in the stack that stores:

• Method parameters
• Local variables
• Return address

Every time a function/method is called, a stack frame is created. When the function ends, the stack frame is automatically destroyed.

Function Call Flow in Stack Memory

Let’s understand how stack memory works with a function call.

Example Code

public class StackExample {
   public static void main(String[] args) {
      function1();
   }

   static void function1() {
      int a = 10;
      function2();
   }

   static void function2() {
      int b = 20;
      function3();
   }

   static void function3() {
      int c = 30;
   }
}

Stack Memory Flow

1. function1() is called → Stack Frame for function1 is created.
2. function2() is called → Stack Frame for function2 is created.
3. function3() is called → Stack Frame for function3 is created.
4. function3() finishes → Stack Frame is removed.
5. function2() finishes → Stack Frame is removed.
6. function1() finishes → Stack Frame is removed.

Objects in Heap Memory

When we create an object using new keyword, it is stored in the Heap Memory.

Example Code

public class House {
   int windows;
   int doors;

   public House(int windows, int doors) {
      this.windows = windows;
      this.doors = doors;
   }

   public static void main(String[] args) {
      House myHouse = new House(5, 10);
   }
}

Memory Allocation

• Heap Memory: The House object is stored in heap.
• Stack Memory: The reference myHouse is stored in stack.

Garbage Collection

What is Garbage Collection?

Garbage Collection (GC) is an automatic process of freeing up memory from unused objects in the heap.

Example

House house1 = new House(5, 10);
House house2 = new House(6, 12);
house1 = null;  // Eligible for Garbage Collection

When house1 reference is set to null, the object is no longer accessible, making it eligible for garbage collection.

Stack Implementation with Linked List

Node.java

public class Node<T extends Comparable<T>> {

	private T data;
	private Node<T> nextNode;
	
	public Node(T data){
		this.data = data;
	}
	
	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public Node<T> getNextNode() {
		return nextNode;
	}

	public void setNextNode(Node<T> nextNode) {
		this.nextNode = nextNode;
	}

	@Override
	public String toString() {
		return this.data.toString();
	}
}

Stack.java

public class Stack<T extends Comparable<T>> {

	private Node<T> root;
	private int count;
	
	// O(1) constant time
	public void push(T newData){
		
		this.count++;
		
		if( this.root == null ){
			this.root = new Node<>(newData);
		}else{
			Node<T> oldRoot = this.root;
			this.root = new Node<>(newData);
			this.root.setNextNode(oldRoot);
		}
	}
	
	
	public int size(){
		return this.count;
	}
	
	
	public T pop(){
		T itemToPop = this.root.getData();
		this.root = this.root.getNextNode();
		this.count--;
		return itemToPop;
	}

	
	public boolean isEmpty(){
		return this.root == null;
	}
}

App.java

public class App {

	public static void main(String[] args) {
		
		Stack<Integer> stack = new Stack<>();
		
		stack.push(10);
		stack.push(20);
		
		System.out.println(stack.pop());
		
		System.out.println(stack.size());
		
		System.out.println(stack.pop());
		
		System.out.println(stack.isEmpty());

	}

}

Stack implementation with Array

Stack.java

public class Stack<Item> {

	private Item[] stack;
	private int numberOfItems;
	
	public Stack(){
		this.stack = ( Item[] ) new Object[1];
	}

	public void push(Item item){
		
		if( numberOfItems == this.stack.length ){
			resize(2*this.stack.length);
		}
		
		this.stack[numberOfItems++] = item;
	}
	
	public Item pop(){
		Item itemToPop = this.stack[--numberOfItems];
		
		if( numberOfItems > 0 && numberOfItems == this.stack.length/4 ){
			resize(this.stack.length/2);
		}
		
		return itemToPop;
	}
	
	public boolean isEmpty(){
		return this.numberOfItems == 0;
	}
	
	public int size(){
		return this.numberOfItems;
	}

	// O(n)
	private void resize(int capacity) {
		
		Item[] stackCopy = ( Item[] ) new Object[capacity];
		
		for(int i=0;i<numberOfItems;i++){
			stackCopy[i]=this.stack[i];
		}
		
		this.stack = stackCopy;
	}
}

App.java

public class App {

	public static void main(String[] args) {
		
		Stack<String> stack = new Stack<>();
		
		stack.push("Roger");
		stack.push("James");
		
		System.out.println(stack.size());
		
		System.out.println(stack.pop());

		System.out.println(stack.size());
		
	}

}

Stack in Java

public class Stack<E>
extends Vector<E>

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.

When a stack is first created, it contains no items.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

Deque<Integer> stack = new ArrayDeque<Integer>();