Stacks are a basic idea in data structures, which are ways to store and organize data so we can use it fast and in a clean way, and in this guide you will learn what a stack is with very simple words and friendly examples while still keeping the facts correct, and you will see words like push, pop, top, underflow, overflow, LIFO, and ADT explained in plain language, and you will also see where stacks show up in real life and in code, and you will learn how to build a stack with an array, with a growing dynamic array, and with a linked list, and you will look at errors and exceptions and time complexity in easy tables, and you will read step-by-step examples and short code, and you will compare pros and cons, and you will even peek at an advanced idea where many stacks share one array, so if you are in a hurry you can read the short “crust” to get the big picture, and if you go slowly and follow the steps you will understand it well.

Stack Introduction: Learn It the Simple Way

Quick Crust: Read This If You Are In a Hurry

A stack is an ordered list where every add and every remove happens only at one end called the top, and the newest item always sits at the top like the top plate in a cafeteria pile, and when you add an item you push, and when you remove the top item you pop, and the rule is LIFO which means Last In, First Out just like plates where you put on the top and take from the top, and if you try to pop when there are no items that error is called underflow, and if the stack is full in a fixed array and you try to push one more that error is called overflow, and a stack is an ADT (Abstract Data Type) which means we name what actions exist and what they should do without saying how they are stored inside, and the main actions are push, pop, and top (or peek), and the helper actions are size, isEmpty, and sometimes isFull, and we can build a stack using a simple array, a dynamic array that doubles when full, or a linked list, where arrays are very fast but can fill up, dynamic arrays give very fast pushes on average, and linked lists grow and shrink freely until memory ends, and stacks help with matching symbols, parsing expressions, function calls and recursion, undo history, browser back, and many similar tasks, so keep the rule in mind that everything happens at the top and the last thing in is the first thing out.

What Is a Stack?

A stack is a simple data structure, which means it is a way to organize and store data so that common actions are quick and predictable, and a stack keeps items in an ordered list where the order matters because we always care most about the most recent item, and in a stack we add only at one end called the top and we also remove only from this same end, and adding a new item is called a push while removing the most recent item is called a pop, and because we always remove the most recent item the guiding rule is LIFO which stands for Last In, First Out and is also called FILO or First In, Last Out, and a cafeteria plate pile is an easy picture because new plates go on the top and you always take from the top, so the last plate added is the first plate taken, and if you try to pop when the stack has no items that is an underflow, and if the storage is full in a fixed array and you try to push one more that is an overflow, and these error cases are exceptions which are signals that say the requested action cannot be done right now, and stacks matter because they are easy to use, fast in practice, and fit many real tasks in programs and in daily life.

Core Words and Meanings

This section explains key words in simple and clear terms, and it will help if you read them slowly and keep them nearby: Data structure: a pattern to hold data so we can work with it quickly and safely; Stack: a list where we add and remove only at the top; Top: the current last item in the stack and the one we can remove next; Push: place a new item on the top; Pop: remove the item at the top; Top() or Peek: look at the top item without removing it; LIFO: last item in is the first item out, which is the key rule of stacks; Underflow: error when we pop or peek from an empty stack; Overflow: error when we push into a full fixed-size stack; ADT (Abstract Data Type): a clean list of allowed operations and their meaning without fixing the storage method; Time complexity: a way to talk about how long an action takes as the data grows, written with Big-O like O(1) for constant time or O(n) for linear time; Space complexity: how much extra memory a method uses; Array: a fixed block of memory with positions 0, 1, 2, and so on; Dynamic array: an array that can grow by making a bigger array and copying items; Linked list: a chain of nodes where each node holds a value and a link to the next node; Amortized: the average cost per operation across many operations.

How a Stack Works: Easy Analogies

Think about a plate pile in the cafeteria where fresh plates go on the top and people take plates from the top, and no one pulls a plate from the middle or the bottom because that would break the pile, and this is exactly how a stack acts, and now think about an office task list where you are doing one big task and your manager brings a new urgent task so you pause the big task and start the urgent one, and then the phone rings so the phone call becomes the new top task and you do it first, and when the call ends you return to the urgent task and finish that, and then you return to the big task, and this shows LIFO because the last thing that arrived is the first thing you finish, and in code the same thing happens with function calls where A calls B and B calls C so we must finish C first, then B, then A, and these stories make the rule feel natural because we use one end only, we put new things on top, we remove from the top, and we never grab from the middle.

