Stack Operations and the LIFO Principle

A stack can be implemented with an array or with a linked list, and both versions expose the same push, pop, and isEmpty operations.

Programming

Interactive lab

Try it: Stack and Queue

The difference between a stack (last in, first out) and a queue (first in, first out).

How it works

A stack adds (push) and removes (pop) at the same end, the top — the last item added leaves first.
A queue adds (enqueue) at the back and removes (dequeue) from the front — the first item added leaves first.
peek / front look at the next item without removing it.
Adding to a full structure is an overflow; removing from an empty one is an underflow.

Default run (3 steps): Stack (bottom → top): 4, 7. 2 of 8 slots used. Choose an operation. Example: push 9. … Stack is now: 4, 7, 9. Size 3/8.

Simplified: Fixed capacity of 8 items so overflow can be shown; Python lists and collections.deque grow as needed.

Educational simulation

Loading the simulation…

Testing an Upside-Down Belief

A stack is an abstract data type that follows the Last-In-First-Out principle: the item added most recently is the first one removed. Because a stack is defined only by its operations, the same idea can be built in more than one way. This article looks at two concrete implementations of a stack of ints, one built from an array and one built from a linked list, and shows exactly how each one tracks its top.

Many learners arrive with a specific belief about the array version. The usual picture of an array stack is drawn upside down, so it seems natural that the top of the stack must sit at the front of the array, at index 0. Keep that belief in mind as you read. The rest of the article checks it against the actual definitions.

What do you think happens?

In an array-based stack holding four items, which index holds the top item: index 0, or index 3 (the last used slot)?

Index 0, the front of the array
Index 3, which is top minus 1 when top is 4

Reveal answer

Answer:

Index 3. The top item sits at position top minus 1, not at index 0.

Index 0 is the bottom of the stack. The source is explicit that position 0 is the bottom and position top-1 is the top, so the upside-down drawing does not move the top to index 0.

Where the Top Lives in an Array Stack

The number of items on an array-based stack changes over time, so the array has many slots that may or may not be in use at any moment. A counter, conventionally named top, records how many of those slots are in use. If top is the counter, the items live in positions 0, 1, up to top-1. The item in position 0 is at the bottom of the stack, and the item in position top-1 is at the top.

With four items in use, which position holds the top item, and what does the counter top record?

The diagram shows why the counter is not simply the index of the newest item. It is the count of items in use. Because the first slot is index 0, that same number is also the index of the next free slot. That double role is why the top item sits at top-1 rather than at top. Once you hold this picture, the upside-down drawing stops being confusing: the bottom and top are determined by positions 0 and top-1, whichever way the array is drawn on paper.

Three pieces make up the logic of the array implementation apart from growth. The first is the counter itself. The second is the guard in pop: if top is 0, the stack is empty, and the method throws an IllegalStateException with the message that you cannot pop from an empty stack. The third is isEmpty, which returns true exactly when top equals 0. Because push and pop both work through the counter, the array never needs to be searched. Each operation touches a fixed position computed from top.

Tracing Push, Pop, and isEmpty

In the array version, push places the new item at position top and then adds 1 to top. Pop reverses the order: it reads the item at position top-1, subtracts 1 from top, and returns the item it read. The next diagram follows a short sequence of operations and shows what the top, the size, and isEmpty look like after each step.

After each push or pop, what is the new top, what items are in use, and what does isEmpty return?

Worked example

Pushing A, B, C, then popping, then pushing D

Starting from an empty array stack with top = 0, perform these operations in order: push A, push B, push C, pop, push D, pop, pop, pop. Record the returned value of each pop and the final value of isEmpty.

1
push A
A is stored at position top, which is position 0. Then top becomes 1.
2
push B
B is stored at position 1. Then top becomes 2.
3
push C
C is stored at position 2. Then top becomes 3.
4
pop (first)
Read position top-1, which is position 2, so the value is C. Subtract 1 from top, so top becomes 2. Return C.
5
push D
D is stored at position top, which is position 2. This overwrites the old C. Nothing had to be erased, because the counter already marked position 2 as free. Then top becomes 3.
6
pop (second)
Read position 2, which holds D. Top becomes 2. Return D.
7
pop (third)
Read position 1, which holds B. Top becomes 1. Return B.
8
pop (fourth)
Read position 0, which holds A. Top becomes 0. Return A.
9
isEmpty
top equals 0, so isEmpty returns true.

Result

Pops return C, D, B, A in that order, and isEmpty returns true. The most recently pushed value still in the stack is always the one removed first.

What do you think happens?

Starting from an empty stack, you push 3, then push 5, then pop. What value does the pop return?

Reveal answer

Answer:

The stack follows Last-In-First-Out, so the item added most recently is removed first. 5 was pushed after 3, so pop returns 5 and leaves 3 on the stack.

