Many beginners hear “stack” and feel it is hard. It is not hard. It is simple and powerful. In this article, we learn what a stack is. We learn how it works. We learn the words push, pop, top, overflow, and underflow. We see stacks in real life and in code. We go step by step. We use very simple English. Each idea is short and clear. We give small programs in Java. We show time cost in a table. A “data structure” is a way to store data in a computer. An “abstract data type” or ADT is a set of allowed actions and rules. It hides how those actions work inside. A stack is one ADT. It has strict rules. We add and remove only at one end. That end is the top. The rule is LIFO. This means Last In, First Out. The last item put in comes out first. Think of a pile of plates. New plates go on the top. You take plates from the top. That is a stack. This simple rule solves many tasks. It helps undo in editors and function calls. It is a small tool with big use.

Stack – Introduction

Quick Crust: Read This If You Are In a Hurry

This section gives the idea in one place. A stack stores items with adds and removes at the top. The rule is LIFO (Last In, First Out). push means put an item on the top. pop means take the top item out. top (or peek) means look at the last pushed item. It does not remove it. Popping an empty stack is underflow. Pushing a full fixed array is overflow. These are exceptions. An exception is a special error that stops normal work. You can build a stack using an array, a growing array with doubling, or a linked list. A simple array is fast but its size is fixed. A dynamic array grows by making a bigger array and copying items. Doubling makes average push time constant. A linked list grows one node at a time. It needs no copying, but stores extra links. Stacks help with brackets, math expression work, and recursion. They power browser back and undo in editors. They also check tags in HTML and XML. With two indexes, we can make two stacks in one array. With shifting, we can make three or more stacks in one array. With recursion, we can reverse a stack. Most basic actions take O(1) time. Space for n items is O(n). These are the core ideas.

• Core rule: Last In, First Out (LIFO).
• Key actions: push, pop, top, size, isEmpty, isFull.
• Errors: underflow on empty pop/top, overflow on push to full fixed array.
• Build options: array, dynamic array with doubling, linked list.
• Uses: brackets, postfix, recursion, browser history, undo, HTML/XML tags.
• Time: most actions O(1); dynamic push average O(1) due to amortized analysis.
• Space: O(n) for n items.

What Is a Stack?

A stack is a very simple and strict data structure. A data structure is a planned way to store data. A stack is also an abstract data type (ADT). An ADT lists operations and rules. It hides inside details. In a stack, we keep items in an ordered list. Ordered means clear positions: first, next, and last. We insert and delete only at one end. This end is called the top. The last item inserted is removed first. This is Last In, First Out (LIFO). It is also called First In, Last Out (FILO). Think of a plate pile. You put a plate on the top. You take a plate from the top. That is a stack. We use two main words. Push inserts a new item at the top. Pop removes the item from the top. A push on a full fixed array is overflow. A pop or top on an empty stack is underflow. Overflow and underflow are exceptions. An exception is a special error we must handle. These rules make stacks predictable. They are easy to reason about. They help build many strong algorithms. They are used inside bigger data structures too.

How Stacks Are Used (Real-Life Analogy)

Let us use a simple story. Think of a developer at work. The developer works on task A. A manager gives urgent task B. The developer pauses A. A goes into a pending tray. That is a push. Now the developer works on B. The phone rings with task C. The developer pauses B. B is pushed to the tray. The developer answers C. When C ends, the developer takes the top task. That task is B. The developer resumes B. When B ends, the developer pops it and resumes A. This shows the LIFO rule. The last paused task resumes first. The tray is the stack. Each pause is a push. Each resume is a pop. If the tray is empty and you pop, nothing is there. That is underflow. If the tray has a hard limit and is full, one more push is overflow. This maps to code. Function calls use a call stack. A called function pushes its state. On return, the state is popped. This keeps programs correct and simple. The same idea helps browser back and editor undo.

• Start task A. No pending items.
• New urgent task B arrives. Push A to pending. Work on B.
• Phone call C happens. Push B to pending. Answer C.
• Call C ends. Pop and resume B.
• Task B ends. Pop and resume A.

