AlgoDaily - Stacks and Queues

Home > 30 days c++ course > 30 days c++ course > 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.

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4int main() {
5  // Creating a stack using an array
6  int stack[5];
7  int top = -1;
8
9  // Push operation
10  top++;
11  stack[top] = 1;
12  top++;
13  stack[top] = 2;
14  top++;
15  stack[top] = 3;
16
17  // Pop operation
18  top--;
19
20  // Peek operation
21  cout << "Top element: " << stack[top] << endl;
22
23  return 0;
24}

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.

xxxxxxxxxx
 
#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;
}

Are you sure you're getting this? Is this statement true or false?

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

Press true if you believe the statement is correct, or false otherwise.

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:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Node class to represent individual elements in the stack
5class Node {
6public:
7  int data;
8  Node* next;
9};
10
11// Stack class
12class Stack {
13private:
14  Node* top;
15public:
16  // Constructor
17  Stack() {
18    top = nullptr;
19  }
20
21  // Push operation
22  void push(int element) {
23    Node* newNode = new Node;
24    newNode->data = element;
25    newNode->next = top;
26    top = newNode;
27  }
28
29  // Pop operation
30  int pop() {
31    if (isEmpty()) {
32      cout << "Stack is empty" << endl;
33      return -1;
34    }
35    int element = top->data;
36    Node* temp = top;
37    top = top->next;
38    delete temp;
39    return element;
40  }
41
42  // Peek operation
43  int peek() {
44    if (isEmpty()) {
45      cout << "Stack is empty" << endl;
46      return -1;
47    }
48    return top->data;
49  }
50
51  // Check if the stack is empty
52  bool isEmpty() {
53    return top == nullptr;
54  }
55};
56
57int main() {
58  // Creating a stack
59  Stack stack;
60
61  // Pushing elements
62  stack.push(1);
63  stack.push(2);
64  stack.push(3);
65
66  // Popping elements
67  cout << stack.pop() << endl; // Output: 3
68  cout << stack.pop() << endl; // Output: 2
69
70  // Peeking element
71  cout << stack.peek() << endl; // Output: 1
72
73  // Checking if the stack is empty
74  cout << stack.isEmpty() << endl; // Output: 0
75
76  return 0;
77}

xxxxxxxxxx
}
 
#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

Let's test your knowledge. Click the correct answer from the options.

Which data structure can be used to implement a stack?

Click the option that best answers the question.

Array
Linked List
Tree
Graph

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:

Push: Adds an element to the top of the stack.
Pop: Removes the top element from the stack.
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++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4class Stack {
5private:
6  int arr[100];
7  int top;
8
9public:
10  Stack() {
11    top = -1;
12  }
13
14  void push(int element) {
15    if (top >= 99) {
16      cout << "Stack Overflow" << endl;
17    } else {
18      arr[++top] = element;
19    }
20  }
21
22  int pop() {
23    if (top < 0) {
24      cout << "Stack Underflow" << endl;
25      return -1;
26    } else {
27      return arr[top--];
28    }
29  }
30
31  int peek() {
32    if (top < 0) {
33      cout << "Stack is empty" << endl;
34      return -1;
35    } else {
36      return arr[top];
37    }
38  }
39};
40
41int main() {
42  Stack stack;
43
44  // Pushing elements
45  stack.push(1);
46  stack.push(2);
47  stack.push(3);
48
49  // Popping elements
50  cout << stack.pop() << endl; // Output: 3
51  cout << stack.pop() << endl; // Output: 2
52
53  // Peeking element
54  cout << stack.peek() << endl; // Output: 1
55
56  return 0;
57}

Build your intuition. Is this statement true or false?

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

Press true if you believe the statement is correct, or false otherwise.

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++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4void functionB(int n) {
5  if (n > 0) {
6    functionA(n - 1);
7  }
8}
9
10void functionA(int n) {
11  if (n > 0) {
12    functionB(n - 1);
13  }
14}
15
16int main() {
17  functionA(5);
18  return 0;
19}

xxxxxxxxxx
 
#include <iostream>
using namespace std;
​
int main() {
  // Code snippet goes here
  return 0;
}

Are you sure you're getting this? Fill in the missing part by typing it in.

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.

Write the missing line below.

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++:

TEXT/X-C++SRC

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

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.

xxxxxxxxxx
 
#include <iostream>
using namespace std;
​
int main() {
  // C++ code for introduction to queues
  cout << "Introduction to Queues in C++" << endl;
  return 0;
}

Let's test your knowledge. Click the correct answer from the options.

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

Click the option that best answers the question.

