Stack
A stack is an abstract data type that represents a collection of elements with two primary operations: push, which adds an element to the top of the stack, and pop, which removes the topmost element.
Imagine you are in a cafeteria or a buffet where plates are stacked on top of each other. When you want to add a plate to the stack, you place it on top of the existing plates. This action is similar to the "push" operation in a stack data structure, where you add an element to the top of the stack.
Now, let's say you need to take a plate from the stack. In order to do so, you can only take the topmost plate from the stack. This reflects the "pop" operation in a stack, where you remove the topmost element from the stack.
The stack follows the Last-In-First-Out (LIFO) principle
The LIFO property is demonstrated by the fact that the plate you placed last (the most recently added) is the first one you can remove.
Operations in Stack:
Push(): This operation adds an element to the top of the stack. The new element becomes the top, and the existing elements are pushed down.
Pop(): The pop operation removes the topmost element from the stack. It returns the removed element and updates the stack's top to the next element below it.
Peek() or Top(): This operation allows you to examine the topmost element without removing it from the stack. It returns the value of the top element but does not modify the stack's structure.
IsEmpty(): This operation checks if the stack is empty, meaning it contains no elements. It returns a Boolean value (true or false) based on the stack's state.
Stack Implementation in C++:
Here, step by step process of implementation of stack in C++ has been shown:
1.Include the necessary header files:
#include <iostream> // For input/output operations
#include <stack> // For using the stack container
2.Declare the stack:
std::stack<int> myStack;
std::stack<std::string> stringStack;
3.Push elements onto the stack, use the push function:
myStack.push(5); // Pushing the integer 5 onto the stack
stringStack.push("Hello"); // Pushing the string "Hello" onto the stack
4. Check if the stack is empty, use the empty function:
if (myStack.empty()) {
std::cout << "Stack is empty!" << std::endl;
}
5.access the top element of the stack without removing it, use the top function:
int topElement = myStack.top(); // Accessing the top element of the stack
std::cout << "Top element: " << topElement << std::endl;
Full Implementation:
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
myStack.push(5);
myStack.push(10);
myStack.push(15);
while (!myStack.empty()) {
int topElement = myStack.top();
std::cout << "Top element: " << topElement << std::endl;
myStack.pop();
}
return 0;
}Output:
Top element: 15
Top element: 10
Top element: 5Demonstrating all functions of Stack:
1.Popping Elements from the Stack:
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);
while (!myStack.empty()) {
int topElement = myStack.top();
std::cout << "Popped element: " << topElement << std::endl;
myStack.pop();
}
return 0;
}
Output:
Popped element: 30
Popped element: 20
Popped element: 10In this code the top element of the stack is retrieved using the top() function and assigns it to the variable topElement. Then, it prints the value of topElement as the "Popped element".
After printing the top element, it removes the element from the top of the stack using the pop() function, which effectively "pops" or removes the topmost element from the stack.
2.Accessing the Top Element:
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);
if (!myStack.empty()) {
int topElement = myStack.top();
std::cout << "Top element: " << topElement << std::endl;
}
return 0;
}
Output:
Top element: 30
The 'empty()' function is used to determine if the stack is not empty. If the stack contains any elements, it uses the top() function to extract the top element and assigns it to the variable topElement.
If the stack is not empty in this instance, only the top piece is printed. As a result, the output will read "Top element: 30" because 30 is the stack's top element after 10, 20, and 30 have been added to it.
3.Checking if the Stack is Empty:
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
// Push elements onto the stack
myStack.push(10);
myStack.push(20);
myStack.push(30);
while (!myStack.empty()) {
// Pop an element from the stack
int poppedElement = myStack.top();
myStack.pop();
std::cout <<"Popped element: " << poppedElement << std::endl;
// Check if the stack is not empty after popping
if (!myStack.empty()) {
std::cout <<"Stack is not empty.\n ";
} else {
std::cout <<"Stack is now empty. ";
}
// Print the popped element
}
return 0;
}Output:
Popped element: 30
Stack is not empty.
Popped element: 20
Stack is not empty.
Popped element: 10
Stack is now empty.In this code the it is whether the stack is empty or not after popping each element. When all the items are popped, the code prints the statement that the stack is empty.
4. Find size of the stack:
#include <iostream>
#include <stack>
int main() {
std::stack<int> myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);
std::cout << "Stack size: " << myStack.size() << std::endl;
return 0;
}
Output:
Stack size: 3
Implementation of Stack using linked list:
#include <iostream>
// Node structure for a linked list
struct Node {
int data;
Node* next;
};
// Stack class using linked list
class Stack {
private:
Node* top; // Pointer to the top of the stack
public:
// Constructor
Stack() : top(nullptr) {}
// Destructor to free memory
~Stack() {
// Pop all elements until the stack becomes empty
while (!isEmpty()) {
pop();
}
}
// Check if the stack is empty
bool isEmpty() {
return top == nullptr;
}
// Push an element onto the stack
void push(int value) {
// Create a new node
Node* newNode = new Node;
newNode->data = value;
newNode->next = top;
// Set the new node as the new top
top = newNode;
}
// Pop the top element from the stack
void pop() {
if (isEmpty()) {
std::cout << "Stack is empty. Cannot perform pop operation." << std::endl;
return;
}
// Store the current top node
Node* temp = top;
// Move the top pointer to the next node
top = top->next;
// Free memory of the previous top node
delete temp;
}
// Get the value of the top element without removing it
int peek() {
if (isEmpty()) {
std::cout << "Stack is empty. Cannot perform peek operation." << std::endl;
return -1;
}
return top->data;
}
// Print the elements in the stack
void printStack() {
if (isEmpty()) {
std::cout << "Stack is empty." << std::endl;
return;
}
Node* current = top;
std::cout << "Stack elements: ";
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
Stack myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);
myStack.printStack();
std::cout << "Top element: " << myStack.peek() << std::endl;
myStack.pop();
myStack.pop();
//after popping elements
std::cout << "After poppping elements " <<std::endl;
myStack.printStack();
return 0;
}
Output:
Stack elements: 30 20 10
Top element: 30
After poppping elements
Stack elements: 10 Types of Stack:
There are several types of stacks that can be categorized based on their specific characteristics and usage.
1.Array-based Stack: An array data structure is used to implement this kind of stack. The array items are subjected to stack operations like push and pop. Typically, the stack's size is fixed, though it can expand dynamically by resizing the array.
2.Linked List-based Stack: A linked list data structure is used to implement this kind of stack. The head or front of the linked list, which represents the top of the stack, is represented by each node in the linked list as an element in the stack. The linked list nodes are manipulated to carry out the stack operations.
3.Dynamic Stack: Dynamically allocated memory is used to implement dynamic stacks. Throughout program execution, they can expand or contract in size as necessary. It is possible to implement dynamic stacks using linked lists or arrays.
4.Static Stack: At compilation time, a static stack's fixed size is determined. No additional elements can be added to the stack after the maximum size has been reached. Arrays are frequently used to implement static stacks.
5.Priority Stack: Each element in a priority stack is given a priority value. The priority controls which elements are accessed or removed from the stack in which order. Priority is given to elements with a higher priority than those with a lower priority.
6.Circular Stack:The top and bottom of a circular stack are connected, and the stack has a circular shape. New elements continuously replace the older elements once the stack is complete. Applications requiring a fixed-size buffer, such as those in hardware or real-time systems, can benefit from circular stacks.
Applications of Stack
Stacks are used in a variety of software development and computer science contexts. Listed below are a few typical uses for stacks:
1. Function Call Stack: In programming languages, stacks are used to organize function calls and monitor the progress of execution. Every function call is added to the stack, and when a function is finished, it is removed from the stack so that the calling function can continue to run.
2. Expression Evaluation: Arithmetic expressions, such as infix, postfix, or prefix notation, can be evaluated using stacks. By maintaining the proper order of operations, they assist in transforming expressions between various notations and calculating the result.
3. Browser History: Stacks can be used to keep track of websites that have been visited in web browsers. The current page is placed into the stack when a user navigates to another page. The top page in the stack can then be popped to take the user back.
4. Depth-First Search (DFS): Stacks are employed in graph algorithms like DFS to maintain track of visited nodes and search nearby nodes before going back. To allow for traversal of the graph in depth first, the stack records the nodes to be visited.
5. Parentheses in Balance: Stacks are frequently used to verify that the parentheses in an expression are balanced. When a closing parenthesis is met, it is compared with the top element of the stack after each opening parenthesis has been added to the stack. The starting parenthesis is popped if they form a pair; else, the expression is unbalanced.
6. Backtracking Algorithms: Backtracking algorithms, such as those used to solve the N-Queens problem or mazes, can make use of stacks. The stack saves the path or decisions made thus far, enabling the algorithm to go back and consider different options as necessary.
These are just a few instances of how stacks are applied in many contexts. Stacks offer a quick and effective approach to trace the sequence of actions and handle data in a variety of circumstances.