Stack ADT: Operations and Exceptions

A stack as an ADT gives a small set of actions. An action is a thing you can do. We use integers for easy learning. Push(int data) adds a new integer to the top. int Pop() removes and returns the top integer. int Top() returns the top integer without removing it. This is also peek. int Size() returns how many items we have now. int IsEmptyStack() returns 1 if empty, else 0. int IsFullStack() returns 1 if a fixed array cannot take more, else 0. Now about an exception. An exception is a special error that is “thrown”. “Thrown” means normal flow stops and we must handle it. In a stack, Pop and Top cannot run on an empty stack. Doing Pop or Top then throws an underflow exception. Pushing into a full fixed array throws an overflow exception. We can catch and handle these exceptions. We can also check IsEmptyStack or IsFullStack first. This keeps code safe. Few actions and clear rules make stacks easy to test.

• Push(int data): insert data at the top.
• int Pop(): remove and return the last inserted element.
• int Top(): return the last inserted element without removing it.
• int Size(): return the number of stored elements.
• int IsEmptyStack(): return 1 if empty, else 0.
• int IsFullStack(): return 1 if full (for fixed array), else 0.

// Simple Stack ADT shape in Java
interface IntStack {
    void push(int data);        // add at top
    int pop();                  // remove from top
    int top();                  // read top without removing
    int size();                 // count items
    boolean isEmpty();          // true if size == 0
    boolean isFull();           // true only for fixed-size array stacks
}

Implementation Options

There are three common ways to build a stack. The first is a simple array. An array is a fixed block with indexes 0, 1, 2, etc. We keep a variable named top for the last item index. Push increases top and writes the value. Pop reads the value and decreases top. If the array is full, push is overflow. If the array is empty, pop is underflow. The second way is a dynamic array. It starts small and grows when full. We make a new array of double size and copy items. This copy is rare. So the average push time is constant. This average over many pushes is amortized time. The third way is a linked list. A linked list is a chain of nodes. Each node stores a value and a link. The top is the head node. Push adds a new head node. Pop removes the head node. A linked list grows one node at a time. It needs no big copies. It uses extra space for links. All three give O(1) time for push and pop in usual cases. Space for n items is O(n). Pick what fits: fixed size speed, smooth growth, or simple node adds.

Simple Array Stack: Code, Steps, and Costs

In a simple array stack, we decide a max size first. This size never changes later. We keep an integer top. We set top to -1 when empty. A push has two steps. First, check if top is at the last index. If yes, that is overflow. If no, increase top and write the data. A pop has two steps. First, check if top is -1. If yes, that is underflow. If no, read the value and decrease top. top() only reads the value and does not change top. size() returns top + 1. isEmpty() checks if top is -1. isFull() checks if top is capacity – 1. The good part is speed. All actions take O(1) time. The limit is the fixed size. You must guess the size first. Guess too small, you hit overflow. Guess too big, you waste memory. This method is great when the max count is known. It is easy to code and very fast in practice.

class ArrayStack implements IntStack {
    private final int[] data;
    private int top = -1; // -1 means empty

    public ArrayStack(int capacity) {
        data = new int[capacity];
    }

    public void push(int x) {
        if (isFull()) throw new RuntimeException("Overflow: stack is full");
        data[++top] = x; // increment top, then write
    }

    public int pop() {
        if (isEmpty()) throw new RuntimeException("Underflow: stack is empty");
        return data[top--]; // read then decrement top
    }

    public int top() {
        if (isEmpty()) throw new RuntimeException("Underflow: stack is empty");
        return data[top];
    }

    public int size() { return top + 1; }

    public boolean isEmpty() { return top == -1; }

    public boolean isFull() { return top == data.length - 1; }
}

• Advantages: very fast O(1) time, simple code, memory is cache friendly.
• Disadvantages: fixed maximum size, overflow can happen, no resizing.

Dynamic Array with Doubling: Code, Steps, and Costs

