LEARNING OUTCOME 5
Stack: A Last-In-First-Out (LIFO) Data Structure
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. A stack is like a pile of books.
- Adding a book: You place it on the top of the pile (push).
- Taking a book: You always take the topmost book (pop).
So, the last book you added is the first one you take. This is the Last-In-First-Out (LIFO) principle.
Key Operations on a Stack:
- Push: Adds an element to the top of the stack.
- Pop: Removes the top element from the stack.
- Peek: Returns the value of the top element without removing it.
- IsEmpty: Checks if the stack is empty.
Implementation of a Stack
We can implement a stack using an array or a linked list. Here's a comprehensive C++ example demonstrating both methods.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Stack implementation using an array
#include <iostream>
#include <vector> // For dynamic array resizing (optional, but good practice)
class StackArray {
private:
int top;
std::vector<int> arr; // Dynamic array (more flexible)
int maxSize; // Maximum size of the stack
public:
StackArray(int size = 100) : top(-1), maxSize(size) {}
bool isEmpty() const {
return top == -1;
}
bool isFull() const {
return top == maxSize - 1;
}
void push(int value) {
if (isFull()) {
std::cerr << "Stack Overflow!" << std::endl;
return;
}
arr.push_back(value);
top++;
std::cout << value << " pushed onto the stack" << std::endl;
}
int pop() {
if (isEmpty()) {
std::cerr << "Stack Underflow!" << std::endl;
return -1;
}
int poppedValue = arr[top];
arr.pop_back();
top--;
return poppedValue;
}
int peek() const {
if (isEmpty()) {
std::cerr << "Stack is Empty!" << std::endl;
return -1;
}
return arr[top];
}
int size() const {
return top + 1;
}
};
// Stack implementation using a linked list
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class StackLinkedList {
private:
Node* head;
public:
StackLinkedList() : head(nullptr) {}
bool isEmpty() const {
return head == nullptr;
}
void push(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
std::cout << value << " pushed onto the stack" << std::endl;
}
int pop() {
if (isEmpty()) {
std::cerr << "Stack Underflow!" << std::endl;
return -1;
}
int poppedValue = head->data;
Node* temp = head;
head = head->next;
delete temp;
return poppedValue;
}
int peek() const {
if (isEmpty()) {
std::cerr << "Stack is Empty!" << std::endl;
return -1;
}
return head->data;
}
int size() const {
int count = 0;
Node* current = head;
while(current != nullptr) {
count++;
current = current->next;
}
return count;
}
};
int main() {
StackArray stackArr;
stackArr.push(10);
stackArr.push(20);
std::cout << "Top element: " << stackArr.peek() << std::endl;
std::cout << "Popped element: " << stackArr.pop() << std::endl;
std::cout << "Stack size: " << stackArr.size() << std::endl;
StackLinkedList stackList;
stackList.push(100);
stackList.push(200);
std::cout << "Top element: " << stackList.peek() << std::endl;
std::cout << "Popped element: " << stackList.pop() << std::endl;
std::cout << "Stack size: " << stackList.size() << std::endl;
return 0;
}
Applications of Stacks
- Function Call Stack: To manage function calls and return addresses.
- Undo/Redo Functionality: To implement undo and redo features in text editors or other applications.
- Backtracking Algorithms: To keep track of states and make backtracking decisions.
- Expression Evaluation: To evaluate postfix and prefix expressions.
- Browser History: To store the history of visited pages.
- Recursion: To manage recursive function calls.
- Balancing Parentheses: To check if parentheses in an expression are balanced.
- Implementing Queues: Using two stacks, we can simulate a queue's behavior.
Queue: A First-In-First-Out (FIFO) Data Structure
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed.
Distinction between Stack and Queue
| Feature | Stack | Queue |
|---|---|---|
| Access Order | LIFO (Last-In-First-Out) | FIFO (First-In-First-Out) |
| Operations | Push, Pop, Peek | Enqueue, Dequeue, Peek |
| Real-world Analogy | Stack of plates | Queue of people |
| Common Use Cases | Function calls, undo/redo, expression evaluation | Print queues, task scheduling, breadth-first search |
| Time Complexity | O(1) for basic operations | O(1) for basic operations |
Queue Operations
- Enqueue: Adds an element to the rear of the queue.
- Dequeue: Removes an element from the front of the queue.
- Peek: Returns the value of the front element without removing it.
- IsEmpty: Checks if the queue is empty.
- IsFull: Checks if the queue is full (if implemented with a fixed-size array).
Implementation of a Queue
A queue can be implemented using an array (often as a circular queue) or a linked list. The C++ Standard Library provides `std::queue` for ease of use. Below is an example showing both the standard library implementation and a manual implementation of a circular queue.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <queue> // For using the standard queue
#include <vector> // For implementing a fixed-size queue
// Example using std::queue (dynamic size)
void exampleStdQueue() {
std::queue<int> q;
// Enqueue
q.push(10);
q.push(20);
q.push(30);
// Peek
std::cout << "Front element: " << q.front() << std::endl; // Output: 10
// Dequeue
std::cout << "Dequeued element: " << q.front() << std::endl;
q.pop();
// IsEmpty
if (q.empty()) {
std::cout << "Queue is empty" << std::endl;
} else {
std::cout << "Queue is not empty" << std::endl; // Output: Queue is not empty
}
// Size
std::cout << "Queue size: " << q.size() << std::endl; // Output: 2
}
// Example of a fixed-size circular queue using a vector
void exampleFixedSizeQueue() {
const int maxSize = 5;
std::vector<int> q(maxSize);
int front = 0;
int rear = -1;
int size = 0;
// Lambda functions for operations
auto isFull = [&]() { return size == maxSize; };
auto isEmpty = [&]() { return size == 0; };
auto enqueue = [&](int value) {
if (isFull()) {
std::cerr << "Queue is full!" << std::endl;
return;
}
rear = (rear + 1) % maxSize; // Wrap around
q[rear] = value;
size++;
std::cout << value << " enqueued" << std::endl;
};
auto dequeue = [&]() {
if (isEmpty()) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
int value = q[front];
front = (front + 1) % maxSize; // Wrap around
size--;
return value;
};
auto peek = [&]() {
if (isEmpty()) {
std::cerr << "Queue is empty!" << std::endl;
return -1;
}
return q[front];
};
enqueue(10);
enqueue(20);
enqueue(30);
std::cout << "Front element: " << peek() << std::endl;
std::cout << "Dequeued element: " << dequeue() << std::endl;
}
int main() {
std::cout << "--- Example using std::queue ---" << std::endl;
exampleStdQueue();
std::cout << "\n--- Example using fixed-size circular queue ---" << std::endl;
exampleFixedSizeQueue();
return 0;
}
Circular Queue
A circular queue is a linear data structure that operates like a queue but with a circular array implementation. In a circular queue, the last position is connected to the first position, forming a circular structure. This allows for efficient use of space and avoids the need for frequent memory reallocations.
Priority Queue
A priority queue is a queue where each element has a priority associated with it. Elements are dequeued in order of their priority, with the highest-priority element being dequeued first. It's often implemented using a heap data structure.
Applications of Queues
| Application | Description |
|---|---|
| Breadth-First Search (BFS) | To explore graph nodes level by level. |
| Print Queue | To manage print jobs in a printer. |
| Task Scheduling | To schedule tasks in operating systems. |
| Simulation | To simulate real-world systems like traffic lights or bank queues. |
| Keyboard Buffer | To store keystrokes temporarily. |
| Call Center Queues | To manage incoming calls. |
| Producer-Consumer Problem | To coordinate between processes or threads that produce and consume data. |