Stacks and Queues in C++

Introduction: Stacks and Queues

Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues! Remember, data structures store and organize data in a manner that is structured and efficient. Stacks and Queues are akin to stacking plates and standing in a line, respectively. Intriguing, isn't it? Let's dive in!

Stacks: Last In, First Out (LIFO)

A Stack adheres to the "Last In, First Out" or LIFO principle. It's like a pile of plates where the last plate added is the first one to be removed. C++ provides the std::stack container from the Standard Library to work with stacks. The primary methods used with stacks are push, pop, empty, and top:

  • push: Adds an element to the top of the stack.
  • pop: Removes the top element from the stack.
  • empty: Checks whether the stack is empty.
  • top: Returns the top element of the stack without removing it.

Let's explore this using a pile of plates.

#include <iostream>
#include <stack>

class StackOfPlates {
public:
    // Inserts a plate at the top of the stack
    void add_plate(const std::string &plate) {
        stack.push(plate); // Using push to add a plate
    }

    // Removes the top plate from the stack
    std::string remove_plate() {
        if (stack.empty()) { // Using empty to check if stack is empty
            return "No plates left to remove!";
        }
        std::string topPlate = stack.top(); // Using top to access the top plate
        stack.pop(); // Using pop to remove the top plate
        return topPlate;
    }

private:
    std::stack<std::string> stack;
};

// Main function to demonstrate stack usage
int main() {
    StackOfPlates plates;
    plates.add_plate("Plate"); // Pushes a plate
    plates.add_plate("Another Plate"); // Pushes another plate

    // Let's remove a plate; it should be the last one we added.
    std::cout << "Removed: " << plates.remove_plate() << std::endl; // Outputs: Removed: Another Plate

    return 0;
}

The last plate added was removed first, demonstrating the LIFO property of a stack.

Queues: First In, First Out (FIFO)

A Queue represents the "First In, First Out" or FIFO principle, much like waiting in line at the grocery store. C++ provides the std::queue container from the Standard Library to work with queues. The primary methods used with queues are push, pop, empty, and front:

  • push: Adds an element to the end of the queue.
  • pop: Removes the first element from the queue.
  • empty: Checks whether the queue is empty.
  • front: Returns the first element of the queue without removing it.

Let's examine this through a queue of people.

#include <iostream>
#include <queue>

class QueueOfPeople {
public:
    // Adds a person to the end of the queue
    void enqueue_person(const std::string &person) {
        queue.push(person); // Using push to add a person
    }

    // Removes the first person from the queue (who has been waiting the longest)
    std::string dequeue_person() {
        if (queue.empty()) { // Using empty to check if queue is empty
            return "No people left to dequeue!";
        }
        std::string frontPerson = queue.front(); // Using front to access the first person
        queue.pop(); // Using pop to remove the first person
        return frontPerson;
    }

private:
    std::queue<std::string> queue;
};

// Main function to demonstrate queue usage
int main() {
    QueueOfPeople people;
    people.enqueue_person("Person 1"); // Person 1 enters the queue
    people.enqueue_person("Person 2"); // Person 2 arrives after Person 1

    // Who's next in line? It must be Person 1!
    std::cout << "Removed: " << people.dequeue_person() << std::endl; // Outputs: Removed: Person 1

    return 0;
}

Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal