Welcome to the world of data structures and algorithms with C++! This article will introduce you to the concepts of stacks and queues, and how you can use them to solve complex problems. We’ll explore how to implement stacks and queues using arrays and classes, how to use the collections framework for stacks and queues, and the various applications of stacks and queues. By the end of this article, you should have a good understanding of how to use stacks and queues in C++.
What are Stacks and Queues?
Stacks and queues are two of the most basic data structures in computer science. They are linear data structures that store data in a certain order. A stack is a “last in, first out” (LIFO) data structure, meaning that the last item to be added to the stack will be the first item to be removed. A queue is a “first in, first out” (FIFO) data structure, meaning that the first item to be added to the queue will be the first item to be removed.
Implementing Stacks and Queues using Arrays
You can implement a stack or queue using an array. When implementing a stack using an array, you must keep track of the size of the stack. You can do this by using a variable to keep track of the number of elements in the stack. In addition, you must also keep track of the top element in the stack. To do this, you can use a variable to keep track of the index of the top element.
Here is an example of a simple stack implementation using an array in C++:
#include <iostream> using namespace std; const int MAX_SIZE = 10; class Stack { private: int arr[MAX_SIZE]; int top; public: Stack() { top = -1; } void push(int data) { if (top == MAX_SIZE - 1) { cout << "Stack overflow" << endl; return; } arr[++top] = data; } int pop() { if (top == -1) { cout << "Stack underflow" << endl; return -1; } return arr[top--]; } }; int main() { Stack s; s.push(1); s.push(2); s.push(3); cout << s.pop() << endl; cout << s.pop() << endl; cout << s.pop() << endl; return 0; }The code above creates a stack with a maximum size of 10. We create a Stack class with a private array arr, and a variable top to keep track of the top element of the stack. We also create two methods: push() and pop() to add and remove elements from the stack.
Similarly, you can implement a queue using an array. You must keep track of the size of the queue, as well as the front and rear elements. You can do this by keeping track of the indices of the front and rear elements. Here is an example of a simple queue implementation using an array in C++:
#include <iostream> using namespace std; const int MAX_SIZE = 10; class Queue { private: int arr[MAX_SIZE]; int front; int rear; public: Queue() { front = 0; rear = MAX_SIZE - 1; } void enqueue(int data) { if (front == rear + 1) { cout << "Queue overflow" << endl; return; } rear = (rear + 1) % MAX_SIZE; arr[rear] = data; } int dequeue() { if (front == rear + 1) { cout << "Queue underflow" << endl; return -1; } int data = arr[front]; front = (front + 1) % MAX_SIZE; return data; } }; int main() { Queue q; q.enqueue(1); q.enqueue(2); q.enqueue(3); cout << q.dequeue() << endl; cout << q.dequeue() << endl; cout << q.dequeue() << endl; return 0; }The code above creates a queue with a maximum size of 10. We create a Queue class with a private array arr, and variables front and rear to keep track of the front and rear elements of the queue. We also create two methods: enqueue() and dequeue() to add and remove elements from the queue.
Implementing Stacks and Queues using Classes
You can also implement a stack or queue using a class. To do this, you must create a class that contains two methods: push() and pop() for stacks, or enqueue() and dequeue() for queues.
Here is an example of a simple stack implementation using a class in C++:
#include <iostream> #include <list> using namespace std; class Stack { private: list<int> data; public: void push(int n) { data.push_back(n); } int pop() { if (data.empty()) { cout << "Stack underflow" << endl; return -1; } int n = data.back(); data.pop_back(); return n; } }; int main() { Stack s; s.push(1); s.push(2); s.push(3); cout << s.pop() << endl; cout << s.pop() << endl; cout << s.pop() << endl; return 0; }The code above creates a stack using a class. We create a Stack class with a private list data. We also create two methods: push() and pop() to add and remove elements from the stack.
Similarly, you can implement a queue using a class. Here is an example of a simple queue implementation using a class in C++:
#include <iostream> #include <list> using namespace std; class Queue { private: list<int> data; public: void enqueue(int n) { data.push_back(n); } int dequeue() { if (data.empty()) { cout << "Queue underflow" << endl; return -1; } int n = data.front(); data.pop_front(); return n; } }; int main() { Queue q; q.enqueue(1); q.enqueue(2); q.enqueue(3); cout << q.dequeue() << endl; cout << q.dequeue() << endl; cout << q.dequeue() << endl; return 0; }The code above creates a queue using a class. We create a Queue class with a private list data. We also create two methods: enqueue() and dequeue() to add and remove elements from the queue.
Using the Collections Framework for Stacks and Queues
In C++, you can also use the collections framework to implement stacks and queues. The collections framework provides several classes for implementing stacks and queues, such as stack, queue, and priority_queue.
Here is an example of a simple stack implementation using the collections framework in C++:
#include <iostream> #include <stack> using namespace std; int main() { stack<int> s; s.push(1); s.push(2); s.push(3); cout << s.top() << endl; s.pop(); cout << s.top() << endl; s.pop(); cout << s.top() << endl; s.pop(); return 0; }The code above creates a stack using the collections framework. We create a stack of integers, and then use the push(), pop(), and top() methods to add, remove, and access the top element of the stack.
Similarly, you can use the collections framework to implement a queue. Here is an example of a simple queue implementation using the collections framework in C++:
#include <iostream> #include <queue> using namespace std; int main() { queue<int> q; q.push(1); q.push(2); q.push(3); cout << q.front() << endl; q.pop(); cout << q.front() << endl; q.pop(); cout << q.front() << endl; q.pop(); return 0; }The code above creates a queue using the collections framework. We create a queue of integers, and then use the push(), pop(), and front() methods to add, remove, and access the front element of the queue.
Applications of Stacks and Queues
Stacks and queues are widely used in many different applications. Stacks are commonly used for keeping track of function calls in a program, for storing expression evaluation and syntax parsing, and for implementing backtracking algorithms. Queues are commonly used for scheduling tasks, for implementing breadth-first search algorithms, and for simulating communication channels.
Conclusion
In this article, we’ve explored how to use stacks and queues in C++. We’ve looked at how to implement stacks and queues using arrays and classes, and how to use the collections framework for stacks and queues. We’ve also discussed the various applications of stacks and queues. By the end of this article, you should have a good understanding of how to use stacks and queues in C++.
Exercises
Given the following stack: [1, 2, 3, 4], write a function that removes the top element from the stack.
#include <iostream> #include <vector> using namespace std; void pop(vector<int>& s) { if (s.empty()) { cout << "Stack underflow" << endl; return; } s.pop_back(); } int main() { vector<int> s = {1, 2, 3, 4}; pop(s); return 0; }Given the following queue: [1, 2, 3, 4], write a function that removes the front element from the queue.
#include <iostream> #include <list> using namespace std; void dequeue(list<int>& q) { if (q.empty()) { cout << "Queue underflow" << endl; return; } q.pop_front(); } int main() { list<int> q = {1, 2, 3, 4}; dequeue(q); return 0; }Given the following stack: [1, 2, 3, 4], write a function that adds the element 5 to the top of the stack.
#include <iostream> #include <vector> using namespace std; void push(vector<int>& s, int data) { s.push_back(data); } int main() { vector<int> s = {1, 2, 3, 4}; push(s, 5); return 0; }Given the following queue: [1, 2, 3, 4], write a function that adds the element 5 to the back of the queue.
#include <iostream> #include <list> using namespace std; void enqueue(list<int>& q, int data) { q.push_back(data); } int main() { list<int> q = {1, 2, 3, 4}; enqueue(q, 5); return 0; }Given an array of integers, write a function that uses a stack to reverse the order of the elements in the array.
#include <iostream> #include <vector> #include <stack> using namespace std; void reverse(int arr[], int n) { stack<int> s; for (int i = 0; i < n; i++) { s.push(arr[i]); } for (int i = 0; i < n; i++) { arr[i] = s.top(); s.pop(); } } int main() { int arr[] = {1, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); reverse(arr, n); return 0; }