Introduction to Data Structures Stack and Queue with Example Code in C++

Data structures are fundamental concepts in computer science and programming. They allow programmers to organize, store and efficiently manipulate data. Two commonly used data structures are stack and queue. In this article, we will introduce the basic concepts of stack and queue and provide example code in C++.

Stack

A stack is a data structure that follows the Last In, First Out (LIFO) principle. It can be visualized as a stack of plates where the last plate added to the stack is the first plate to be removed. The operations performed on a stack are:

• Push: Add an element to the top of the stack

Algorithm for push

begin
 if the stack is full
    return
 endif
else  
 increment top
 stack[top] assign value
end else
end procedure

• Pop: Remove the top element from the stack

Algorithm for pop

begin
 if the stack is empty
    return
 endif
else
 store value of stack[top]
 decrement top
 return value
end else
end procedure

• Top: Retrieve the top element from the stack without removing it.

Algorithm for top

begin 
  return stack[top]
end procedure

• isEmpty: Check if the stack is empty

algorithm for isEmpty

begin
 if top < 1
    return true
 else
    return false
end procedure

Applications of Stack

Stacks have many applications in computer science and programming. Here are some of the common applications of the stack:

• Expression evaluation: Stacks are used to evaluating expressions in programming languages. For example, postfix notation can be used along with a stack to evaluate arithmetic expressions.

• Function calls and recursion: Stacks are used to keeping track of function calls and recursive calls. When a function is called, its local variables and return addresses are stored on the stack, and when the function returns, the values are popped up from the stack.

• Backtracking: Stacks are used to implementing backtracking algorithms such as depth-first search. In such algorithms, the states of the search are pushed onto the stack, and when a dead-end is reached, the states are popped, and the search continues from the previous state.

• Parsing: Stacks are used to parsing and validate the syntax of programming languages. Each token is pushed onto the stack in a parser, and when a syntax rule is matched, the tokens are popped from the stack.

• Memory management: Stacks are used in memory management, such as allocating and deallocating memory on the heap.

• Undo/Redo: Stacks are used to implement the undo and redo functionality in many applications, such as text editors, where the most recent action is stored on the stack and can be undone by popping it from the stack.

Complexity analysis

Time complexity

Here is an example implementation of a stack data structure in C++ using a dynamic array:

#include <iostream>
using namespace std;


class Stack {
private:
    int* data;  // pointer to dynamic array to store elements
    int capacity;  // maximum number of elements in the stack
    int topIndex;  // index of the top element
public:
    Stack(int cap) {
        capacity = cap;
        data = new int[capacity];
        topIndex = -1;  // initialize the top index to -1 to indicate an empty stack
    }
    
    ~Stack() {
        delete[] data;  // deallocate the dynamic array
    }
    
    void push(int val) {
        if (topIndex == capacity - 1) {
            cout << "Stack overflow" << endl;
            return;
        }
        topIndex++;
        data[topIndex] = val;
    }
    
    void pop() {
        if (topIndex == -1) {
            cout << "Stack underflow" << endl;
            return;
        }
        topIndex--;
    }
    
    int top() {
        if (topIndex == -1) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        return data[topIndex];
    }
    
    bool isEmpty() {
        return (topIndex == -1);
    }
};


int main() {
    Stack myStack(5);  // create a stack with capacity 5
    
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    cout << "Top element: " << myStack.top() << endl;
    myStack.pop();
    cout << "Top element: " << myStack.top() << endl;
    myStack.push(4);
    myStack.push(5);
    myStack.push(6);  // should cause stack overflow error
    while (!myStack.isEmpty()) {
        cout << myStack.top() << " ";
        myStack.pop();
    }
    cout << endl;
    
    return 0;
}

Output :

This implementation defines a Stack class with a dynamic array to store the elements, the maximum capacity, the index of the top element, and four basic operations: push, pop, top, and isEmpty.

In Summarized way:

• The push operation adds an element to the top of the stack, and if the stack is already full, it prints an error message.
• The pop operation removes the top element from the stack; if the stack is empty, it prints an error message.
• The top operation returns the top element of the stack without removing it, and if the stack is already empty, it prints an error message.
• The isEmpty operation returns true if the stack is empty and false otherwise.

The main function demonstrates the usage of the Stack class by creating a stack, pushing, and popping elements, and printing the elements in reverse order.

Here is an example implementation of a stack data structure in C++ using a linked list:

#include <iostream>
using namespace std;


class Node {
public:
    int val;  // value of the node
    Node* next;  // pointer to the next node
};


class Stack {
private:
    Node* head;  // pointer to the head node of the linked list
public:
    Stack() {
        head = NULL;  // initialize the head pointer to NULL to indicate an empty list
    }
    
