1. Introduction
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means the last element added to the stack will be the first element to be removed. It provides operations to push (add) items, pop (remove) items, and check the top item without removal, often named peek or top.
Common real-world examples of a stack include a pile of books or plates, where you add or remove items from the top of the pile.
2. Implementation Steps
1. Define the maximum size of the stack.
2. Initialize the stack with a structure or class containing an array to store elements and a variable to keep track of the topmost element's index.
3. Implement the push operation to add elements to the stack.
4. Implement the pop operation to remove the topmost element from the stack.
5. Implement the top or peek operation to view the topmost element without removing it.
6. Implement utility functions like isEmpty and isFull to check the status of the stack.
3. Implementation in C++ Programming
#include <iostream>
using namespace std;
#define MAX 1000 // Define the maximum size of the stack
class Stack {
private:
int arr[MAX]; // Stack array to store elements
int top; // Index of the topmost element
public:
Stack() { top = -1; } // Constructor to initialize stack
bool push(int x) {
if (top >= (MAX - 1)) {
cout << "Stack Overflow";
return false;
} else {
arr[++top] = x;
return true;
}
}
int pop() {
if (top < 0) {
cout << "Stack Underflow";
return 0;
} else {
return arr[top--];
}
}
int peek() {
if (top < 0) {
cout << "Stack is Empty";
return 0;
} else {
return arr[top];
}
}
bool isEmpty() {
return (top < 0);
}
};
// Client code to test the stack implementation
int main() {
Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.pop() << " Popped from stack\n";
cout << "Top element is " << s.peek() << endl;
return 0;
}
Output:
30 Popped from stack Top element is 20
Explanation:
1. The Stack class contains an array arr to store stack elements and a variable top to keep track of the topmost element.
2. The push function checks if there is space in the stack. If there's room, it increments the top index and adds the element. Otherwise, it indicates a "Stack Overflow" error.
3. The pop function checks if the stack is empty. If not, it returns the topmost element and decrements the top index. Otherwise, it indicates a "Stack Underflow" error.
4. The peek function returns the topmost element without modifying the top index.
5. The isEmpty function checks if the stack is empty by examining the value of the top.
6. In the client code, we push a few elements onto the stack and then pop an element. The program also demonstrates checking the topmost element using the peek function.
Comments
Post a Comment