Stack ADT and Operations

A stack as an ADT means we clearly define which actions exist and what each action should do while we do not fix how the items are stored inside, which keeps our thinking clean and our code flexible, and the main actions are Push(int data) to add a new item at the top, int Pop() to remove and return the top item, and int Top() to read the top item without removing it, and the helper actions are int Size() to return how many items are inside, boolean IsEmptyStack() to check if there are no items, and boolean IsFullStack() to check if no more items can be added in a fixed-size array, and we must handle exceptions because Pop and Top cannot run on an empty stack and should throw an exception, and in a fixed-size array Push cannot run on a full stack and should also throw an exception, and since an ADT describes the outside behavior we can choose any inside storage like arrays, dynamic arrays, or linked lists while keeping the same function names and the same behavior so that only the inside changes and user code stays the same.

• Push(int data): Insert data onto the top of the stack.
• int Pop(): Remove and return the last inserted (top) element.
• int Top(): Return the last inserted (top) element without removing it.
• int Size(): Return count of elements currently in the stack.
• boolean IsEmptyStack(): Return true if the stack has no elements.
• boolean IsFullStack(): Return true if the stack is full (mainly in fixed-size array design).

Implementation Options

We can build a stack in more than one way, and the most common choices are a simple array, a dynamic array with doubling, and a linked list, and a simple array stack keeps items in a fixed-size array and tracks the top index in a variable called top so that push moves the top forward and writes the value and pop reads the value and moves the top back, and this is very fast because all actions are constant time but the array can fill and cause overflow, and a dynamic array stack also uses an array but when full it makes a new bigger array, usually double the size, and copies items before pushing, which makes pushes very fast on average because the rare copy cost is spread out, and a linked list stack uses nodes where each node stores a value and a link to the next node, and the top points to the first node so push adds a node at the front and pop removes the front node, and this grows and shrinks smoothly without resizing while using extra memory for links, and your choice depends on how much you know about the size, how you want to use memory, and what speed trade-offs you accept.

Simple Array Based Stack

The simple array based stack is easy and fast because we create an integer array with a fixed size and keep an integer top that starts at -1 to mean empty, and when we push we first check if top is already at the last index which would mean the array is full and a push would cause overflow, and if there is space we add one to top and write the value at array[top], and when we pop we first check if top is -1 which means the stack is empty and a pop would cause underflow, and if not empty we read array[top], then we subtract one from top and return the value, and Top() or Peek() checks empty and if not empty reads array[top] without changing top, and Size() is top + 1 when top starts at -1, and IsEmptyStack() is true when top is -1, and IsFullStack() is true when top is capacity – 1, and all these are constant time, and the main limit is that we must pick the capacity first so too small causes overflow and too large wastes memory, which is fine when we know the maximum size or want a very simple memory plan.

class ArrayStack {
    private final int[] a;
    private int top; // index of the last inserted element; -1 means empty

    public ArrayStack(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("Capacity must be > 0");
        this.a = new int[capacity];
        this.top = -1;
    }

    public void push(int data) {
        if (isFull()) throw new IllegalStateException("Overflow: stack is full");
        a[++top] = data;
    }

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

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

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

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

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

Time and Space: Simple Array Stack

• Limitations:
  • Must fix a maximum size up front.
  • Overflow if you push beyond capacity.
  • Wasted space if you pick a capacity that is too large.

Dynamic Array with Doubling (Amortized O(1) Push)

A dynamic array stack removes the fixed limit by growing as needed while keeping the same simple top index idea, and the key trick is doubling where, when the array is full during a push, we make a new array that is twice as big, copy all items over, and then push the new value, and this copy is costly on that push but it does not happen often so over many pushes the average cost per push stays small which is called amortized O(1), and this is very practical when you do not know the final size, and many libraries use this idea, and you can also shrink when the stack gets small, for example when size drops below one quarter of capacity you can halve the capacity, but shrinking too often can cause resize thrashing so many designs only grow for simplicity, and exceptions still apply because Pop and Top on an empty stack throw underflow, and normally there is no IsFullStack because the stack can grow until memory ends, although a resize can fail if the system cannot find more memory.

class DynamicArrayStack {
    private int[] a;
    private int top; // -1 means empty

    public DynamicArrayStack() {
        this.a = new int[1];
        this.top = -1;
    }

