Linked List, Queue, and Stack in C++

To implement a queue using two stacks in C++, you can use the following approach:

#include 

class Queue {
private:
    std::stack stack1;
    std::stack stack2;

public:
    void enqueue(int value) {
        stack1.push(value);
    }

    int dequeue() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int value = stack2.top();
        stack2.pop();
        return value;
    }
};

int main() {
    Queue queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    std::cout << queue.dequeue() << std::endl; // Output: 1
    std::cout << queue.dequeue() << std::endl; // Output: 2
    std::cout << queue.dequeue() << std::endl; // Output: 3
    return 0;
}

In this implementation, the enqueue operation is performed by pushing elements onto stack1. The dequeue operation is performed by transferring elements from stack1 to stack2 in reverse order, and then popping the top element from stack2.

A scenario where a linked list would be more beneficial to use than a queue or a stack is when frequent insertions and deletions at arbitrary positions in the collection are required. Linked lists provide efficient insertion and deletion operations at any position, as they only require updating the references between nodes. In contrast, queues and stacks have specific insertion and deletion points (front and back for queues, top for stacks) and do not support efficient operations at arbitrary positions. Therefore, if the order of elements is not important and random access is not required, a linked list can be a better choice.

The time complexities of insertion, deletion, and access operations in linked lists, queues, and stacks are as follows:

• Linked List:

  • Insertion at the beginning: O(1)
  • Insertion at the end: O(1) (with a reference to the tail)
  • Insertion at an arbitrary position: O(n)
  • Deletion at the beginning: O(1)
  • Deletion at the end: O(1) (with a reference to the tail)
  • Deletion at an arbitrary position: O(n)
  • Access by index: O(n)

• Queue:

  • Enqueue (insertion at the back): O(1)
  • Dequeue (deletion from the front): O(1)
  • Access to other elements: O(n)

• Stack:

  • Push (insertion at the top): O(1)
  • Pop (deletion from the top): O(1)
  • Access to other elements: O(n)

It's important to note that these time complexities are based on the assumption that the data structures are implemented efficiently, using appropriate data structures and algorithms.

Advantages of using a linked list:

• Dynamic size: Linked lists can grow or shrink dynamically, allowing for efficient memory usage.
• Insertion and deletion: Insertion and deletion operations can be performed in constant time, as long as the position of the element is known.

Disadvantages of using a linked list:

• Random access: Linked lists do not support random access to elements, meaning that accessing an element at a specific index requires traversing the list from the beginning.
• Extra memory: Linked lists require extra memory to store the pointers/references to the next nodes, which can be inefficient for small data types.
• Sequential access: Sequentially accessing elements in a linked list can be slower compared to arrays or vectors due to the lack of cache locality.

To implement a doubly linked list in C++, you can modify the Node class from the previous example to include a pointer to the previous node. Here's an example implementation:

#include 

class Node {
public:
    int data;
    Node* next;
    Node* prev;
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() {
        head = nullptr;
    }

    void insert(int value) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->next = nullptr;
        newNode->prev = nullptr;

        if (head == nullptr) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
            newNode->prev = current;
        }
    }

    void display() {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    DoublyLinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.display();
    return 0;
}

In this implementation, the Node class has an additional prev pointer that points to the previous node in the list. The insert function is modified to update the prev pointer of the new node when inserting it at the end of the list.

Sure! Here's an example function to reverse a linked list in C++:

void reverseLinkedList(LinkedList& list) {
    Node* prev = nullptr;
    Node* current = list.head;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    list.head = prev;
}

This function uses three pointers (prev, current, and next) to reverse the links between the nodes in the linked list. It starts by initializing prev to nullptr, current to the head of the list, and next to nullptr. Then, it iterates through the list, updating the links and moving the pointers until the end of the list is reached. Finally, it updates the head of the list to the last node, effectively reversing the list.

Yes, a stack can be used to check whether a given expression has balanced parentheses. The algorithm works as follows:

1. Initialize an empty stack.
2. Traverse the expression from left to right.
3. If the current character is an opening parenthesis (e.g., '(', '{', '['), push it onto the stack.
4. If the current character is a closing parenthesis (e.g., ')', '}', ']'), check if the stack is empty. If it is, return false as there is no corresponding opening parenthesis. If the stack is not empty, pop the top element from the stack and check if it is the corresponding opening parenthesis. If it is not, return false. If it is, continue to the next character.
5. After traversing the entire expression, check if the stack is empty. If it is, return true as all parentheses are balanced. If it is not, return false as there are unmatched opening parentheses.

