What is Stack and Queue in Data Structures: Programs

In computer science, a stack is a linear data structure based on the Last In, First Out (LIFO) principle. It is an abstract data type that consists of a set of similar elements, such as objects, integers, or characters, which are added and removed from the top of the stack.

In a stack, the element that is added last is the first one to be removed. This means that the order of elements is reversed when they are retrieved. For example, if you push elements A, B, and C onto a stack, the order of retrieval would be C, B, and A.

Operations of Stack

The basic operations associated with a stack are:

• Push: The operation of adding an element to the top of the stack.
• Peek or Top: Retrieving the topmost element without removing it.
• Pop: Removing the topmost element from the stack.
• IsEmpty: Checking if the stack is empty.

In data structures, queues follow the principle of First-In-First-Out (FIFO). The queue is open on both ends, so elements may be added (enqueued) and removed (dequeued) in a specific sequence.

Operations of Queue

The basic operations associated with a queue are:

• Enqueue: Adds an element to the queue at the end.
• Dequeue: This is the process of removing an element from the queue.
• Peek (or Front): Retrieves the element at the front of the queue without removing it.
• IsEmpty: Checks if the queue is empty.
• IsFull (for fixed-size queues): Checks if the queue is full.

Here is the comparison of stack and queue:

Here are the stack and queue programs in data structures:

Program of Stack in C++

Here is a stack program in C++ using the class:

#include <iostream>
#include <vector>

class Stack {
private:
    std::vector<int> stack;  // Vector to store stack elements

public:
    // Push an element onto the stack
    void push(int item) {
        stack.push_back(item);
    }

    // Pop an element from the stack
    int pop() {
        if (isEmpty()) {
            std::cout << "Stack is empty!" << std::endl;
            return -1; // Or throw an exception
        }
        int item = stack.back();
        stack.pop_back();
        return item;
    }

    // Peek at the top element of the stack
    int peek() {
        if (isEmpty()) {
            std::cout << "Stack is empty!" << std::endl;
            return -1; // Or throw an exception
        }
        return stack.back();
    }

    // Check if the stack is empty
    bool isEmpty() {
        return stack.empty();
    }
// Get the size of the stack
    int size() {
        return stack.size();
    }

    // Print the stack
    void print() {
        if (isEmpty()) {
            std::cout << "Stack is empty!" << std::endl;
            return;
        }
        for (int i = stack.size() - 1; i >= 0; i--) {
            std::cout << stack[i] << " ";
        }
        std::cout << std::endl;
    }
};

// Example usage:
int main() {
    Stack stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);

    stack.print();  // Output: 30 20 10

    std::cout << "Pop: " << stack.pop() << std::endl; // 30
    std::cout << "Peek: " << stack.peek() << std::endl; // 20
    std::cout << "Size: " << stack.size() << std::endl; // 2

    stack.print();  // Output: 20 10

    return 0;
}

Output

30 20 10 
Pop: 30
Peek: 20
Size: 2
20 10

Program of Queue in C++

Here is a queue program in C++ using the class:

#include <iostream>
#include <deque>

class Queue {
private:
    std::deque<int> queue;  // Deque to store queue elements

public:
    // Enqueue an element
    void enqueue(int item) {
        queue.push_back(item);
    }

    // Dequeue an element
    int dequeue() {
        if (isEmpty()) {
            std::cout << "Queue is empty!" << std::endl;
            return -1; // Or throw an exception
        }
        int item = queue.front();
        queue.pop_front();
        return item;
    }

    // Peek at the front element of the queue
    int peek() {
        if (isEmpty()) {
            std::cout << "Queue is empty!" << std::endl;
            return -1; // Or throw an exception
        }
        return queue.front();
    }

    // Check if the queue is empty
    bool isEmpty() {
        return queue.empty();
    }

    // Get the size of the queue
    int size() {
        return queue.size();
    }

    // Print the queue
    void print() {
        if (isEmpty()) {
            std::cout << "Queue is empty!" << std::endl;
            return;
        }
        for (int i = 0; i < queue.size(); i++) {
            std::cout << queue[i] << " ";
        }
        std::cout << std::endl;
    }
};

// Example usage:
int main() {
    Queue queue;

    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    queue.print();  // Output: 10 20 30

    std::cout << "Dequeue: " << queue.dequeue() << std::endl; // 10
    std::cout << "Peek: " << queue.peek() << std::endl;     // 20
    std::cout << "Size: " << queue.size() << std::endl;     // 2

    queue.print();  // Output: 20 30

    return 0;
}

Output

10 20 30 
Dequeue: 10
Peek: 20
Size: 2
20 30

The following are some similarities between stacks and queues:

• Both are linear data structures as they arrange data sequentially.
• The operations on stack and queue are simple and can be defined clearly (push, pop, enqueue, dequeue).
• Both structures can be implemented using arrays or linked lists.

Here are some of the applications of stack and queue:

Stack

• Used in parsing expressions and evaluating mathematical operations (infix, postfix).
• In applications like maze solving, backtracking relies on stacks to store states.
• The call stack is used in recursive functions and function calls in programming.

Queue

• Queues are used in operating systems to schedule tasks based on FIFO.
• Packets in network protocols are managed using queues.
• Queues are essential for graph traversal in BFS.

In conclusion, stacks and queues are fundamental data structures in computer science, each designed for specific use cases. The stack is useful for problems that require reversal or backtracking, while the queue is ideal for tasks requiring sequential processing, like scheduling or resource management. Understanding the unique characteristics of these structures helps in selecting the appropriate one for different algorithms and applications.

1. What is the main difference between a stack and a queue?

A stack follows the LIFO (Last In, First Out) principle, while a queue follows the FIFO (First In, First Out) principle.

2. Can a stack or queue be implemented using arrays or linked lists?

Yes, stacks and queues can be implemented by using arrays or linked lists. In some cases, a queue may also use a circular buffer for more efficient memory usage.

3. In which real-life situations can a stack be useful?

Stacks are useful in situations like managing function calls in programming, undo operations in applications, and evaluating expressions.

4. When would a queue be used in computer science?

Queues are typically used in scenarios like task scheduling, managing print jobs, or in breadth-first search (BFS) in graph traversal.

5. What is the time complexity of basic operations in stack and queue?

Both stack and queue operations such as Push/Pop for stack and Enqueue/Dequeue for queue are performed in constant time, i.e., O(1).