    public void push(int data) {
        if (top == a.length - 1) {
            resize(a.length * 2); // double capacity
        }
        a[++top] = data;
    }

    public int pop() {
        if (isEmpty()) throw new IllegalStateException("Underflow: stack is empty");
        int val = a[top--];
        // Optional shrink: if size is <= 1/4 of capacity, halve it (keep min capacity 1)
        if (top + 1 > 0 && (top + 1) <= a.length / 4) {
            int newCap = Math.max(1, a.length / 2);
            resize(newCap);
        }
        return val;
    }

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

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

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

    private void resize(int newCap) {
        int[] b = new int[newCap];
        System.arraycopy(a, 0, b, 0, top + 1);
        a = b;
    }
}

Time and Space: Dynamic Array Stack

• Notes:
  • Doubling happens log n times over n pushes.
  • Total copy work over n pushes is O(n), so amortized push is O(1).
  • Too many doublings in low memory may throw memory exceptions.

Linked List Based Stack

A linked list stack uses nodes instead of an array where a node holds a value and a link to the next node, and the top points to the first node while the stack is empty when top is null, and to push we create a new node, set its next to the current top, and move top to this new node, and to pop we check if top is null which would be an underflow, and if not null we read top’s value, move top to top.next, and return the value, and Top() or Peek() reads top’s value without changing top, and Size() can be kept as a counter that we update on push and pop, and this design grows and shrinks smoothly without resizing or copying, and it does not overflow unless the whole system runs out of memory, and the trade-off is that each node uses extra memory for the link and there can be a tiny time overhead compared to a plain array read, but for many jobs it is still excellent.

class LinkedListStack {
    private static class Node {
        int data;
        Node next;
        Node(int d, Node n) { data = d; next = n; }
    }

    private Node top;
    private int size;

    public LinkedListStack() {
        top = null;
        size = 0;
    }

    public void push(int data) {
        top = new Node(data, top);
        size++;
    }

    public int pop() {
        if (isEmpty()) throw new IllegalStateException("Underflow: stack is empty");
        int val = top.data;
        top = top.next;
        size--;
        return val;
    }

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

    public int size() {
        return size;
    }

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