Here is an example implementation in C++:

#include 
#include 
#include 

bool isBalanced(const std::string& expression) {
    std::stack parenthesesStack;
    for (char c : expression) {
        if (c == '(' || c == '{' || c == '[') {
            parenthesesStack.push(c);
        }
        else if (c == ')' || c == '}' || c == ']') {
            if (parenthesesStack.empty()) {
                return false;
            }
            char top = parenthesesStack.top();
            parenthesesStack.pop();
            if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return parenthesesStack.empty();
}

int main() {
    std::string expression = "((a + b) * (c - d))";
    if (isBalanced(expression)) {
        std::cout << "The expression has balanced parentheses." << std::endl;
    }
    else {
        std::cout << "The expression does not have balanced parentheses." << std::endl;
    }
    return 0;
}

In a breadth-first search (BFS) algorithm, a queue is used to keep track of the nodes that need to be visited. The algorithm works as follows:

1. Initialize an empty queue and a boolean array to keep track of visited nodes.
2. Enqueue the starting node into the queue and mark it as visited.
3. Repeat the following steps until the queue is empty:
   • Dequeue a node from the front of the queue.
   • Process the node (e.g., print its value or perform any desired operation).
   • Enqueue all the unvisited neighbors of the node into the queue and mark them as visited.
4. The BFS algorithm is complete when all reachable nodes have been visited.

Here is an example implementation in C++:

#include 
#include 
#include 

void breadthFirstSearch(const std::vector>& graph, int startNode) {
    int numNodes = graph.size();
    std::vector visited(numNodes, false);
    std::queue nodeQueue;
    nodeQueue.push(startNode);
    visited[startNode] = true;
    while (!nodeQueue.empty()) {
        int currentNode = nodeQueue.front();
        nodeQueue.pop();
        std::cout << "Visiting node: " << currentNode << std::endl;
        for (int neighbor : graph[currentNode]) {
            if (!visited[neighbor]) {
                nodeQueue.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    std::vector> graph = {
        {1, 2},
        {0, 2, 3},
        {0, 1, 3},
        {1, 2}
    };
    int startNode = 0;
    breadthFirstSearch(graph, startNode);
    return 0;
}

Sure! Here is an example scenario for both a stack and a queue:

Stack: A stack data structure can be useful in a web browser's back button functionality. When a user visits different web pages, the URLs of the visited pages can be stored in a stack. When the user clicks the back button, the most recently visited URL is popped from the stack and the user is redirected to that page.

Queue: A queue data structure can be useful in a print spooler system. When multiple users send print requests to a printer, the requests can be stored in a queue. The printer processes the requests in the order they were added to the queue (FIFO), ensuring fairness and preventing any user from monopolizing the printer.

Both stack and queue data structures have numerous other real-world applications, but these examples illustrate their usefulness in managing and processing data in specific scenarios.

There are several advantages of implementing a stack using a linked list:

1. Dynamic size: Unlike an array-based implementation, a linked list-based implementation allows the stack to grow and shrink dynamically without requiring a fixed size.
2. Efficient insertion and deletion: Insertion and deletion operations can be performed in constant time O(1) at the top of the stack, as they only involve updating the top pointer and creating or deleting a node.
3. No overflow or underflow: Since a linked list can dynamically allocate memory, there is no fixed size limit for the stack, preventing overflow or underflow conditions.
4. Easy implementation: Implementing a stack using a linked list is relatively simple and requires fewer lines of code compared to an array-based implementation.

Yes, it is possible to find the minimum element in a stack in O(1) time by using an additional stack to keep track of the minimum values. Here's an example implementation in C++:

#include 
#include 

using namespace std;

class MinStack {
private:
    stack mainStack;
    stack minStack;
public:
    void push(int value) {
        mainStack.push(value);
        if (minStack.empty() || value <= minStack.top()) {
            minStack.push(value);
        }
    }

    void pop() {
        if (mainStack.empty()) {
            cout << "Stack is empty. Cannot pop." << endl;
            return;
        }
        if (mainStack.top() == minStack.top()) {
            minStack.pop();
        }
        mainStack.pop();
    }

    int getMin() {
        if (minStack.empty()) {
            cout << "Stack is empty." << endl;
            return -1;
        }
        return minStack.top();
    }
};

int main() {
    MinStack stack;
    stack.push(3);
    stack.push(2);
    stack.push(5);
    stack.push(1);
    cout << stack.getMin() << endl; // Output: 1
    stack.pop();
    cout << stack.getMin() << endl; // Output: 2
    stack.pop();
    cout << stack.getMin() << endl; // Output: 2
    return 0;
}

In a stack, underflow occurs when trying to pop an element from an empty stack, and overflow occurs when trying to push an element into a full stack. Here's how you can handle these conditions:

1. Underflow: When popping an element from an empty stack, you can check if the stack is empty before performing the pop operation. If the stack is empty, you can display an error message or throw an exception to indicate that the stack is empty and popping is not possible.

2. Overflow: In a linked list-based implementation, the stack can dynamically allocate memory, so overflow is less likely to occur. However, if you have a fixed-size array-based implementation, you can check if the stack is full before performing the push operation. If the stack is full, you can display an error message or throw an exception to indicate that the stack is full and pushing is not possible.

There are several advantages of a circular queue over a simple queue:

1. Efficient memory utilization: In a circular queue, the elements are stored in a fixed-size array, and the front and rear pointers wrap around the array. This allows the queue to efficiently utilize the available memory.

2. Constant time complexity for enqueue and dequeue operations: In a circular queue, the front and rear pointers are incremented or decremented in a circular manner. This ensures that the enqueue and dequeue operations have a constant time complexity of O(1), regardless of the size of the queue.

3. Ability to reuse empty spaces: In a circular queue, when elements are dequeued, the empty spaces can be reused for future enqueue operations. This reduces the need for resizing the queue and improves the overall efficiency.

To implement a circular queue using an array, you would need to define an array of a fixed size, and two pointers: front and rear. The front pointer points to the first element in the queue, and the rear pointer points to the last element in the queue. Initially, both pointers are set to -1 to indicate an empty queue.

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

#define MAX_SIZE 10

class CircularQueue {
    int arr[MAX_SIZE];
    int front;
    int rear;

public:
    CircularQueue() {
        front = -1;
        rear = -1;
    }

    bool isEmpty() {
        return (front == -1 && rear == -1);
    }

    bool isFull() {
        return (front == (rear + 1) % MAX_SIZE);
    }

    void enqueue(int data) {
        if (isFull()) {
            cout << "Queue is full. Cannot enqueue." << endl;
            return;
        }
        else if (isEmpty()) {
            front = 0;
            rear = 0;
        }
        else {
            rear = (rear + 1) % MAX_SIZE;
        }
        arr[rear] = data;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty. Cannot dequeue." << endl;
            return;
        }
        else if (front == rear) {
            front = -1;
            rear = -1;
        }
        else {
            front = (front + 1) % MAX_SIZE;
        }
    }

    int getFront() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return -1;
        }
        return arr[front];
    }
};

Certainly! Here is an example implementation of functions to insert and delete elements in a circular queue:

#define MAX_SIZE 10

class CircularQueue {
    int arr[MAX_SIZE];
    int front;
    int rear;

public:
    CircularQueue() {
        front = -1;
        rear = -1;
    }

    bool isEmpty() {
        return (front == -1 && rear == -1);
    }

    bool isFull() {
        return (front == (rear + 1) % MAX_SIZE);
    }

    void enqueue(int data) {
        if (isFull()) {
            cout << "Queue is full. Cannot enqueue." << endl;
            return;
        }
        else if (isEmpty()) {
            front = 0;
            rear = 0;
        }
        else {
            rear = (rear + 1) % MAX_SIZE;
        }
        arr[rear] = data;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty. Cannot dequeue." << endl;
            return;
        }
        else if (front == rear) {
            front = -1;
            rear = -1;
        }
        else {
            front = (front + 1) % MAX_SIZE;
        }
    }

    int getFront() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return -1;
        }
        return arr[front];
    }
};

int main() {
    CircularQueue queue;

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

    cout << "Front element: " << queue.getFront() << endl;

    queue.dequeue();

    cout << "Front element after dequeue: " << queue.getFront() << endl;

    return 0;
}