How a Full Array Grows

A fixed-size array puts a limit on how many items the stack can hold. If that limit is unwanted, the source suggests the dynamic array technique. Before each push, the implementation checks whether top equals the length of the items array. If it does, the array is full. The code then creates a new, larger array and copies the current stack items into it. The source resizes by doubling the array's size, using Arrays.copyOf with twice the current length. The new item is stored in the next available spot, and top goes up by one as usual.

When the array is full and another push arrives, what happens step by step to allocate a larger array and copy the existing items?

The resize step changes the storage but not the stack. The four existing items keep their order from bottom to top, and top still counts them. Only the container grows. This is why the abstract stack operations can stay the same while the array underneath is replaced. Callers of push, pop, and isEmpty never see the copy happen.

The Linked List Version

The linked list implementation reaches the same abstract behavior by a different route. Here the top of the stack is the node at the head of the list. A private static nested class named Node holds an int item and a reference next to the following node. The stack stores a single pointer, top, which points to the head node. If top is null, the stack is empty.

Push creates a new node, stores the new item in it, and points its next reference at the old top. Then top is moved to the new node. Pop saves the item from the head node, moves top to the second node, and returns the saved item. The source explains why this is a good choice: adding and removing nodes at the front of a linked list is much easier than inserting or deleting nodes in the middle. A stack only ever works at one end, so the front is the only place it needs.

Worked example

Pushing 3 and 8, then popping on a linked list stack

Starting from an empty linked-list stack where top is null, push 3, push 8, then pop. Describe the head node after each step and state the returned value.

1
push 3
Create a node holding 3. Its next reference points at the old top, which is null. Move top to this node. The head is now the node holding 3.
2
push 8
Create a node holding 8. Its next reference points at the node holding 3. Move top to the new node. The head is now the node holding 8, and it names the node holding 3 beneath it.
3
pop
Save the item 8 from the head node. Move top to the second node, which holds 3. Return the saved 8.

Result

The pop returns 8, and the head is now the node holding 3. The stack is not empty, because top is not null.

In the array version, the top of the stack is found by arithmetic on the counter. In the linked list version, it is found by following the head pointer. Both designs present the same stack behavior to the caller, which is the point of defining a stack by its operations rather than by its storage.

Mistakes Beginners Make with Index 0

Common mistake
Treating index 0 as the top of the array stack
What it looks like
With items A, B, C in positions 0 to 2 and top = 3, the learner says the top item is A because it sits first in the array.
Why it fails
Position 0 is the bottom of the stack. The top item sits at position top-1, which here is position 2 holding C.
Do this instead
Find the top with top-1, not with index 0. Pop reads position top-1, subtracts 1 from top, and returns the value it read.
Common mistake
Pushing to position top-1 instead of position top
What it looks like
With top = 2, the learner writes the new item into position 1, overwriting B.
Why it fails
top is the count of items in use and also the index of the next free slot. The new item belongs at position top, which is position 2 here.
Do this instead
Push stores the item at position top first, then adds 1 to top.
Common mistake
Assuming pop must erase the removed value
What it looks like
After popping C from a stack with top = 3, the learner expects position 2 to be cleared before the next push.
Why it fails
Pop only lowers the counter. The next push simply writes over position 2.
Do this instead
Rely on top to know which positions are in use, rather than on the contents of the array.
Common mistake
Popping from an empty stack without the guard: pop must throw an IllegalStateException when top is 0

Best practice

When tracing an array stack by hand, write down top before every operation and redo the arithmetic each time. Locating the top item as position top-1 avoids the upside-down trap entirely.

Comparing the Two Implementations

Aspect	Array-based stack	Linked-list stack
Where the top is	Position top-1, found by arithmetic on the counter	The head node, found by following the top pointer
Push	Store at position top, then add 1 to top	Create a node pointing at the old top, then move top to it
Pop	Read position top-1, subtract 1 from top, return the value	Save the head's item, move top to the second node, return the item
isEmpty	True when top equals 0	True when top is null
Capacity	Fixed unless a dynamic array grows it by doubling	Nodes are added as needed
Shared behavior	Same push, pop, and isEmpty operations	Same push, pop, and isEmpty operations

Both implementations expose the same stack operations through different internal top tracking.

Practice Tracing a Stack

MEDIUM

Starting from an empty array stack with top = 0, perform these operations in order: push 4, push 6, push 2, pop, push 9, pop, pop. Predict the value returned by each pop, then state the final top and whether isEmpty returns true or false.

Hints

After each push, the new item goes to position top, and then top increases by 1.
Each pop reads position top-1, so the most recent item still in use is removed first.
After pop returns 2, top is 2, so the next push writes into position 2.

Your attempt (not saved)