    ~Stack() {
        while (head != NULL) {  // deallocate all the nodes in the linked list
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
    
    void push(int val) {
        Node* newNode = new Node;  // create a new node
        newNode->val = val;
        newNode->next = head;
        head = newNode;  // update the head pointer to point to the new node
    }
    
    void pop() {
        if (head == NULL) {
            cout << "Stack underflow" << endl;
            return;
        }
        Node* temp = head;
        head = head->next;
        delete temp;  // deallocate the node being removed
    }
    
    int top() {
        if (head == NULL) {
            cout << "Stack is empty" << endl;
            return -1;
        }
        return head->val;
    }
    
    bool isEmpty() {
        return (head == NULL);
    }
};


int main() {
    Stack myStack;
    
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    cout << "Top element: " << myStack.top() << endl;
    myStack.pop();
    cout << "Top element: " << myStack.top() << endl;
    myStack.push(4);
    myStack.push(5);
    myStack.push(6);
    while (!myStack.isEmpty()) {
        cout << myStack.top() << " ";
        myStack.pop();
    }
    cout << endl;
    
    return 0;
}

Output:

Top element: 3
Top element: 2
6 5 4 2 1

Queue

A queue is a data structure that follows the First In First Out (FIFO) principle. It can be visualized as a queue of people waiting in line where the first person who joins the line is the first person to be served. The operations performed on a queue are:

• Enqueue: Add an element to the back of the queue
• Dequeue: Remove the front element from the queue
• Front: Retrieve the front element from the queue without removing it
• Empty: Check if the queue is empty

Complexity analysis

The basic implementation of a queue is using an array. Here is an example code using an array in C++:

Here is an example implementation of a queue data structure in C++ using an array:

#include <iostream>
using namespace std;


const int MAXN = 100;  // maximum size of the queue


class Queue {
private:
    int q[MAXN];  // array to store the elements of the queue
    int front;  // index of the front element
    int rear;  // index of the rear element
public:
    Queue() {
        front = -1;
        rear = -1;  // initialize both front and rear to -1 to indicate an empty queue
    }
    
    bool isEmpty() {
        return (front == -1 && rear == -1);  // the queue is empty if both front and rear are -1
    }
    
    bool isFull() {
        return (rear == MAXN - 1);  // the queue is full if rear has reached the maximum index
    }
    
    void enqueue(int val) {
        if (isFull()) {
            cout << "Queue overflow" << endl;
            return;
        }
        if (isEmpty()) {
            front = 0;  // if the queue is empty, set both front and rear to 0
        }
        rear++;
        q[rear] = val;  // insert the element at the rear of the queue
    }
    
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue underflow" << endl;
            return;
        }
        if (front == rear) {
            front = -1;
            rear = -1;  // if the queue has only one element, set both front and rear to -1 to indicate an empty queue
        }
        else {
            front++;  // increment the front index to remove the front element
        }
    }
    
    int getFront() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        return q[front];  // return the value of the front element
    }
};


int main() {
    Queue myQueue;
    
    myQueue.enqueue(1);
    myQueue.enqueue(2);
    myQueue.enqueue(3);
    cout << "Front element: " << myQueue.getFront() << endl;
    myQueue.dequeue();
    cout << "Front element: " << myQueue.getFront() << endl;
    myQueue.enqueue(4);
    myQueue.enqueue(5);
    myQueue.enqueue(6);
    while (!myQueue.isEmpty()) {
        cout << myQueue.getFront() << " ";
        myQueue.dequeue();
    }
    cout << endl;
    
    return 0;
}

Explanation:

This implementation defines a Queue class that has an array to store the elements of the queue, and two indices front and rear to keep track of the front and rear elements of the queue.

• The isEmpty operation returns true if both front and rear are -1, indicating an empty queue.

• The isFull operation returns true if the rear has reached the maximum index, indicating a full queue.

• The enqueue operation inserts an element at the rear of the queue by incrementing the rear index and inserting the element at the new rear position. It also checks for an overflow condition.

• The dequeue operation removes the element at the front of the queue by incrementing the front index and checking for underflow conditions. If the queue has only one element, it sets both front and rear to -1 to indicate an empty queue.

• The getFront operation returns the value of the front element of the queue, and if the queue is empty, it prints an error message.

The main function demonstrates the usage of the Queue class by creating a queue, enqueueing and dequeuing elements, and printing the front element of the queue.

Output:

In this example, we created a Queue object named queue. We enqueue the elements 1, 2, and 3 and print the front element of the queue, which is 1. We then dequeue the front element, which is 1, and print the new front element, which is 2. We enqueued elements 4, 5, and 6, but when we try to enqueue element 7, we get an overflow error message because the queue is full. We then dequeue all the elements from the queue and print them, which gives us the output 2 3 4 5 6. Finally, we check if the queue is empty by calling the isEmpty operation, which returns true

Types of Queue

Here's a brief overview of each type of queue:

• Single Queue: A single queue is a basic data structure following the First-In-First-Out (FIFO) principle. Elements are inserted from the rear end and deleted from the front end. Single queues can be implemented using arrays or linked lists.

• Circular Queue: A circular queue is a modified version of the linear queue in which the last element points to the first element, making a circular link. In a circular queue, elements are added to the rear end and deleted from the front end. Circular queues can be implemented using arrays or linked lists.

• Priority Queue: A priority queue is a type of queue in which each element is assigned a priority and is inserted in the queue according to its priority. The element with the highest priority is placed at the front of the queue, and the element with the lowest priority is placed at the rear of the queue. Priority queues can be implemented using a variety of data structures such as arrays, linked lists, binary heaps, and balanced binary search trees.

• Deque: A deque, short for the double-ended queue, is a data structure that allows elements to be inserted and deleted from both ends. A deque can be considered a combination of a stack and a queue. It supports operations such as push_front, push_back, pop_front, pop_back, front, and back. Deques can be implemented using arrays or linked lists.

Conclusion: Stack and queue data structures are important concepts in computer science and programming, and understanding their basic principles and implementations is essential for building efficient algorithms and software. Stack and queue are commonly used data structures that follow different principles, but both are useful in various applications.