ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Custom Stack Implementation

C++

Goal -- WPM

Ready
Exercise Algorithm Area
1#include <vector>

2#include <stdexcept>

3#include <iostream>

4

5class CustomStack {

6private:

7std::vector<int> data;

8int topIndex;

9int capacity;

10

11void resize(int newCapacity) {

12std::vector<int> newData(newCapacity);

13for (int i = 0; i <= topIndex; ++i) {

14newData[i] = data[i];

15}

16data = std::move(newData);

17capacity = newCapacity;

18}

19

20public:

21CustomStack(int initialCapacity = 10) : topIndex(-1), capacity(initialCapacity) {

22if (initialCapacity <= 0) {

23throw std::invalid_argument("Initial capacity must be positive.");

24}

25data.resize(capacity);

26}

27

28void push(int value) {

29if (topIndex == capacity - 1) {

30// Array is full, double the capacity

31resize(capacity * 2);

32}

33data[++topIndex] = value;

34}

35

36int pop() {

37if (isEmpty()) {

38throw std::out_of_range("Stack is empty.");

39}

40// Optional: Shrink array if it's too sparse (e.g., less than 1/4 full)

41if (topIndex > 0 && topIndex == capacity / 4) {

42resize(capacity / 2);

43}

44return data[topIndex--];

45}

46

47int top() const {

48if (isEmpty()) {

49throw std::out_of_range("Stack is empty.");

50}

51return data[topIndex];

52}

53

54bool isEmpty() const {

55return topIndex == -1;

56}

57

58int size() const {

59return topIndex + 1;

60}

61};
Algorithm description viewbox

Custom Stack Implementation

Algorithm description:

This C++ class implements a custom stack data structure using a `std::vector` as its underlying storage. It provides standard stack operations: `push` to add an element, `pop` to remove and return the top element, `top` to view the top element, and `isEmpty` to check if the stack is empty. The implementation includes dynamic resizing of the internal vector to efficiently handle varying numbers of elements, ensuring amortized constant time complexity for push and pop operations.

Algorithm explanation:

The `CustomStack` class manages elements using a `std::vector` named `data`. `topIndex` tracks the index of the top element, initialized to -1 for an empty stack. `capacity` stores the current allocated size of the `data` vector. The `push` operation adds an element; if the vector is full (`topIndex == capacity - 1`), it calls `resize` to double the capacity. The `pop` operation removes and returns the top element; it also includes an optional shrinking mechanism if the stack becomes very sparse (e.g., `topIndex` is 1/4 of `capacity`), resizing to half the capacity. Both `push` and `pop` have amortized O(1) time complexity due to the resizing strategy. `top` returns the top element without removing it (O(1)). `isEmpty` checks if `topIndex` is -1 (O(1)). The constructor handles invalid initial capacities and resizes the vector. Edge cases like popping from an empty stack or creating a stack with non-positive capacity are handled with exceptions.

Pseudocode:

CLASS CustomStack:
  PRIVATE:
    vector data
    int topIndex = -1
    int capacity

    METHOD resize(newCapacity):
      create new vector newData of size newCapacity
      COPY elements from data[0..topIndex] to newData[0..topIndex]
      data = newData
      capacity = newCapacity

  PUBLIC:
    CONSTRUCTOR(initialCapacity = 10):
      IF initialCapacity <= 0 THEN
        THROW invalid_argument
      END IF
      capacity = initialCapacity
      RESIZE data to capacity

    METHOD push(value):
      IF topIndex == capacity - 1 THEN
        resize(capacity * 2)
      END IF
      topIndex = topIndex + 1
      data[topIndex] = value

    METHOD pop():
      IF isEmpty() THEN
        THROW out_of_range
      END IF
      // Optional shrink logic here
      returnValue = data[topIndex]
      topIndex = topIndex - 1
      RETURN returnValue

    METHOD top() const:
      IF isEmpty() THEN
        THROW out_of_range
      END IF
      RETURN data[topIndex]

    METHOD isEmpty() const:
      RETURN topIndex == -1

    METHOD size() const:
      RETURN topIndex + 1
END CLASS