Last In First Out (LIFO)
First In First Out (FIFO)
Random access
Unordered

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++:

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Node class
5class Node {
6public:
7    int data;
8    Node* next;
9};
10
11// Queue class
12class Queue {
13private:
14    Node* front;
15    Node* rear;
16
17public:
18    // Constructor
19    Queue() {
20        front = nullptr;
21        rear = nullptr;
22    }
23
24    // Check if queue is empty
25    bool isEmpty() {
26        return (front == nullptr);
27    }
28
29    // Enqueue an element
30    void enqueue(int item) {
31        Node* newNode = new Node;
32        newNode->data = item;
33        newNode->next = nullptr;
34
35        if (isEmpty()) {
36            front = rear = newNode;
37        }
38        else {
39            rear->next = newNode;
40            rear = newNode;
41        }
42
43        cout << "Enqueued: " << item << endl;
44    }
45
46    // Dequeue an element
47    void dequeue() {
48        if (isEmpty()) {
49            cout << "Queue is empty" << endl;
50        }
51        else {
52            Node* temp = front;
53            cout << "Dequeued: " << front->data << endl;
54            front = front->next;
55
56            delete temp;
57        }
58    }
59
60    // Get the front element
61    int getFront() {
62        if (isEmpty()) {
63            return -1;
64        }
65        else {
66            return front->data;
67        }
68    }
69};
70
71int main() {
72    // Create a queue object
73    Queue q;
74
75    // Enqueue elements
76    q.enqueue(10);
77    q.enqueue(20);
78    q.enqueue(30);
79
80    // Dequeue elements
81    q.dequeue();
82    q.dequeue();
83
84    // Get the front element
85    int front = q.getFront();
86    cout << "Front element: " << front << endl;
87
88    return 0;
89}

xxxxxxxxxx
}
 
#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

Let's test your knowledge. Click the correct answer from the options.

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

Click the option that best answers the question.

Enqueue items at the front of the queue
Use a linked list to store the elements
Use two pointers to keep track of the front and rear of the queue
Check if the queue is empty before dequeueing an item

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.

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.

TEXT/X-C++SRC

1void enqueue(int item) {
2    Node* newNode = new Node;
3    newNode->data = item;
4    newNode->next = nullptr;
5
6    if (isEmpty()) {
7        front = rear = newNode;
8    }
9    else {
10        rear->next = newNode;
11        rear = newNode;
12    }
13}

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.

TEXT/X-C++SRC

1void dequeue() {
2    if (isEmpty()) {
3        cout << "Queue is empty" << endl;
4    }
5    else {
6        Node* temp = front;
7        cout << "Dequeued: " << front->data << endl;
8        front = front->next;
9
10        delete temp;
11    }
12}

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.

TEXT/X-C++SRC

1int getFront() {
2    if (isEmpty()) {
3        return -1;
4    }
5    else {
6        return front->data;
7    }
8}

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

TEXT/X-C++SRC

1#include <iostream>
2using namespace std;
3
4// Node class
5class Node {
6public:
7    int data;
8    Node* next;
9};
10
11// Queue class
12class Queue {
13private:
14    Node* front;
15    Node* rear;
16
17public:
18    // Constructor
19    Queue() {
20        front = nullptr;
21        rear = nullptr;
22    }
23
24    // Check if queue is empty
25    bool isEmpty() {
26        return (front == nullptr);
27    }
28
29    // Enqueue an element
30    void enqueue(int item) {
31        Node* newNode = new Node;
32        newNode->data = item;
33        newNode->next = nullptr;
34
35        if (isEmpty()) {
36            front = rear = newNode;
37        }
38        else {
39            rear->next = newNode;
40            rear = newNode;
41        }
42    }
43
44    // Dequeue an element
45    void dequeue() {
46        if (isEmpty()) {
47            cout << "Queue is empty" << endl;
48        }
49        else {
50            Node* temp = front;
51            cout << "Dequeued: " << front->data << endl;
52            front = front->next;
53
54            delete temp;
55        }
56    }
57
58    // Get the front element
59    int getFront() {
60        if (isEmpty()) {
61            return -1;
62        }
63        else {
64            return front->data;
65        }
66    }
67};
68
69int main() {
70    // Create a queue object
71    Queue q;
72
73    // Enqueue elements
74    q.enqueue(10);
75    q.enqueue(20);
76    q.enqueue(30);
77
78    // Dequeue elements
79    q.dequeue();
80    q.dequeue();
81
82    // Get the front element
83    int front = q.getFront();
84    cout << "Front element: " << front << endl;
85
86    return 0;
87}

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.

xxxxxxxxxx
}
 
#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;

Let's test your knowledge. Click the correct answer from the options.

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

Click the option that best answers the question.

Enqueue
Dequeue
Get Front
IsEmpty

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!

xxxxxxxxxx
 
#include <iostream>
using namespace std;
​
int main() {
  // Replace with relevant content
}

Try this exercise. Is this statement true or false?

Queues are commonly used in task scheduling systems.

Press true if you believe the statement is correct, or false otherwise.

Generating complete for this lesson!

Introduction to Stacks

Are you sure you're getting this? Is this statement true or false?

Implementing a Stack

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Build your intuition. Is this statement true or false?

Are you sure you're getting this? Fill in the missing part by typing it in.

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Try this exercise. Is this statement true or false?

Programming Categories

Popular Lessons