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.

Stacks and Queues: When and Where to Use?

Stacks handle ordered data efficiently, much like your web browser's history. Queues, on the other hand, are optimal when the order of arrival is essential, such as in a store queue.

Mastering Stack and Queue Operations With a Class

Let's depict the two structures in a text editor that features an Undo mechanism (a Stack) and a Print Queue.

#include <iostream>
#include <stack>
#include <queue>

class TextEditor {
public:
    // Makes a change (e.g., edits text, inserts image, changes font)
    void make_change(const std::string &action) {
        stack.push(action); // Adds to the stack of actions
    }

    // Undoes the most recent change
    std::string undo_change() {
        if (stack.empty()) {
            return "No changes to undo!";
        }
        std::string lastAction = stack.top();
        stack.pop();
        return lastAction;
    }

    // Adds a document to the queue for printing
    void add_to_print(const std::string &doc) {
        queue.push(doc);
    }

    // Prints the document that has been waiting the longest
    std::string print_doc() {
        if (queue.empty()) {
            return "No documents in the print queue!";
        }
        std::string nextDocument = queue.front();
        queue.pop();
        return nextDocument;
    }

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

// Main function to demonstrate TextEditor usage
int main() {
    TextEditor editor;
    editor.make_change("Changed font size"); // Makes a change
    editor.make_change("Inserted image"); // Makes another change

    // Let's undo a change. It should be the last change we made.
    std::cout << "Undo: " << editor.undo_change() << std::endl; // Outputs: Undo: Inserted image

    editor.add_to_print("Proposal.docx"); // Queues a document for printing
    editor.add_to_print("Report.xlsx"); // Queues another document

    // Let's print a document. It should be the document that has been waiting the longest.
    std::cout << "Print: " << editor.print_doc() << std::endl; // Outputs: Print: Proposal.docx

    return 0;
}

This code reintroduces the concepts of a Stack (Undo feature) and Queue (Print queue) in the context of a real-life scenario.

Lesson Summary

Great work! You have examined the mechanics of Stacks and Queues, both integral data structures. Remember to practice what you've learned. Happy coding!

Previous
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