Making a circular stack in C++

As a developer, having a profound understanding of data structures can significantly enhance your problem-solving abilities. One such interesting and less talked about data structure is the Circular Stack. While traditional linear stacks have a start and an end, a circular stack, as the name suggests, is a stack that forms a continuous loop. In this post, we'll explore how to implement a circular stack in C++.

What is a circular stack?

Before we jump into the implementation, let's understand what a circular stack is. A circular stack is a variation of the stack data structure in which the last element points to the first one, forming a loop or a 'circle.' This makes the circular stack a versatile tool, especially when dealing with cyclic data or scenarios where overflow management is crucial.

Designing a circular stack in C++

For our circular stack, we will use a dynamic array to store the elements. Like a traditional stack, we will provide push and pop operations to add and remove elements, respectively. Additionally, we will also provide a peek operation to inspect the top element without removing it.

Defining the circular stack class

Let's start by defining the CircularStack class and declaring our member variables and methods:

template <typename T>
class CircularStack {
private:
    T* stackArray;
    int topIndex;
    int capacity;
public:
    CircularStack(int size);
    ~CircularStack();
    void push(T value);
    T pop();
    T peek() const;
    bool isEmpty() const;
    bool isFull() const;
};

In the class above, stackArray is the dynamic array that will store our stack elements. topIndex keeps track of the current top of the stack, and capacity stores the maximum size of the stack. We've also declared a constructor to initialize the stack and a destructor to clean up when we're done.

Implementing the constructor and destructor

The constructor will take a size parameter that sets the maximum capacity of the stack. It will also initialize stackArray and topIndex:

template <typename T>
CircularStack<T>::CircularStack(int size) {
    if (size <= 0) throw std::invalid_argument("Size must be greater than 0");
    stackArray = new T[size];
    capacity = size;
    topIndex = -1;
}

template <typename T>
CircularStack<T>::~CircularStack() {
    delete[] stackArray;
}

Implementing stack operations

Now, let's implement the push, pop, peek, isEmpty, and isFull operations:

template <typename T>
void CircularStack<T>::push(T value) {
    if (isFull()) {
        topIndex = 0; // Wrap around to the start of the stack
    } else {
        topIndex++;
    }
    stackArray[topIndex] = value;
}

template <typename T>
T CircularStack<T>::pop() {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty");
    }
    T value = stackArray[topIndex];
    if (topIndex == 0) {
        topIndex = capacity - 1; // Wrap around to the end of the stack
    } else {
        topIndex--;
    }
    return value;
}

template <typename T>
T CircularStack<T>::peek() const {
    if (isEmpty()) {
        throw std::out_of_range("Stack is empty");
    }
    return stackArray[topIndex];
}

template <typename T>
bool CircularStack<T>::isEmpty() const {
    return topIndex == -1;
}

template <typename T>
bool CircularStack<T>::isFull() const {
    return topIndex == capacity - 1;
}

In the code above, the push method checks if the stack is full. If it is, it wraps around to the start of the stack and overwrites the oldest value. The pop method does the opposite, wrapping around to the end of the stack if it's at the start. The peek method simply returns the value at the top of the stack.

Wrapping up

That's it! We've successfully implemented a circular stack in C++. This data structure, while simple, offers unique advantages when dealing with certain types of problems, especially those that involve cyclic or continuous data. Understanding its implementation is a good step toward a deeper comprehension of data structures and how they can be adapted to suit different scenarios.

Remember, the real power of any data structure only becomes evident when you understand its underlying concept and know when and how to use it. Happy coding!