Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

Implementing a Stack

Explore how to implement a stack in C++ using both array-based and linked list-based approaches. Understand the structure, operations like push and pop, and evaluate the pros and cons of each method. This lesson also introduces the use of std::stack for practical applications.

We'll cover the following...

With the concept of a stack established, the next step is to examine its implementation. A stack is an abstract data type. It defines a set of operations but does not specify how data is stored or managed in memory. A stack can be implemented using different underlying structures, such as an array or a linked list.

Using an array

In an array-based stack implementation, we use an array to store stack elements, with all elements stored in a contiguous block of memory. Since a stack only ever adds and removes elements from the top, we can simply treat one end of the array as the top. The first element added sits at index 0, and each new element is placed at the next available position. The most recently added element always sits at the last index.

Think of it like a stack of plates, with the tray as a row of numbered slots. The first plate goes into slot 0, the second into slot 1, and so on. The top plate is always the one in the last occupied slot.

Stack represented by an array
Stack represented by an array

In an array, an index called the top is used to track the position of the most recently added element. The size tells us how many elements are currently in the stack. Additionally, a capacity defines the maximum number of elements the stack can hold; this is the total size of the underlying array.

Fixed-size array
Fixed-size array

If the array has a fixed size, then the stack has a maximum capacity that cannot be exceeded without resizing. If a dynamic array is used, the capacity can grow when needed (typically doubling when full), although the top position is still managed explicitly to maintain LIFO order.

Here is how an array-based stack works:

canvasAnimation-image
1 / 4

As elements are pushed onto the stack, the top index increments. When elements are popped, the top index decrements. The stack only grows and shrinks from one end, making the implementation straightforward and efficient.

Implementation in C++

In C++, an array-based stack can be implemented using a class with a fixed-size array:

C++ 17
#include <vector>
#include <stdexcept>
class ArrayStack {
private:
    std::vector<int> arr;
    int topIndex;
public:
    ArrayStack(int capacity = 10) : arr(capacity), topIndex(-1) {}
    // Stack operations (push, pop, peek, etc.) will be discussed in the next lesson
};
Implementation of a stack using an array

This ...