Stacks and Queues

Introduction to Stacks

In the field of computer science and programming, a stack is an abstract data type that represents a collection of elements. It follows the Last-In-First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed.

#include <iostream>
using namespace std;

int main() {
  // Creating a stack using an array
  int stack[5];
  int top = -1;

  // Push operation
  top++;
  stack[top] = 1;
  top++;
  stack[top] = 2;
  top++;
  stack[top] = 3;

  // Pop operation
  top--;

  // Peek operation
  cout << "Top element: " << stack[top] << endl;

  return 0;
}

Let's break down the code snippet above:

• We first declare an array stack which will be used to store the elements of the stack.

• We also declare a variable top to keep track of the index of the top element in the stack.

• In the push operation, we increment top by 1 and assign the element to be added to the stack at stack[top].

• In the pop operation, we decrement top by 1 to remove the top element from the stack.

• In the peek operation, we simply print the top element of the stack.

Using this code snippet as an example, you can see the basic implementation of a stack using an array in C++. The principles and concepts discussed here can be applied to other programming languages as well.

Next, we will dive deeper into implementing the stack data structure and exploring its associated methods.

```c++
#include <iostream>
using namespace std;

int main() {
  // Creating a stack using an array
  int stack[5];
  int top = -1;

  // Push operation
  top++;
  stack[top] = 1;
  top++;
  stack[top] = 2;
  top++;
  stack[top] = 3;

  // Pop operation
  top--;

  // Peek operation
  cout << "Top element: " << stack[top] << endl;

  return 0;
}
```

In a stack, the element that was added first is the first one to be removed.

Implementing a Stack

To implement a stack data structure, we can use a linked list where each element of the stack is represented by a node in the linked list. The top of the stack will be represented by the first node in the linked list.

Let's take a look at the C++ implementation of a stack using a linked list: ```cpp

include

using namespace std;

// Node class to represent individual elements in the stack class Node { public: int data; Node* next; };

// Stack class class Stack { private: Node* top; public: // Constructor Stack() { top = nullptr; }

// Push operation void push(int element) { Node* newNode = new Node; newNode->data = element; newNode->next = top; top = newNode; }

// Pop operation int pop() { if (isEmpty()) { cout << "Stack is empty" << endl; return -1; } int element = top->data; Node* temp = top; top = top->next; delete temp; return element; }

// Peek operation int peek() { if (isEmpty()) { cout << "Stack is empty" << endl; return -1; } return top->data; }

// Check if the stack is empty bool isEmpty() { return top == nullptr; } };

int main() { // Creating a stack Stack stack;

// Pushing elements stack.push(1); stack.push(2); stack.push(3);

// Popping elements cout << stack.pop() << endl; // Output: 3 cout << stack.pop() << endl; // Output: 2

// Peeking element cout << stack.peek() << endl; // Output: 1

// Checking if the stack is empty cout << stack.isEmpty() << endl; // Output: 0

return 0; } ```

```c++
#include <iostream>
using namespace std;

// Node class to represent individual elements in the stack
class Node {
public:
  int data;
  Node* next;
};

// Stack class
class Stack {
private:
  Node* top;
public:
  // Constructor
  Stack() {
    top = nullptr;
  }

  // Push operation
  void push(int element) {
    Node* newNode = new Node;
    newNode->data = element;
    newNode->next = top;
    top = newNode;
  }

  // Pop operation
  int pop() {
    if (isEmpty()) {
      cout << "Stack is empty" << endl;
      return -1;
    }
    int element = top->data;
    Node* temp = top;
    top = top->next;
    delete temp;
    return element;
  }

  // Peek operation
  int peek() {
    if (isEmpty()) {
      cout << "Stack is empty" << endl;
      return -1;
    }
    return top->data;
  }

  // Check if the stack is empty
  bool isEmpty() {
    return top == nullptr;
  }
};

