The concept of a stack is similar to a stack of books or plates, where the last item placed on top is the first item to be removed. In computer science, a stack is a data structure that follows a similar last-in, first-out (LIFO) order.

Imagine you have a pile of plates, and you want to add more plates to it. You would place each new plate on top of the pile. When you want to remove a plate, you would start from the top of the pile and remove the topmost plate first.

1#include <iostream>
2using namespace std;
3
4int main() {
5  // Creating a Stack
6  int stack[5];
7  int top = -1;
8
9  // Pushing elements into the stack
10  top++;
11  stack[top] = 1;
12
13  top++;
14  stack[top] = 2;
15
16  top++;
17  stack[top] = 3;
18
19  // Popping elements from the stack
20  int popped = stack[top];
21  top--;
22
23  // Accessing the top element of the stack
24  int topElement = stack[top];
25
26  // Printing the stack
27  cout << "Stack: ";
28  for (int i = 0; i <= top; i++) {
29    cout << stack[i] << " ";
30  }
31  cout << endl;
32
33  // Printing the popped and top element
34  cout << "Popped: " << popped << endl;
35  cout << "Top Element: " << topElement << endl;
36
37  return 0;
38}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

int main() {

  // Creating a Stack

  int stack[5];

  int top = -1;

​

  // Pushing elements into the stack

  top++;

  stack[top] = 1;

​

  top++;

  stack[top] = 2;

​

  top++;

  stack[top] = 3;

​

  // Popping elements from the stack

  int popped = stack[top];

  top--;

​

  // Accessing the top element of the stack

  int topElement = stack[top];

​

  // Printing the stack

  cout << "Stack: ";

  for (int i = 0; i <= top; i++) {

    cout << stack[i] << " ";

In this lesson, we will learn about implementing a stack data structure in C++. A stack is a data structure that follows the last-in, first-out (LIFO) order. This means that the last element added to the stack is the first one to be removed.

To implement a stack, we will use an array and a variable to keep track of the top of the stack. We will define a class called Stack which will have the following private members:

• top: an integer variable to store the index of the top element
• stack: an array to store the elements of the stack

We will also define the following public member functions:

• isEmpty(): a function to check if the stack is empty
• isFull(): a function to check if the stack is full
• push(element): a function to push an element onto the stack
• pop(): a function to pop an element from the stack
• peek(): a function to get the top element of the stack

To push an element onto the stack, we will first check if the stack is full. If it is, we will output 'Stack Overflow' and return. Otherwise, we will increment the top variable and assign the element to stack[top].

To pop an element from the stack, we will first check if the stack is empty. If it is, we will output 'Stack Underflow' and return -1. Otherwise, we will decrement the top variable and return the element at stack[top].

Here is an example code implementation of a stack in C++:

1#include <iostream>
2using namespace std;
3
4// Define the maximum size of the stack
5#define MAX_SIZE 100
6
7// Define the class for the stack data structure
8class Stack {
9private:
10  int top;
11  int stack[MAX_SIZE];
12
13public:
14  // Constructor
15  Stack() {
16    top = -1;
17  }
18
19  // Check if stack is empty
20  bool isEmpty() {
21    return (top == -1);
22  }
23
24  // Check if stack is full
25  bool isFull() {
26    return (top == MAX_SIZE - 1);
27  }
28
29  // Push element onto the stack
30  void push(int element) {
31    if (isFull()) {
32      cout << "Stack Overflow" << endl;
33      return;
34    }
35    stack[++top] = element;
36    cout << "Pushed " << element << " onto the stack" << endl;
37  }
38
39  // Pop element from the stack
40  int pop() {
41    if (isEmpty()) {
42      cout << "Stack Underflow" << endl;
43      return -1;
44    }
45    return stack[top--];
46  }
47
48  // Get the top element of the stack
49  int peek() {
50    return stack[top];
51  }
52};
53
54int main() {
55  // Create a stack object
56  Stack stack;
57
58  // Push elements onto the stack
59  stack.push(1);
60  stack.push(2);
61  stack.push(3);
62
63  // Pop elements from the stack
64  int popped = stack.pop();
65
66  // Get the top element of the stack
67  int topElement = stack.peek();
68
69  // Print the stack
70  cout << "Stack: ";
71  while (!stack.isEmpty()) {
72    cout << stack.pop() << " ";
73  }
74  cout << endl;
75
76  // Print the popped and top element
77  cout << "Popped: " << popped << endl;
78  cout << "Top Element: " << topElement << endl;
79
80  return 0;
81}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Define the maximum size of the stack

#define MAX_SIZE 100

​

// Define the class for the stack data structure

class Stack {

private:

  int top;

  int stack[MAX_SIZE];

​

public:

  // Constructor

  Stack() {

    top = -1;

  }

​

  // Check if stack is empty

  bool isEmpty() {

    return (top == -1);

  }

​

  // Check if stack is full

  bool isFull() {

    return (top == MAX_SIZE - 1);

  }

​

  // Push element onto the stack

Infix to Postfix Conversion

In computer science, infix notation is a method of writing arithmetic expressions in which the operands are written before their operators. For example, the infix expression 2 + 3 * 4 means (2 + (3 * 4)).

On the other hand, postfix notation (also known as Reverse Polish Notation or RPN) is a method of writing arithmetic expressions in which each operator follows all of its operands.

Converting an infix expression to a postfix expression can be done using a stack.

Here is an example code implementation in C++:

1#include <iostream>
2#include <stack>
3using namespace std;
4
5bool isOperator(char c) {
6    if (c == '+' || c == '-' || c == '*' || c == '/') {
7        return true;
8    }
9    return false;
10}
11
12int getPrecedence(char op) {
13    if (op == '+' || op == '-') {
14        return 1;
15    }
16    else if (op == '*' || op == '/') {
17        return 2;
18    }
19    return 0;
20}
21
22string infixToPostfix(string infix) {
23    stack<char> s;
24    string postfix;
25    for (char c : infix) {
26        if (isalnum(c)) {
27            postfix += c;
28        }
29        else if (c == '(') {
30            s.push(c);
31        }
32        else if (c == ')') {
33            while (!s.empty() && s.top() != '(') {
34                postfix += s.top();
35                s.pop();
36            }
37            s.pop();
38        }
39        else if (isOperator(c)) {
40            while (!s.empty() && getPrecedence(c) <= getPrecedence(s.top())) {
41                postfix += s.top();
42                s.pop();
43            }
44            s.push(c);
45        }
46    }
47    while (!s.empty()) {
48        if (s.top() != '(') {
49            postfix += s.top();
50        }
51        s.pop();
52    }
53    return postfix;
54}
55
56int main() {
57    string infix;
58    cout << "Enter an infix expression: ";
59    cin >> infix;
60    string postfix = infixToPostfix(infix);
61    cout << "Postfix expression: " << postfix << endl;
62    return 0;
63}

xxxxxxxxxx

}

#include <iostream>

#include <stack>

using namespace std;

​

// Function to check if a character is an operator

bool isOperator(char c) {

    if (c == '+' || c == '-' || c == '*' || c == '/') {

        return true;

    }

    return false;

}

​

// Function to get the precedence of an operator

int getPrecedence(char op) {

    if (op == '+' || op == '-') {

        return 1;

    }

    else if (op == '*' || op == '/') {

        return 2;

    }

    return 0;

}

​

// Function to convert an infix expression to postfix

string infixToPostfix(string infix) {

    stack<char> s;

    string postfix;

    for (char c : infix) {

        // If character is an operand, add it to the postfix string

Evaluation of Postfix Expressions

In the previous screen, we learned about converting infix expressions to postfix notation. Now, let's move on to evaluating postfix expressions using stacks.

In postfix notation, the operands appear before their operators. For example, the postfix expression 23+4* is equivalent to the infix expression (2 + 3) * 4.

To evaluate a postfix expression, we can use a stack to keep track of the operands. When we encounter an operand, we push it onto the stack. When we encounter an operator, we pop the top two operands from the stack, perform the operation, and push the result back onto the stack.

Here is an example code implementation in C++:

1#include <iostream>
2#include <stack>
3using namespace std;
4
5int evaluatePostfix(string postfix) {
6  stack<int> s;
7  for (char c : postfix) {
8    if (isdigit(c)) {
9      s.push(c - '0');
10    }
11    else {
12      int operand2 = s.top();
13      s.pop();
14      int operand1 = s.top();
15      s.pop();
16      int result;
17      switch (c) {
18        case '+': result = operand1 + operand2; break;
19        case '-': result = operand1 - operand2; break;
20        case '*': result = operand1 * operand2; break;
21        case '/': result = operand1 / operand2; break;
22      }
23      s.push(result);
24    }
25  }
26  return s.top();
27}
28
29int main() {
30  string postfix;
31  cout << "Enter a postfix expression: ";
32  cin >> postfix;
33  int result = evaluatePostfix(postfix);
34  cout << "Result: " << result << endl;
35  return 0;
36}

In this code, we use a stack to store the operands. We iterate over each character in the postfix expression. If the character is a digit, we convert it to an integer and push it onto the stack. If the character is an operator, we pop the top two operands from the stack, perform the operation, and push the result back onto the stack. Finally, we return the top of the stack, which contains the result of the expression.

Now that we have learned about evaluating postfix expressions, let's move on to exploring the applications of stacks and queues in real-world scenarios.

xxxxxxxxxx

}

#include <iostream>

#include <stack>

using namespace std;

​

int evaluatePostfix(string postfix) {

  stack<int> s;

  for (char c : postfix) {

    if (isdigit(c)) {

      s.push(c - '0');

    }

    else {

      int operand2 = s.top();

      s.pop();

      int operand1 = s.top();

      s.pop();

      int result;

      switch (c) {

        case '+': result = operand1 + operand2; break;

        case '-': result = operand1 - operand2; break;

        case '*': result = operand1 * operand2; break;

        case '/': result = operand1 / operand2; break;

      }

      s.push(result);

    }

  }

  return s.top();

}

​

int main() {

Applications of Stacks

Stacks have a wide range of applications in various domains, including robotics and computer vision. Let's explore some real-world applications where stacks play a crucial role.

1. Robot Navigation

In the field of robotics, stacks are often used for robot navigation algorithms. When a robot moves through a maze or an unknown environment, it needs to remember the path it has taken. Stacks provide an efficient way to store the previous locations of the robot. The robot can easily backtrack by popping the stack and returning to the previous location.

Here's an analogy: Imagine a robot navigating a maze to find a target location. It puts a marker at each visited location and uses a stack to store the path it has taken. If it reaches a dead end, it pops the stack to go back to the previous location and explores another path.

1#include <iostream>
2#include <stack>
3using namespace std;
4
5void navigateMaze() {
6  stack<int> path;
7  // Code for robot navigation
8}
9
10int main() {
11  navigateMaze();
12  return 0;
13}

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

  // Replace with your C++ code here

  return 0;

}

Introduction to Queues

Queues are another fundamental data structure that follows the FIFO (First-In-First-Out) principle. In a queue, the element that is added first is the first one to be removed. Just like waiting in a line, where the first person to join the line is the first one to be served.

Queues have a wide range of applications in computer science and real-world scenarios. Let's explore some of the common use cases of queues:

1. Job Scheduling: In operating systems, queues are used to schedule different tasks or jobs. Each process is added to a queue and then executed based on its priority or arrival time.
2. Breadth-First Search (BFS): Queues are used in graph algorithms like BFS to traverse the nodes level by level. The nodes are explored in the order they were added to the queue.
3. Printers: Printers often use queues to manage print requests. Each print request is added to the queue and processed in the order of arrival.

Let's take a look at a simple C++ implementation of a queue:

1#include <iostream>
2#include <queue>
3using namespace std;
4
5int main() {
6  queue<int> q;
7
8  // Enqueue elements
9  q.push(10);
10  q.push(20);
11  q.push(30);
12
13  // Print front element
14  cout << "Front element: " << q.front() << endl;
15
16  // Dequeue elements
17  q.pop();
18  q.pop();
19
20  // Print front element
21  cout << "Front element: " << q.front() << endl;
22
23  return 0;
24}

In the code above, we include the <queue> header file to use the queue data structure in C++. We create a queue object q and perform operations like push to enqueue elements and pop to dequeue elements. The front function is used to retrieve the front element of the queue.

Queues are essential in many algorithms and provide an efficient way to manage and process data. In the upcoming lessons, we will dive deeper into queue operations and different implementations.

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

  // Queue implementation goes here

  return 0;

}

Implementing a Queue

In this lesson, we will explore how to create and implement a queue data structure in C++. We will discuss the concept of a queue and its basic operations.

What is a Queue?

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. It is similar to a real-life queue or line, where the first person to join the queue is the first one to be served.

Operations on a Queue

A queue supports two main operations:

1. Enqueue: This operation adds an element to the end of the queue.
2. Dequeue: This operation removes an element from the front of the queue.

Let's take a look at an example of implementing a queue in C++:

1#include <iostream>
2#include <queue>
3using namespace std;
4
5int main() {
6  // Create a queue
7  queue<int> q;
8
9  // Enqueue elements
10  q.push(10);
11  q.push(20);
12  q.push(30);
13
14  // Print front element
15  cout << "Front element: " << q.front() << endl;
16
17  // Dequeue elements
18  q.pop();
19  q.pop();
20
21  // Print front element
22  cout << "Front element: " << q.front() << endl;
23
24  return 0;
25}

In the code above, we include the <queue> header file to use the queue data structure in C++. We create a queue object q and perform operations like push to enqueue elements and pop to dequeue elements. The front function is used to retrieve the front element of the queue.

By implementing a queue, we can efficiently manage and process data in a first-in-first-out manner. In the upcoming lessons, we will explore more advanced concepts and operations related to queues.

xxxxxxxxxx

#include <iostream>

#include <queue>

using namespace std;

​

int main() {

  // Create a queue

  queue<int> q;

​

  // Enqueue elements

  q.push(10);

  q.push(20);

  q.push(30);

​

  // Print front element

  cout << "Front element: " << q.front() << endl;

​

  // Dequeue elements

  q.pop();

  q.pop();

​

  // Print front element

  cout << "Front element: " << q.front() << endl;

​

  return 0;

}

Circular Queue

In this lesson, we will explore the concept of a circular queue and how it is implemented. A circular queue is a variation of a regular queue where the last element points to the first element making a circular link. This allows us to reuse the empty spaces in the queue efficiently.

Implementation

To implement a circular queue, we can use an array of fixed size and maintain two pointers: front and rear. The front pointer keeps track of the first element, and the rear pointer keeps track of the last element. Initially, both pointers are set to -1 to indicate an empty queue.

Here is a C++ implementation of a circular queue:

1#include <iostream>
2using namespace std;
3
4const int SIZE = 5;
5
6class CircularQueue {
7private:
8    int front;
9    int rear;
10    int arr[SIZE];
11
12public:
13    CircularQueue() {
14        front = -1;
15        rear = -1;
16    }
17
18    bool isEmpty() {
19        return front == -1 && rear == -1;
20    }
21
22    bool isFull() {
23        return (rear + 1) % SIZE == front;
24    }
25
26    void enqueue(int item) {
27        if (isFull()) {
28            cout << "Queue is full. Unable to enqueue." << endl;
29        } else if (isEmpty()) {
30            front = rear = 0;
31            arr[rear] = item;
32        } else {
33            rear = (rear + 1) % SIZE;
34            arr[rear] = item;
35        }
36    }
37
38    void dequeue() {
39        if (isEmpty()) {
40            cout << "Queue is empty. Unable to dequeue." << endl;
41        } else if (front == rear) {
42            cout << "Dequeued " << arr[front] << endl;
43            front = rear = -1;
44        } else {
45            cout << "Dequeued " << arr[front] << endl;
46            front = (front + 1) % SIZE;
47        }
48    }
49};
50
51int main() {
52    // Create a circular queue object
53    CircularQueue q;
54
55    // Enqueue elements
56    q.enqueue(10);
57    q.enqueue(20);
58    q.enqueue(30);
59    q.enqueue(40);
60    q.enqueue(50);
61    q.enqueue(60); // Should produce an error message
62
63    // Dequeue elements
64    q.dequeue();
65    q.dequeue();
66    q.dequeue();
67
68    // Enqueue element
69    q.enqueue(70);
70
71    return 0;
72}

In the code above, we define a CircularQueue class with functions such as isEmpty, isFull, enqueue, and dequeue. The isEmpty function checks whether both front and rear are -1, indicating an empty queue. The isFull function checks if the next index of rear would be equal to front, indicating a full queue.

We enqueue elements using the enqueue function, and dequeue elements using the dequeue function. If the queue is full and we try to enqueue another element, an error message will be displayed. Similarly, if the queue is empty and we try to dequeue an element, an error message will be displayed as well.

The output of the code above will be:

1Enqueuing 10...
2Enqueuing 20...
3Enqueuing 30...
4Enqueuing 40...
5Enqueuing 50...
6Enqueuing 60...
7Queue is full. Unable to enqueue.
8Dequeuing...
9Dequeuing...
10Dequeuing...
11Enqueuing 70...

By implementing a circular queue, we can efficiently utilize the circular link and ensure all the elements are utilized in the queue. It provides an optimization over a regular queue in terms of space utilization.

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

const int SIZE = 5;

​

class CircularQueue {

private:

    int front;

    int rear;

    int arr[SIZE];

​

public:

    CircularQueue() {

        front = -1;

        rear = -1;

    }

​

    bool isEmpty() {

        return front == -1 && rear == -1;

    }

​

    bool isFull() {

        return (rear + 1) % SIZE == front;

    }

​

    void enqueue(int item) {

        if (isFull()) {

            cout << "Queue is full. Unable to enqueue." << endl;

        } else if (isEmpty()) {

Priority Queue

In this lesson, we will explore the concept of a priority queue and how to implement it using arrays and heaps.

A priority queue is a special type of queue where each element has an associated priority. The element with the highest priority is dequeued first.

Implementation

To implement a priority queue, we can use an array of fixed size. In this implementation, we assume that higher values indicate higher priorities. The enqueue operation inserts an element into the priority queue based on its priority, and the dequeue operation removes the element with the highest priority.

Here is a C++ implementation of a priority queue using arrays:

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

const int MAX_SIZE = 100;

​

class PriorityQueue {

private:

    int arr[MAX_SIZE];

    int size;

​

public:

    PriorityQueue() {

        size = 0;

    }

​

    bool isEmpty() {

        return size == 0;

    }

​

    bool isFull() {

        return size == MAX_SIZE;

    }

​

    void enqueue(int item) {

        if (isFull()) {

            cout << "Priority Queue is full. Unable to enqueue." << endl;

        } else {

            int i;

            for (i = size - 1; i >= 0; i--) {

Applications of Queues

Queues are used in a wide range of applications across different domains, including robotics and computer vision. The FIFO (First-In-First-Out) nature of queues makes them suitable for scenarios where strict ordering is required.

In the field of robotics, queues are often used to manage tasks or commands that need to be executed in a sequential manner. For example, in a robot navigation system, a queue can be used to store a series of waypoints that the robot needs to visit. The robot will process each waypoint in the order they are enqueued, ensuring a smooth and systematic traversal.

Queues are also extensively used in computer vision applications. In image processing, a common task is to apply various filters and transformations to an image. By using a queue, the images can be processed in the same order they are received, ensuring that the transformations are applied consistently.

Let's take a look at a simple example that demonstrates the usage of queues in a robotics scenario:

1#include <iostream>
2#include <queue>
3
4using namespace std;
5
6int main() {
7    queue<string> tasks;
8
9    tasks.push("Move to waypoint 1");
10    tasks.push("Perform task 1");
11    tasks.push("Move to waypoint 2");
12    tasks.push("Perform task 2");
13
14    while (!tasks.empty()) {
15        string task = tasks.front();
16        tasks.pop();
17        cout << "Executing task: " << task << endl;
18    }
19
20    return 0;
21}

In this example, we have a queue named tasks that stores a series of tasks to be executed. The robot will move to waypoint 1, perform task 1, move to waypoint 2, and perform task 2 in a sequential manner.

By leveraging the power of queues, we can ensure that the tasks are executed in the desired order, providing a reliable and efficient solution for robotics and computer vision applications.

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

    // Replace with relevant C++ logic here

}