Why this matters
A stack is a rule about order. The last item added is the first item removed. The rule does not say where the items are stored. The same stack can sit on a chain of small boxes linked together, or on one block of memory. The two choices behave differently in speed and memory use, and each one has a cost that is easy to miss at first.
This lesson builds a stack on a linked list, then builds a stack on an array that grows as it fills. The second part measures the cost of growing. That measurement explains why the std::vector you may already use can add an item quickly most of the time and sometimes slowly, while the average stays fast.
The lesson uses pointers and the stack operations push, pop, top and empty. Pointers are covered earlier in this course. The fixed-size array stack is in the first lesson of this module, so this lesson does not repeat it.
Part one: a stack on a linked list
What a linked list is
A linked list is a chain of small boxes. Each box is called a node. A node holds a value and the location of the next node. The location is stored as a pointer. The first node is called the head. The last node has no next node.
Nodes are created one at a time in memory, so they do not need to sit next to each other. A linked list does not need one large block of memory. That is the main difference from an array.
The diagram below shows a stack of three numbers, with 30 on top. The arrows are the stored locations of the next node.
head
|
v
[ 30 | next ] --> [ 20 | next ] --> [ 10 | none ]A stack on a linked list uses the head as the top. A push creates a new node and makes it the head. A pop removes the head and makes the next node the new head. Both operations touch only the head, so both take the same amount of work no matter how long the list is.
Smart pointers in one paragraph
A plain pointer does not free memory on its own. The programmer must call delete for each node, and forgetting to do so leaks memory. A smart pointer is an object that owns a pointer and frees the memory when the owner goes away. This lesson uses std::unique_ptr. A unique_ptr owns one node. When the unique_ptr is destroyed, the node it owns is destroyed too. Only one unique_ptr can own a node at a time, so ownership moves with std::move and cannot be copied.
The code
Each node owns the node after it, through a unique_ptr called next. The stack owns the head. Pushing creates a node whose next takes over the old head. Popping moves the head pointer forward, and the old head node is freed automatically when its unique_ptr is emptied.
#include <cstddef>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <utility>
class ListStack {
struct Node {
int value;
std::unique_ptr<Node> next;
};
std::unique_ptr<Node> head_;
std::size_t size_ = 0;
public:
void push(int x) {
head_ = std::make_unique<Node>(Node{x, std::move(head_)});
++size_;
}
int pop() {
if (!head_) {
throw std::underflow_error("pop from empty stack");
}
int value = head_->value;
head_ = std::move(head_->next);
--size_;
return value;
}
int top() const {
if (!head_) {
throw std::underflow_error("top of empty stack");
}
return head_->value;
}
bool empty() const { return size_ == 0; }
std::size_t size() const { return size_; }
};Take the push line slowly. The expression Node{x, std::move(head_)} builds a new node. Its value is x, and its next takes ownership of the old head. The std::make_unique call puts the new node on the heap, which is the part of memory that lives until it is freed. The result is assigned to head_, so the new node is now the head. The old head is still alive, because the new node's next owns it.
The line head_ = std::move(head_->next); in pop does the same thing in reverse. The old head's next gives up its node and the head moves to it. When the assignment runs, the old head is no longer owned by anything, so it is freed.
The pop and top functions check head_ before they read it. An empty stack has no head, so head_ is a null pointer. Reading head_->value on a null pointer is undefined behaviour, which usually means a crash. The check turns that case into an exception with a clear message.
Running it
The main function below pushes three numbers, reads the top, pops them all, and tries one more pop.
int main() {
ListStack ls;
for (int i = 1; i <= 3; ++i) {
ls.push(i * 10);
}
std::cout << "top " << ls.top() << ", size " << ls.size() << '\n';
while (!ls.empty()) {
std::cout << "pop " << ls.pop() << '\n';
}
try {
ls.pop();
} catch (const std::underflow_error& e) {
std::cout << "error: " << e.what() << '\n';
}
}Compiled with g++ -std=c++20 -Wall, the program prints:
top 30, size 3
pop 30
pop 20
pop 10
error: pop from empty stackThe order is last in, first out, as expected. The numbers come back in the reverse of the order they went in.
The cost of a linked list stack
Each operation takes constant time. Push allocates one node, which costs a little more than writing into an array slot. Pop frees one node. Neither operation copies the other items.
The cost in memory is higher. Each item needs its value plus a pointer to the next node, and each node is a separate allocation. Reading the whole stack means jumping from one node to another across memory, which is slower than reading an array one slot after another. These costs are real, but they do not change the big-O time of the operations.
The destructor problem
When a ListStack is destroyed, its head_ is destroyed. That destroys the first node, which destroys its next, and so on down the chain. The destruction is recursive: each node waits for the next node to be destroyed before it finishes. For a short list this is fine. For a very long list, the recursion uses a lot of stack space, which is the memory the program uses for function calls.
The next program is the stack without a destructor. It pushes one million numbers and then ends. The line that prints comes before the destruction, so the output shows that the pushes worked.
#include <iostream>
#include <memory>
#include <utility>
struct Node { int value; std::unique_ptr<Node> next; };
class ListStack {
std::unique_ptr<Node> head_;
public:
void push(int x) { head_ = std::make_unique<Node>(Node{x, std::move(head_)}); }
};
int main() {
ListStack ls;
for (int i = 0; i < 1000000; ++i) ls.push(i);
std::cout << "pushed 1000000" << std::endl;
}Compiled with g++ -std=c++20 -Wall -O0 and run on this machine, it prints pushed 1000000 and then ends with exit code 139, which is the code for a segmentation fault. A segmentation fault is a crash caused by touching memory the program is not allowed to use. Here the recursion ran out of stack space while the list was being destroyed.
The fix is a destructor that frees the nodes one at a time, with no recursion. The destructor takes the head, moves the head forward, and lets the old node go, until the list is empty:
~ListStack() {
while (head_) {
head_ = std::move(head_->next);
}
}Each assignment moves the next node into head_. The old head is freed at that moment, and its next is already empty because it was moved from. With the destructor added, the same program prints pushed 1000000 and exits with code 0.
Part two: a stack on an array that grows
Why an array needs a plan for growth
An array has a fixed size. A stack on an array needs room for every item, and the number of items is not known in advance. The earlier lesson on stacks used a fixed capacity and printed "overflow" when it was full. This part removes that limit.
The plan is this. Keep an array with a capacity, which is the number of slots in the array. Keep a separate size, which is the number of slots in use. The items sit in slots 0 to size minus one. When a push arrives and the size equals the capacity, the stack asks for a bigger array, copies every item into it, and throws the old array away. Then it writes the new item.
Two words need care. Size counts the items. Capacity counts the room. A stack with 3 items and room for 4 has size 3 and capacity 4.
The code
The class below holds the array in a unique_ptr<int[]>, which owns an array of integers and frees it automatically. The grow function creates an array with twice the capacity, copies the items over, and takes ownership of the new array. The class also counts every item it copies. The count is there to measure the cost, and a real stack would not need it.
#include <cstddef>
#include <memory>
#include <stdexcept>
#include <utility>
class GrowStack {
std::unique_ptr<int[]> data_;
std::size_t size_ = 0;
std::size_t capacity_ = 0;
std::size_t copies_ = 0;
void grow() {
std::size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;
auto bigger = std::make_unique<int[]>(new_capacity);
for (std::size_t i = 0; i < size_; ++i) {
bigger[i] = data_[i];
++copies_;
}
data_ = std::move(bigger);
capacity_ = new_capacity;
}
public:
void push(int x) {
if (size_ == capacity_) {
grow();
}
data_[size_++] = x;
}
int pop() {
if (size_ == 0) {
throw std::underflow_error("pop from empty stack");
}
return data_[--size_];
}
std::size_t size() const { return size_; }
std::size_t capacity() const { return capacity_; }
std::size_t copies() const { return copies_; }
};The line data_[size_++] = x; writes the new item into the first free slot, then adds one to the size. The post-increment size_++ gives the old value for the index and then increments the variable. The grow check comes first, so there is always a free slot when the write happens.
The line std::make_unique<int[]>(new_capacity) creates an array of new_capacity integers. The integers start at zero, because make_unique value-initialises them. The copy loop then fills the first size_ slots with the old items.
The doubling is in one line: capacity_ * 2. The first grow uses a capacity of 1, because doubling 0 would give 0 and leave no room.
Watching the growth
The program below pushes ten numbers and prints the state after each push. The output shows when the capacity changes and how many copies have happened so far.
int main() {
GrowStack gs;
for (int i = 1; i <= 10; ++i) {
gs.push(i);
std::cout << "push " << i << " size " << gs.size() << " capacity " << gs.capacity()
<< " copies " << gs.copies() << '\n';
}
}The output is:
push 1 size 1 capacity 1 copies 0
push 2 size 2 capacity 2 copies 1
push 3 size 3 capacity 4 copies 3
push 4 size 4 capacity 4 copies 3
push 5 size 5 capacity 8 copies 7
push 6 size 6 capacity 8 copies 7
push 7 size 7 capacity 8 copies 7
push 8 size 8 capacity 8 copies 7
push 9 size 9 capacity 16 copies 15
push 10 size 10 capacity 16 copies 15Look at the rows for pushes 2, 3, 5 and 9. These are the pushes that found the array full. On each of those pushes the copies went up by the number of items already in the stack: 1, then 2, then 4, then 8. The other pushes cost nothing extra. Between two grows, the stack just writes into a free slot.
Each grow copies the items that are already there. The copy counts 1, 2, 4 and 8 add up to 15 after ten items. The capacity sequence 1, 2, 4, 8, 16 is the doubling.
Amortised cost
Most pushes cost one write. A few pushes cost one write plus a copy of every item. The question is what a single push costs on average.
Amortised cost is the average cost per operation over a whole sequence of operations, even when a few operations are expensive. The word means spread out over time. A grow is expensive, but it happens rarely, and each grow makes room for as many pushes as there are items. The big copy is paid for by the many cheap pushes that come after it.
The numbers show this. The table below counts the copies that a growth rule causes for a given number of pushes. The second column uses doubling. The third column grows by one slot each time the array is full.
n, doubling copies, plus-one copies
10, 15, 45
100, 127, 4950
1000, 1023, 499500
10000, 16383, 49995000
100000, 131071, 4999950000With doubling, the total copies stay below twice n. For 100000 pushes the total is 131071, which is less than 200000. So the average is about one copy per push, plus one write. That is constant work per push, in the amortised sense. With growth by one, the total is n times n minus one, divided by two. That grows with the square of n. For 100000 pushes it is about 5 billion copies, which is far too slow.
The program that produced this table also checks the real stack. Pushing 100000 numbers into GrowStack gives the same count as the doubling column:
GrowStack 100000 pushes: copies 131071, capacity 131072The real stack and the counting function agree, because they use the same growth rule.
What the standard library does
The std::vector type uses this same idea. The C++ standard requires push_back on a vector to take amortised constant time. It does not fix the growth factor, so other compilers may use a different number. The program below prints the capacity of a std::vector<int> as it grows. It was compiled with g++ 15.2 on Linux.
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
std::size_t last = v.capacity();
std::cout << "capacity " << last << '\n';
for (int i = 0; i < 100; ++i) {
v.push_back(i);
if (v.capacity() != last) {
last = v.capacity();
std::cout << "after push " << i + 1 << " capacity " << last << '\n';
}
}
}The output on that compiler is:
capacity 0
after push 1 capacity 1
after push 2 capacity 2
after push 3 capacity 4
after push 5 capacity 8
after push 9 capacity 16
after push 17 capacity 32
after push 33 capacity 64
after push 65 capacity 128The capacity doubles at each step, just like the stack in this lesson. Other compilers may print different numbers. The rule that matters is the amortised bound, not the exact sequence.
Choosing between the two
Here are the trade-offs in plain terms.
A linked list stack never copies items. A push allocates one node, so each push has a steady small cost. Its drawbacks are memory use, since each item carries a pointer and sits in its own allocation, and slower reading, since the nodes are scattered in memory.
An array stack stores items side by side, which is fast to read and uses memory well. Its drawbacks are the occasional big copy and the unused room. After a grow, the capacity can be close to twice the size, so up to about half the memory can sit unused. A single push can also take time proportional to the number of items, which matters if a program must respond within a fixed time limit.
There is one more trap with growing arrays. A pointer or reference to an item in the array becomes invalid after a grow, because the item now lives at a new address and the old array is gone. Code that saves a reference to top and then pushes can read freed memory. Store the index instead, or read the value again after the push.
Common mistakes
Copying a unique_ptr
A unique_ptr cannot be copied, because only one owner may exist. Writing Node{1, head} instead of Node{1, std::move(head)} causes a compile error. Here is a small program with that mistake:
#include <memory>
struct Node { int value; std::unique_ptr<Node> next; };
int main() {
std::unique_ptr<Node> head;
head = std::make_unique<Node>(Node{1, head});
}The compiler reports this error, with the first line and the key part shown here:
copy_err.cpp:7:43: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]’The word deleted means the copy operation was removed on purpose. The fix is to write std::move(head). The compiler is protecting the list from having two owners of the same node.
Freeing a long list recursively
The destructor problem from part one is a common mistake. The program runs without error for small lists and crashes for a list of one million nodes. The fix is the loop shown earlier, which frees the nodes one at a time.
Growing by a fixed amount
A common first version of a growing array adds one slot each time it is full. The code looks simple, but the copy counts show the cost. The table in part two shows 49995000 copies for 10000 pushes, against 16383 with doubling. The difference grows with n. Doubling is the usual choice for that reason.
Popping an empty stack
Both stacks in this lesson check for emptiness before popping. A pop on an empty array stack would subtract one from a size of zero, which wraps around to a huge number and reads outside the array, and a pop on an empty list stack would read through a null pointer. Both are bugs that may not crash right away. The check is what keeps the stack safe, so keep it even when the calling code seems to guarantee the stack is not empty.
Practice
Exercise 1: Copies for five pushes
How many items does GrowStack copy during five pushes, starting from an empty stack?
Show the answer
Seven. The grows happen when the stack holds 1, 2 and 4 items and the next push arrives. The copies are 1, 2 and 4, which add up to 7. The ten-push trace in part two shows this: after push 5 the copies value is 7.
Exercise 2: Why check head before reading it
In ListStack::top, the code checks head_ before reading head_->value. What would happen on an empty stack without that check?
Show the answer
On an empty stack head_ holds a null pointer, which points at no node. Reading head_->value reads memory through that null pointer. That is undefined behaviour, which usually means a crash. The check throws std::underflow_error with a clear message instead.
Exercise 3: Count copies for growth by three
Suppose the capacity grows by 3 each time it is full, starting from 0. How many copies happen during 10 pushes?
Show the answer
Eighteen. The grows happen at pushes 1, 4, 7 and 10, when the stack holds 0, 3, 6 and 9 items. The copies are 0, 3, 6 and 9, which add up to 18. A program that counts this with the same rule prints 18 as well.
Exercise 4: The most expensive push
A GrowStack receives 1000 pushes. Which push copies the most items, and how many copies does it make?
Show the answer
Push number 513. Before that push the stack holds 512 items, which fills the capacity of 512, so the grow copies 512 items. The total copies for 1000 pushes is 1023, which is 1 plus 2 plus 4 and so on up to 512. Push 513 makes up half of the total on its own.
Exercise 5: Shrinking the array
Explain why a stack that halves its capacity as soon as the size drops to half would be slow in one specific pattern of pushes and pops, and what rule avoids this.
Show the answer
Suppose the capacity is 8 and the stack holds 5 items. A pop leaves 4 items, which is half the capacity, so the stack halves to capacity 4 and copies 4 items. A push then makes 5 items, which is more than the capacity of 4, so the stack doubles back to 8 and copies 4 items. Repeating a pop and a push now costs a copy every time. The rule that avoids this is to shrink only when the size drops to a quarter of the capacity, and then halve it. That leaves room for a few pushes and pops before the next copy.
Summary
- A stack on a linked list pushes and pops at the head, and both operations take constant time. Each node is a separate allocation, so memory use is higher.
- A recursive destructor on a very long list can crash with a segmentation fault. A loop that frees the nodes one at a time avoids the problem.
- An array stack that doubles its capacity copies the items only when it is full. Over many pushes the total copies stay below twice the number of pushes.
- Amortised cost is the average cost over a sequence of operations. Doubling makes each push constant on average, while growing by a fixed amount makes the total cost grow with the square of the number of pushes.
- A pointer or reference into a growing array can become invalid after a grow, so store an index instead.