A dynamic array stack starts small and grows. We still use a top index. We still use an array. On push, if full, we double the size. We copy all old items to the new array. Then we insert the new item. The copy step is costly when it happens. But it is rare. It happens at sizes like 1, 2, 4, 8, 16, etc. So average push time stays constant. This average is amortized O(1). We spread the rare big cost over many cheap pushes. For 32 items, total copies are about 31. That is O(n) for n pushes. Pop and top are still O(1). You may shrink on many pops. Shrink too often can cause thrashing. Many libraries only grow. Note: many doublings can fail if memory is low. Handle out-of-memory too. This method is best when size is unknown. It gives smooth growth with few limits.

class DynamicArrayStack implements IntStack {
    private int[] data = new int[1];
    private int top = -1;

    public void push(int x) {
        if (isFull()) grow();
        data[++top] = x;
    }

    private void grow() {
        int newCap = Math.max(1, data.length * 2);
        int[] newData = new int[newCap];
        System.arraycopy(data, 0, newData, 0, data.length);
        data = newData;
    }

    public int pop() {
        if (isEmpty()) throw new RuntimeException("Underflow: stack is empty");
        return data[top--];
    }

    public int top() {
        if (isEmpty()) throw new RuntimeException("Underflow: stack is empty");
        return data[top];
    }

    public int size() { return top + 1; }

    public boolean isEmpty() { return top == -1; }

    // In dynamic stacks, "full" means current array is filled, but we can grow.
    public boolean isFull() { return top == data.length - 1; }
}

• Advantages: grows as needed, avoids overflow, average push is O(1).
• Disadvantages: rare copy cost, can hit memory limits, code is a bit harder.

Linked List Stack: Code, Steps, and Costs

A linked list stack uses nodes. A node stores a value and a link to next. A reference is a pointer to another node. We keep head as the top. On push, make a new node. Set its next to head. Move head to this node. On pop, read head’s value. Move head to head.next. The old head is freed later. top reads head’s value. size can be tracked in a counter. Or we can count by walking the list. There is no fixed size and no copying. It grows one node at a time. Each operation is O(1) on average. The trade-off is extra space for links. Cache use is also worse than arrays. DeleteStack is O(n) if we free nodes by hand. With garbage collection, it is automatic. This method is great for unbounded growth and many pushes and pops. It avoids bulk copies when size changes a lot.

class LinkedListStack implements IntStack {
    private static class Node {
        int val;
        Node next;
        Node(int v, Node n) { val = v; next = n; }
    }
    private Node head = null;
    private int count = 0;

    public void push(int x) {
        head = new Node(x, head);
        count++;
    }

    public int pop() {
        if (isEmpty()) throw new RuntimeException("Underflow: stack is empty");
        int v = head.val;
        head = head.next;
        count--;
        return v;
    }

    public int top() {
        if (isEmpty()) throw new RuntimeException("Underflow: stack is empty");
        return head.val;
    }

    public int size() { return count; }

    public boolean isEmpty() { return head == null; }

    public boolean isFull() { return false; } // linked list has no fixed limit unless memory is exhausted
}

• Advantages: grows and shrinks smoothly, O(1) ops, no big copies.
• Disadvantages: extra memory per node, less cache friendly, more pointer work.

Comparing Implementations

Let us compare the three methods. The array stack is constant time and very simple. It is great for speed and a known limit. But it cannot grow. Push beyond capacity causes overflow. The dynamic array with doubling grows when needed. It copies items only sometimes. Growth at 1, 2, 4, 8, etc keeps total copy O(n). So average push is amortized O(1). We spread rare big costs over many small ones. The linked list stack adds and removes at the head. It never copies many items at once. Every operation is O(1). It uses extra space for links but grows well. Do not grow by +1 each time. That is very slow. Total time becomes O(n^2) for n pushes. Use doubling instead. If your data fits a known bound, use a fixed array. If size is unknown, choose dynamic array or linked list. If you need tight space per item, prefer arrays. If you must avoid big copies, prefer linked lists.

• Array: O(1) ops, but fixed size. Overflow can happen. No growth.
• Dynamic array (doubling): average O(1) push, rare O(n) copy on grow, flexible size.
• Linked list: O(1) ops, grows/shrinks one node at a time, extra pointer space.
• Incremental growth by +1: avoid it, total time is O(n^2) for n pushes.