int main() {
  // Creating a stack
  Stack stack;

  // Pushing elements
  stack.push(1);
  stack.push(2);
  stack.push(3);

  // Popping elements
  cout << stack.pop() << endl; // Output: 3
  cout << stack.pop() << endl; // Output: 2

  // Peeking element
  cout << stack.peek() << endl; // Output: 1

  // Checking if the stack is empty
  cout << stack.isEmpty() << endl; // Output: 0

  return 0;
}
```

Which data structure can be used to implement a stack?

Now that we have implemented a stack data structure, let's explore the various operations that can be performed on a stack. These operations include:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.
3. Peek: Retrieves the top element of the stack without removing it.

The push operation is used to add elements to the stack. When a new element is pushed onto the stack, it becomes the new top element. The pop operation, on the other hand, removes the top element from the stack. Lastly, the peek operation allows us to see the top element of the stack without removing it.

Let's take a look at an example implementation of these stack operations in C++: ```cpp

include

using namespace std;

class Stack { private: int arr[100]; int top;

public: Stack() { top = -1; }

void push(int element) { if (top >= 99) { cout << "Stack Overflow" << endl; } else { arr[++top] = element; } }

int pop() { if (top < 0) { cout << "Stack Underflow" << endl; return -1; } else { return arr[top--]; } }

int peek() { if (top < 0) { cout << "Stack is empty" << endl; return -1; } else { return arr[top]; } } };

int main() { Stack stack;

// Pushing elements stack.push(1); stack.push(2); stack.push(3);

// Popping elements cout << stack.pop() << endl; // Output: 3 cout << stack.pop() << endl; // Output: 2

// Peeking element cout << stack.peek() << endl; // Output: 1

return 0; } ```

The push operation is used to add elements to the stack.

Now that we have learned about the stack data structure and its operations, let's explore some real-world applications where stacks are commonly used.

1. Function Call Stack:

In programming languages, such as C++, the function call stack is an important application of stacks. Whenever a function is called, its parameters, return address, and local variables are stored in a stack frame. The function parameters and variables are pushed onto the stack, and when the function returns, its stack frame is popped off the stack.

Here's an example in C++: ```cpp

include

using namespace std;

void functionB(int n) { if (n > 0) { functionA(n - 1); } }

void functionA(int n) { if (n > 0) { functionB(n - 1); } }

int main() { functionA(5); return 0; } ```

```c++
#include <iostream>
using namespace std;

int main() {
  // Code snippet goes here
  return 0;
}
```

One common application of stacks is in the implementation of _______________. In this representation, an expression is first converted into a postfix notation. Then, the postfix notation can be evaluated efficiently using a stack. The stack is used to store the operands and intermediate results of the expression evaluation. The process involves scanning the postfix notation from left to right. Whenever an operand is encountered, it is pushed onto the stack. When an operator is encountered, the top two operands from the stack are popped and the operator is applied to them. The result is then pushed back onto the stack. This process continues until the entire postfix notation is scanned and the final result is obtained from the stack.

A queue is a fundamental data structure in computer science that represents a collection of items where the operations are arranged in a FIFO (First In First Out) format. In a queue, the element that is inserted first is the first one to be removed. The two primary operations associated with queues are enqueue and dequeue.

In real-world scenarios, queues can be compared to everyday situations like waiting in line at a supermarket or standing in a queue for tickets to a movie. The first person who arrives in the line is the first person to be served or to get the tickets.

Let's take a look at an example to demonstrate the implementation of queues in C++: ```cpp

include

include

using namespace std;

int main() { // Create an empty queue queue q;

// Enqueue elements q.push(10); q.push(20); q.push(30);

// Dequeue elements cout << "Dequeued element: " << q.front() << endl; q.pop(); cout << "Dequeued element: " << q.front() << endl; q.pop();

return 0; } ```

The above code demonstrates the implementation of a queue using the C++ standard library queue container. Firstly, we create an empty queue q. Then, we enqueue elements using the push function. Finally, we dequeue elements using the front function to retrieve the front element, and the pop function to remove the front element.

Now that we have understood the basic concept and implementation of queues, let's explore further operations and applications of queues in the upcoming lessons.

```c++
#include <iostream>
using namespace std;

