Published: 20 Nov 2024
Reading Time: 4 min read
Data structures Stack and Queue are essential building blocks for organizing and managing data efficiently. Two of the most fundamental linear data structures are the stack and the queue. Both have different purposes and are implemented based on distinct principles that determine how data is added, accessed, and removed. Understanding the differences between stacks and queues is key. This article explores stack and queue with their operations, applications, and programming examples.
In computer science, a stack is a linear data structure based on the Last In, First Out (LIFO) principle. It is an abstract data type that consists of a set of similar elements, such as objects, integers, or characters, which are added and removed from the top of the stack.
In a stack, the element that is added last is the first one to be removed. This means that the order of elements is reversed when they are retrieved. For example, if you push elements A, B, and C onto a stack, the order of retrieval would be C, B, and A.
The basic operations associated with a stack are:
In data structures, queues follow the principle of First-In-First-Out (FIFO). The queue is open on both ends, so elements may be added (enqueued) and removed (dequeued) in a specific sequence.
The basic operations associated with a queue are:
Here is the comparison of stack and queue:
| Aspect | Stack | Queue |
|---|---|---|
| Principle | Last In, First Out (LIFO) | First In, First Out (FIFO) |
| Primary Operations | Push, Pop, Peek | Enqueue, Dequeue, Front, Rear |
| Operation Ends | Both insertion and removal happen at the same end (top) | Insertion happens at the rear, and removal happens from the front |
| Main Use Cases | Function call management, expression evaluation, and undo mechanisms | Task scheduling, print spooling, and breadth-first search |
| Examples | Browser history and expression reversal | Customer service queues and CPU task scheduling |
| Real-World Analogy | Plates (add/remove from the top) | Queue at a ticket counter (first in, first served) |
| Time Complexity | O(1) for Push, Pop, and Peek | O(1) for Enqueue, Dequeue, Front, Rear |
| Memory Structure | Can be implemented using arrays or linked lists | Can be implemented using arrays, linked lists, or circular buffers |
Here are the stack and queue programs in data structures:
Here is a stack program in C++ using the class:
#include <iostream>
#include <vector>
class Stack {
private:
std::vector<int> stack; // Vector to store stack elements
public:
// Push an element onto the stack
void push(int item) {
stack.push_back(item);
}
// Pop an element from the stack
int pop() {
if (isEmpty()) {
std::cout << "Stack is empty!" << std::endl;
return -1; // Or throw an exception
}
int item = stack.back();
stack.pop_back();
return item;
}
// Peek at the top element of the stack
int peek() {
if (isEmpty()) {
std::cout << "Stack is empty!" << std::endl;
return -1; // Or throw an exception
}
return stack.back();
}
// Check if the stack is empty
bool isEmpty() {
return stack.empty();
}
// Get the size of the stack
int size() {
return stack.size();
}
// Print the stack
void print() {
if (isEmpty()) {
std::cout << "Stack is empty!" << std::endl;
return;
}
for (int i = stack.size() - 1; i >= 0; i--) {
std::cout << stack[i] << " ";
}
std::cout << std::endl;
}
};
// Example usage:
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // Output: 30 20 10
std::cout << "Pop: " << stack.pop() << std::endl; // 30
std::cout << "Peek: " << stack.peek() << std::endl; // 20
std::cout << "Size: " << stack.size() << std::endl; // 2
stack.print(); // Output: 20 10
return 0;
}
Output:
30 20 10
Pop: 30
Peek: 20
Size: 2
20 10
Here is a queue program in C++ using the class:
#include <iostream>
#include <deque>
class Queue {
private:
std::deque<int> queue; // Deque to store queue elements
public:
// Enqueue an element
void enqueue(int item) {
queue.push_back(item);
}
// Dequeue an element
int dequeue() {
if (isEmpty()) {
std::cout << "Queue is empty!" << std::endl;
return -1; // Or throw an exception
}
int item = queue.front();
queue.pop_front();
return item;
}
// Peek at the front element of the queue
int peek() {
if (isEmpty()) {
std::cout << "Queue is empty!" << std::endl;
return -1; // Or throw an exception
}
return queue.front();
}
// Check if the queue is empty
bool isEmpty() {
return queue.empty();
}
// Get the size of the queue
int size() {
return queue.size();
}
// Print the queue
void print() {
if (isEmpty()) {
std::cout << "Queue is empty!" << std::endl;
return;
}
for (int i = 0; i < queue.size(); i++) {
std::cout << queue[i] << " ";
}
std::cout << std::endl;
}
};
// Example usage:
int main() {
Queue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.print(); // Output: 10 20 30
std::cout << "Dequeue: " << queue.dequeue() << std::endl; // 10
std::cout << "Peek: " << queue.peek() << std::endl; // 20
std::cout << "Size: " << queue.size() << std::endl; // 2
queue.print(); // Output: 20 30
return 0;
}
Output:
10 20 30
Dequeue: 10
Peek: 20
Size: 2
20 30
The following are some similarities between stacks and queues:
Here are some of the applications of stack and queue:
In conclusion, stacks and queues are fundamental data structures in computer science, each designed for specific use cases. The stack is useful for problems that require reversal or backtracking, while the queue is ideal for tasks requiring sequential processing, like scheduling or resource management. Understanding the unique characteristics of these structures helps in selecting the appropriate one for different algorithms and applications.
A stack follows the LIFO (Last In, First Out) principle, while a queue follows the FIFO (First In, First Out) principle.
Yes, stacks and queues can be implemented by using arrays or linked lists. In some cases, a queue may also use a circular buffer for more efficient memory usage.
Stacks are useful in situations like managing function calls in programming, undo operations in applications, and evaluating expressions.
Queues are typically used in scenarios like task scheduling, managing print jobs, or in breadth-first search (BFS) in graph traversal.
Both stack and queue operations such as Push/Pop for stack and Enqueue/Dequeue for queue are performed in constant time, i.e., O(1).