Classic Applications of Stacks

Stacks solve many common problems in a clean way. A key one is balancing of symbols. Symbols are (), {}, and []. Push opens and pop on closes. If all match and end empty, it is balanced. Another core use is infix to postfix and postfix evaluation. Infix is A + B. Postfix is A B +. Stacks hold operators and help order. Function calls and recursion use a system stack. It stores local state and return data. On call, state is pushed. On return, state is popped. Stock span uses a stack for recent prices. A browser back uses a stack of pages. Press back to pop a page. Undo in editors stores edits on a stack. Press undo to pop the last change. HTML and XML tag matching uses a stack for open and close tags. Stacks also help with tree traversals. Two stacks can also simulate a queue. These ideas run in real tools every day.

• Direct applications: balancing brackets, infix-to-postfix conversion, postfix evaluation, function calls and recursion, stock span, browser back history, undo in editors, HTML/XML tag matching.
• Indirect applications: helper for tree traversals, component inside other structures, simulating queues with two stacks.

Worked Examples and Step-by-Step Guides

Now we learn by small steps. Each move is clear. First, balancing of symbols. Read the string left to right. On ‘(’, ‘{’, or ‘[’, push it. On ‘)’, ‘}’, or ‘]’, check the top. If types match, pop. If not, it is not balanced. If stack is empty when closing, not balanced. At the end, empty stack means balanced. Second, palindrome check with a stack. Read until marker X. Push the first half. Then read the second half. Compare each character with the stack top. If all match and stack ends empty, it is a palindrome. Third, reverse a stack with recursion. Pop all items until empty. On return, insert each saved item at the bottom. This reverses the order. Fourth, two stacks in one array. Use two indexes. Left grows right. Right grows left. They meet only when full. Fifth, three stacks in one array. Keep base and top for the middle stack. Shift the middle when it collides. Sixth, m stacks in one array. Split the array into m regions and shift neighbors on need. These ideas show stack flexibility. They teach clean boundary checks and clear steps.

Balancing of Symbols: Steps

• Step 1: Create an empty stack.
• Step 2: Traverse the input string from left to right.
• Step 3: If the character is ‘(’, ‘{’, or ‘[’, push it.
• Step 4: If the character is ‘)’, ‘}’, or ‘]’, check if the stack is empty. If empty, not balanced.
• Step 5: If not empty, compare the top. If types match, pop. If not, not balanced.
• Step 6: After the loop, if the stack is empty, it is balanced. Else, not balanced.

Palindrome Using Stack: Steps

• Step 1: Traverse until marker X. Push each element onto the stack.
• Step 2: Continue reading after X. For each element, compare with stack top.
• Step 3: If same, pop and continue. If different, it is not a palindrome.
• Step 4: If at end the stack is empty, it is a palindrome.
• Time Complexity: O(n); Space Complexity: O(n/2) ≈ O(n).

Reverse a Stack Using Only Push and Pop: Steps

• Step 1: If stack is empty, return.
• Step 2: Pop top element and hold it.
• Step 3: Recursively reverse the remaining stack.
• Step 4: Insert the held element at the bottom. Pop all, push held, then push others back.
• Time Complexity: O(n^2); Space Complexity: O(n) for recursion.

Two Stacks in One Array: Steps

• Step 1: Left top starts at -1. Right top starts at n.
• Step 2: Push left by ++leftTop and write. Push right by –rightTop and write.
• Step 3: Pop left by returning data[leftTop–]. Pop right by returning data[rightTop++].
• Step 4: If leftTop + 1 == rightTop, array is full; both pushes stop.
• Time Complexity for push/pop: O(1); Space Overhead: O(1).

Three Stacks in One Array: Idea and Steps

• Step 1: Keep base and top indexes for each stack. Let middle shift when needed.
• Step 2: If left push collides with middle, try shifting middle right.
• Step 3: If right push collides with middle, try shifting middle left.
• Step 4: If middle push collides with right, shift middle left; if with left, shift right.
• Step 5: Popping needs no shifting; just adjust top.
• Time Complexity: push worst-case O(n) due to shifts; pop O(1); Space Overhead: O(1).