int main() {
  // C++ code for introduction to queues
  cout << "Introduction to Queues in C++" << endl;
  return 0;
}
```

Which of the following best describes the behavior of a queue?

In order to implement a queue in C++, we can use the concept of linked lists. A queue can be represented as a linked list where each element is a node containing a data value and a pointer to the next node. The front and rear of the queue will be pointers to the first and last nodes, respectively.

Here is an implementation of a queue using linked lists in C++:

#include <iostream>
using namespace std;

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

// Queue class
class Queue {
private:
    Node* front;
    Node* rear;

public:
    // Constructor
    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    // Check if queue is empty
    bool isEmpty() {
        return (front == nullptr);
    }

    // Enqueue an element
    void enqueue(int item) {
        Node* newNode = new Node;
        newNode->data = item;
        newNode->next = nullptr;

        if (isEmpty()) {
            front = rear = newNode;
        }
        else {
            rear->next = newNode;
            rear = newNode;
        }

        cout << "Enqueued: " << item << endl;
    }

    // Dequeue an element
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
        }
        else {
            Node* temp = front;
            cout << "Dequeued: " << front->data << endl;
            front = front->next;

            delete temp;
        }
    }

    // Get the front element
    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        else {
            return front->data;
        }
    }
};

int main() {
    // Create a queue object
    Queue q;

    // Enqueue elements
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    // Dequeue elements
    q.dequeue();
    q.dequeue();

    // Get the front element
    int front = q.getFront();
    cout << "Front element: " << front << endl;

    return 0;
}

```c++
#include <iostream>
using namespace std;

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

// Queue class
class Queue {
private:
    Node* front;
    Node* rear;

public:
    // Constructor
    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    // Check if queue is empty
    bool isEmpty() {
        return (front == nullptr);
    }

    // Enqueue an element
    void enqueue(int item) {
        Node* newNode = new Node;
        newNode->data = item;
        newNode->next = nullptr;

        if (isEmpty()) {
            front = rear = newNode;
        }
        else {
            rear->next = newNode;
            rear = newNode;
        }

        cout << "Enqueued: " << item << endl;
    }

    // Dequeue an element
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
        }
        else {
            Node* temp = front;
            cout << "Dequeued: " << front->data << endl;
            front = front->next;

            delete temp;
        }
    }

    // Get the front element
    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        else {
            return front->data;
        }
    }
};

int main() {
    // Create a queue object
    Queue q;

    // Enqueue elements
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    // Dequeue elements
    q.dequeue();
    q.dequeue();

    // Get the front element
    int front = q.getFront();
    cout << "Front element: " << front << endl;

    return 0;
}
```

Which of the following is NOT a best practice when implementing a queue?

In the previous section, we discussed how to implement a queue using a linked list. Now, let's dive into the various operations that we can perform on a queue.

1. Enqueue: The enqueue operation adds an element to the rear of the queue. In simple terms, it puts an item at the end of the line. To enqueue an element, we create a new node with the given data value and add it to the rear of the queue. If the queue is empty, we update both the front and rear pointers to the new node.

void enqueue(int item) {
    Node* newNode = new Node;
    newNode->data = item;
    newNode->next = nullptr;

    if (isEmpty()) {
        front = rear = newNode;
    }
    else {
        rear->next = newNode;
        rear = newNode;
    }
}

1. Dequeue: The dequeue operation removes an element from the front of the queue. In simple terms, it takes an item off from the front of the line. To dequeue an element, we remove the front node from the queue and update the front pointer to the next node. If the queue becomes empty after the dequeue operation, we update the rear pointer to null as well.

void dequeue() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
    }
    else {
        Node* temp = front;
        cout << "Dequeued: " << front->data << endl;
        front = front->next;

        delete temp;
    }
}

1. Get Front: The getFront operation returns the data value of the front node without removing it from the queue. If the queue is empty, we return -1 to indicate an error.

int getFront() {
    if (isEmpty()) {
        return -1;
    }
    else {
        return front->data;
    }
}

Now that we have seen the basic queue operations, let's put them to use in an example:

#include <iostream>
using namespace std;

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

// Queue class
class Queue {
private:
    Node* front;
    Node* rear;

public:
    // Constructor
    Queue() {
        front = nullptr;
        rear = nullptr;
    }

    // Check if queue is empty
    bool isEmpty() {
        return (front == nullptr);
    }

    // Enqueue an element
    void enqueue(int item) {
        Node* newNode = new Node;
        newNode->data = item;
        newNode->next = nullptr;

        if (isEmpty()) {
            front = rear = newNode;
        }
        else {
            rear->next = newNode;
            rear = newNode;
        }
    }

    // Dequeue an element
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
        }
        else {
            Node* temp = front;
            cout << "Dequeued: " << front->data << endl;
            front = front->next;

            delete temp;
        }
    }

    // Get the front element
    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        else {
            return front->data;
        }
    }
};

int main() {
    // Create a queue object
    Queue q;

    // Enqueue elements
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    // Dequeue elements
    q.dequeue();
    q.dequeue();

    // Get the front element
    int front = q.getFront();
    cout << "Front element: " << front << endl;

    return 0;
}

This is a simple example that demonstrates the enqueue, dequeue, and getFront operations.

In the next section, we will explore the applications of queues in various real-world scenarios.

```c++
#include <iostream>
using namespace std;

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