    public void deleteStack() {
        top = null;
        size = 0;
    }
}

Time and Space: Linked List Stack

Incremental Resizing vs Doubling (Amortized Analysis)

There are two classic ways to grow an array stack and the first is incremental growth where, each time the array is full, you make a new array with capacity plus one, copy all old items, and then push the new item, which looks simple but is very slow because the total work over n pushes is about 1 + 2 + 3 + … + n which is O(n²) so the amortized time per push is O(n), and the second way is doubling where, when the array is full, you make a new array that is twice the size, copy the old items once in a while, and then push the new item, and over n pushes the total copy work is O(n) so the amortized time per push is O(1), which is a huge win and is why most real systems use doubling even though a single resize can still fail if memory is too tight.

Common Exceptions and Error States

When we work with stacks we must handle errors in a clear and steady way, and the two main error states are underflow and overflow, where underflow happens when we call Pop() or Top() on an empty stack because there is nothing to remove or read so the correct action is to throw an exception that says the action cannot be done, and overflow happens when we call Push() on a fixed-size array stack that is already full so there is no room for the new item and an exception should be thrown, and in a dynamic array stack push does not overflow in normal logic because it resizes, but a resize can fail if the system cannot get more memory, so good code checks the state, documents what will happen on errors, and uses clear messages to keep bugs small and make the program easy to debug.

Applications of Stacks

Stacks appear in many direct and indirect uses, where a direct application means we use a stack exactly with the LIFO rule to store and get items, and an indirect application means a stack helps another algorithm or larger structure, and in code stacks help check balanced symbols like (), [], and {} in expressions, and they convert infix expressions to postfix and also help evaluate postfix, and they power function calls and recursion inside programming languages, and they help compute spans like the stock span problem, and in user interfaces a stack drives the browser Back button and the editor Undo feature, and in markup like HTML and XML stacks help match tags, and as an indirect tool stacks help with tree traversals, depth-first search, and the design of other structures such as simulating queues, because many tasks need us to remember “what we did last” and then come back to it, which is exactly what a stack remembers quickly and cleanly.

• Direct applications:
  • Balancing of symbols in code and math.
  • Infix-to-postfix conversion in expression parsing.
  • Evaluation of postfix expressions.
  • Implementing function call stacks and recursion.
  • Finding spans (for example, stock span problem).
  • Page-visited history in browsers (Back button).
  • Undo sequence in text editors.
  • Matching tags in HTML and XML.
• Indirect applications:
  • Auxiliary structure in algorithms (e.g., tree traversals, DFS).
  • Component inside other data structures (e.g., simulating queues).

Step-by-Step: What Happens During Push and Pop

This step list shows what happens in a basic array stack for push and pop in a way that is easy to follow, and for Push(x) we do Step 1 which is to check if the stack is full by seeing if top is at capacity – 1 and if it is full we throw overflow, and Step 2 is to move top forward by one, and Step 3 is to write x into a[top], and Step 4 is to finish with x now at the top, and for Pop() we do Step 1 which is to check if the stack is empty by seeing if top is -1 and if it is empty we throw underflow, and Step 2 is to read v = a[top], and Step 3 is to move top back by one, and Step 4 is to return v which makes the next item become the new top, and for Top() or Peek() we do Step 1 which is to check empty and throw underflow if empty, and Step 2 which is to read v = a[top], and Step 3 which is to return v without changing top, and all these actions are O(1) which means their time does not depend on how many items are in the stack, and the checks before moving top are very important because they keep your stack safe.

1. Push(x):
   1. Check overflow condition.
   2. Increment top.
   3. Write x at array[top].
   4. Finish.
2. Pop():
   1. Check underflow condition.
   2. Read array[top] into a variable.
   3. Decrement top.
   4. Return the read value.
3. Top():
   1. Check underflow condition.
   2. Read array[top].
   3. Return it without changing top.

Java Examples with Step-by-Step Function Notes

Below are short Java examples for each implementation along with simple notes on how the main methods behave, and for the ArrayStack the push method first checks space with isFull and throws overflow if full, and if not full it increases top and stores the value, while pop checks isEmpty and throws underflow if empty, and otherwise reads the value, decreases top, and returns the value, and top is a safe read that does not change the stack, and for the DynamicArrayStack, push checks if top is at the last index and if yes it doubles capacity by calling resize which makes a new array and copies items, and then it pushes like before, and pop reads the value, moves top back, and can optionally shrink, and for the LinkedListStack, push makes a new Node whose next is the current top and then moves top to that node, and pop reads top.data, moves top to top.next, and returns the data, and these actions are O(1) except when a resize happens in the dynamic array, so read the code slowly and then read the step lists again and try running the code to see the flow happen.

// Step-by-step demo using the three stacks
public class StackDemo {
    public static void main(String[] args) {
        ArrayStack s1 = new ArrayStack(3);
        s1.push(10); // top = 0
        s1.push(20); // top = 1
        s1.push(30); // top = 2
        // s1.push(40); // would throw overflow

        System.out.println(s1.top()); // 30
        System.out.println(s1.pop()); // 30
        System.out.println(s1.size()); // 2

        DynamicArrayStack s2 = new DynamicArrayStack();
        for (int i = 1; i <= 8; i++) s2.push(i); // triggers resizes at 1,2,4...
        System.out.println(s2.top()); // 8
        System.out.println(s2.pop()); // 8
        System.out.println(s2.size()); // 7

        LinkedListStack s3 = new LinkedListStack();
        s3.push(100);
        s3.push(200);
        s3.push(300);
        System.out.println(s3.top()); // 300
        System.out.println(s3.pop()); // 300
        System.out.println(s3.size()); // 2
    }
}

Advanced Variation: Many Stacks Inside One Array

Sometimes we want to keep several stacks inside a single array to save space and keep data together, and a simple plan is to split the array into equal parts with one part per stack and to use two helper arrays where Base[i] stores the start of the i-th stack’s part and Top[i] stores the current top index for that stack, and stack i is empty if Base[i] == Top[i] and is full if Top[i] == Base[i+1] because it has grown to meet the next stack’s start, and to push into stack i we first check if it is full and if it is full we try to shift stacks on the right to the right or stacks on the left to the left to make space, and if neither side can move then the whole array is full, and to pop from stack i we simply move Top[i] back and return the value, and a related design lets three stacks grow toward each other and sometimes balances pushes to reduce movement, and while these tricks can help in practice the worst case for push can still be O(n) because we may need to shift many items, while pop stays O(1), so this is an advanced option when space is fixed and tightly managed.

1. Setup:
   1. Divide an array A[1..n] into m equal parts.
   2. Base[i] and Top[i] mark the start and current top of stack i.
   3. Initially, Base[i] = Top[i] = start index of part i.
2. Push on stack i:
   1. If Top[i] + 1 == Base[i+1], try shifting right side stacks to the right.
   2. If not possible, try shifting left side stacks to the left.
   3. If still not possible, array is full; throw overflow.
   4. Else, increment Top[i] and write the value.
3. Pop on stack i:
   1. If Base[i] == Top[i], underflow for stack i.
   2. Read A[Top[i]] and decrement Top[i].
   3. Return the read value.

Advantages and Disadvantages

It helps to compare designs so you can pick the one that fits your task, and the array stack gives O(1) push and pop with very low overhead and great cache behavior which is good when you know the maximum size, but it can overflow if your guess is too small, and the dynamic array stack gives O(1) amortized push with automatic growth which is a great default when sizes are unknown although rare resizes can be costly and can fail if memory is tight, and the linked list stack grows and shrinks without resizing and keeps O(1) push and pop but uses extra memory per node and may be slightly less cache-friendly, and the many-stacks-in-one-array design gives tight space control in one block but can make push O(n) in the worst case and is harder to code, so in real work start with a dynamic array or a linked list, pick array when sizes are known and raw speed matters, and pick linked list when smooth growth and simple changes are wanted.

• Array Stack:
  • Advantages: O(1) operations, great cache locality, very simple.
  • Disadvantages: Fixed capacity, overflow if size guess is wrong.
• Dynamic Array Stack:
  • Advantages: Amortized O(1) push, automatic growth, simple interface.
  • Disadvantages: Rare costly resizes, possible memory allocation failures.
• Linked List Stack:
  • Advantages: Grows and shrinks gracefully, no resize, O(1) operations.
  • Disadvantages: Extra pointer memory per node, slightly less cache-friendly.
• Multiple Stacks in One Array:
  • Advantages: Tight space control, single block memory management.
  • Disadvantages: Push can be O(n) due to shifting, code complexity is higher.

Putting It All Together: Small Worked Example

Let us walk through a tiny example to make the flow clear by starting with an empty stack where top = -1, and Step 1 is Push 5 where we check overflow, see there is space, move top to 0, and place 5 at index 0, and Step 2 is Push 8 where we check overflow, move top to 1, and place 8 at index 1, and Step 3 is Top() where we check underflow, read index 1, return 8, and keep top at 1, and Step 4 is Pop() where we check underflow, read index 1 with value 8, move top to 0, and return 8, and Step 5 is Pop() where we check underflow, read index 0 with value 5, move top to -1, and return 5, and Step 6 is Pop() where top is -1 so it is underflow and we throw an exception, and if this were a dynamic array stack the push steps would match and if the array filled we would double capacity first then save the new value, and if this were a linked list stack we would replace indexes with nodes where push links a new node in front and pop unlinks the top node, showing that the ADT behavior stays the same while only the inside storage changes.

Performance Summary (All Implementations)

This table gives a quick view of common actions across the three stack implementations, where the array stack has constant time for all main actions, the dynamic array stack also has constant time with amortized O(1) for push because resizing happens only sometimes, and the linked list stack has constant time and never resizes but uses extra node pointers, and all use O(n) space for n items, so choose based on whether you know the size, how memory behaves on your system, and how you expect growth, and for most general tasks the dynamic array stack is a safe fast default, while for strict memory and speed with known size the array stack is best, and for flexible growth with no copies the linked list stack is strong, and all three obey the same ADT rules for push, pop, top, size, and isEmpty, and all raise underflow on empty pop or top, while only the fixed array can raise overflow on push when it cannot grow.

Final Tips and Best Practices

Keep your stack API simple and strict by always checking for underflow before pop and top, by checking for overflow before push in a fixed array, and by favoring the dynamic array stack when the size is unknown and you want simple and fast behavior, and by favoring the array stack when you know the exact maximum size and want the lowest overhead per action, and by favoring the linked list stack when you need smooth growth and shrink with no copy steps and the small extra pointer memory is fine, and you should document which exceptions are thrown so callers know how to handle errors, and you should write unit tests for empty, single element, and full cases, and you should measure with your real workload because cache, memory, and usage patterns can change which design is fastest, and if you remember the core idea that everything happens at the top and the last in is the first out, you will use stacks well and feel ready to learn queues, deques, priority queues, and trees with confidence.