Step-by-Step: How Each Function Works in a Stack

Now we explain each action in small steps. This helps coding and debugging. For Push(x), step 1 is capacity check. In a fixed array, if top is last index, throw overflow. In a dynamic array, if full, grow first. Step 2: increment top and store x at data[top]. Step 3: update size if you track it. For Pop(), step 1 is empty check. If top is -1 or head is null, throw underflow. Step 2: read the top value. Step 3: decrement top or move head to head.next. Step 4: update size if tracked. For Top(), step 1: check empty. Step 2: read the top value without changes. For Size(), return top + 1 or the tracked count. For IsEmpty(), return true if top == -1 or head == null. For IsFull() in a fixed array, return true if top == capacity – 1. In dynamic arrays or linked lists, isFull is false unless memory is gone. For exceptions, you can throw or return a code. Throwing is safer and clearer. Keep steps small and clear. Add tests for many pushes and pops. Test underflow and overflow. Test edge sizes 0 and 1. Then your stack is robust and ready.

• Push: check capacity, grow if needed, ++top, write value.
• Pop: check empty, read value, –top or move head, return value.
• Top: check empty, read value, do not change state.
• Size: return count (top + 1 or tracked variable).
• IsEmpty: check top == -1 or head == null.
• IsFull: check top == capacity – 1 (fixed array only).

Time Complexity Summary Tables

Here we group time costs for quick reference. Time complexity shows how run time grows with n. Space complexity shows how memory use grows with n. O(1) means constant time. O(n) means time grows with item count. Amortized O(1) means average time per operation is constant. Some single operations can be slower sometimes. These tables help you choose the right method. If you want fast and simple and know the max size, use a fixed array. If you need auto growth and mostly push and pop, use a dynamic array. If size changes a lot and you want no bulk copies, use a linked list. Remember: Big-O can be the same, but constants matter. Arrays are usually more cache friendly than lists.

Examples: Small Java Demo

Below is a small demo using ArrayStack. We create a stack of size 5. We push three numbers. We read the top. We pop two numbers. We print the size. These steps match the rules you learned. The code throws exceptions on underflow and overflow. In a real app, you would catch them where you call. Try to run and change numbers. Push more than five to see overflow. Pop from empty to see underflow. Watch size after each action. This builds a clear LIFO model in your mind.

public class StackDemo {
    public static void main(String[] args) {
        ArrayStack st = new ArrayStack(5);
        st.push(10);
        st.push(20);
        st.push(30);
        System.out.println("Top: " + st.top()); // 30
        System.out.println("Pop: " + st.pop()); // 30
        System.out.println("Pop: " + st.pop()); // 20
        System.out.println("Size: " + st.size()); // 1
        System.out.println("Is Empty: " + st.isEmpty()); // false
    }
}

Troubleshooting and Tips

Use these checks to avoid common bugs. Always set top to -1 for arrays. This marks empty state. For dynamic arrays, check full before writing. Call grow if needed. For linked lists, check head is null before reads. On pop, always decrement top or move head. Use IsEmpty before pop and top. For fixed arrays, use IsFull before push. If indexes fail, check math around capacity – 1. If dynamic arrays feel slow, be sure you double. Do not grow by +1 each time. That gives O(n^2) total time. If memory is high with lists, remember node links add cost. For many small ints, prefer arrays. Add tests for empty, single, full, and mixed cases. Log steps while learning. Keep names short and clear. Keep checks simple and early. This builds reliable stack code and avoids tricky bugs.

• Initialize top = -1 (array) or head = null (list).
• Check isEmpty() before pop/top; check isFull() before push in fixed arrays.
• Prefer doubling over +1 growth to avoid O(n^2) behavior.
• Use arrays for tight memory and cache speed; use linked lists to avoid bulk copying.
• Add tests for underflow/overflow and edge cases 0, 1, and capacity sizes.