// Queue class
class Queue {
private:
    Node* front;
    Node* rear;
public:
    // Constructor
    Queue() {
        front = nullptr;
        rear = nullptr;
    }
    // Check if queue is empty
    bool isEmpty() {
        return (front == nullptr);
    }
    // Enqueue an element
    void enqueue(int item) {
        Node* newNode = new Node;
        newNode->data = item;
        newNode->next = nullptr;
        if (isEmpty()) {
            front = rear = newNode;
        }
        else {
            rear->next = newNode;
            rear = newNode;
        }
    }
    // Dequeue an element
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
        }
        else {
            Node* temp = front;
            cout << "Dequeued: " << front->data << endl;
            front = front->next;
            delete temp;
        }
    }
    // Get the front element
    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        else {
            return front->data;
        }
    }
};

int main() {
    // Create a queue object
    Queue q;
    // Enqueue elements
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    // Dequeue elements
    q.dequeue();
    q.dequeue();
    // Get the front element
    int front = q.getFront();
    cout << "Front element: " << front << endl;
    return 0;
}
```

Which operation adds an element to the rear of the queue?

In the previous section, we explored the basic operations of a queue. Now, let's delve into the real-world applications of queues and understand why they are an essential data structure.

1. Task Scheduling

Queues are commonly used in task scheduling systems. Consider a scenario where different tasks with varying priorities need to be executed. A queue can be used to order the tasks based on their priority and ensure they are executed in the correct order.

2. Message Queuing

In distributed systems, queues play a crucial role in implementing reliable message delivery. They enable decoupling between the sender and receiver, allowing messages to be sent asynchronously. Applications can enqueue messages in the sender's queue, and the receiver can efficiently dequeue and process them at its own pace.

3. Printer Spooling

Printers often employ a queue to manage multiple print jobs. Each print job is enqueued in the printer's queue, and they are processed one by one in the order they were added. This ensures fair resource allocation and prevents one print job from monopolizing the printer for an extended period.

4. Call Center Management

In call centers, queues are used to handle incoming calls. When all call center agents are occupied, incoming calls are put in a queue until an agent becomes available. The queued calls are then serviced in the order they arrived.

5. Breadth-First Search

Queues also play a crucial role in graph traversal algorithms such as breadth-first search (BFS). BFS explores a graph level by level, visiting all the neighbors of a node before moving to the next level. A queue is used to keep track of the nodes to be visited in the next level.

These are just a few examples of the many real-world applications of queues. Understanding queues and their applications can help you solve a wide range of problems efficiently.

Now that we have explored the applications of queues, let's move on to the next topic in our course: Trees!

```c++
#include <iostream>
using namespace std;

int main() {
  // Replace with relevant content
}

```

Queues are commonly used in task scheduling systems.

Generating complete for this lesson!