.png)
Stack
Stack is a linear data structure in which insertion & deletion is allowed at one end called top
The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Stack Primary Operations:
- push(data) - inserts data onto the Stack
- pop() - deletes the last inserted element from the Stack
Stack Secondary Operations:
- top() - returns the last inserted element without removing it
- size() - returns the size or the number of elements in the stack
- isEmpty() - returns TRUE if Stack is empty. Else returns FALSE
- isFull() - returns TRUE is Stack is full. Else returns FALSE
⭐Using the Standard Template Library (STL) Stack:
CODE:
#include <iostream>#include <stack>int main() {std::stack<int> s;s.push(1);s.push(2);s.push(3);std::cout << "Top element: " << s.top() << std::endl;s.pop();std::cout << "Top element after pop: " << s.top() << std::endl;if (!s.empty()) {std::cout << "Stack is not empty." << std::endl;}std::cout << "Stack size: " << s.size() << std::endl;return 0;}
OUTPUT:
Top element: 3
Top element after pop: 2
Stack is not empty.
Stack size: 2
⭐Array Implementation of Stack:
CODE:
#include <iostream>using namespace std;class Stack {int *arr;int top;int maxSize;public://initialize the stackStack(int size) {maxSize = size;arr = new int[maxSize];top = -1;}//check empty or fullbool isEmpty() {return top == -1;}bool isFull() {return top == maxSize - 1;}//Push (add to end)void push(int value) {if (isFull()) {std::cout << "Stack Overflow" << endl;return;}arr[++top] = value;}//Pop (remove from end)int pop() {if (isEmpty()) {std::cout << "Stack Underflow" << endl;return -1;}return arr[top--];}//Peek (check end) operationsint peek() {if (isEmpty()) {std::cout << "Stack is empty" << endl;return -1;}return arr[top];}};int main() {int size;std::cin >> size;Stack stack(size);stack.push(10);stack.push(20);stack.push(30);stack.push(40);stack.push(50);stack.push(60);cout << "Top element is: " << stack.peek() << endl;cout << "Popped element: " << stack.pop() << endl;cout << "Top element is: " << stack.peek() << endl;return 0;}
OUTPUT:
Stack Overflow
Top element is: 50
Popped element: 50
Top element is: 40
⭐Linked List Implementation of Stack:
CODE:
#include <iostream>using namespace std;class Node {public:int data;Node *next;Node(int value) : data(value), next(nullptr) {}};class Stack {private:Node *top;public:Stack() : top(nullptr) {}bool isEmpty() {return top == nullptr;}//Push Operation:void push(int value) {Node *newNode = new Node(value);newNode->next = top;top = newNode;}//Pop Operation:int pop() {if (isEmpty()) {cout << "Stack Underflow" << endl;return -1;}int poppedValue = top->data;Node *temp = top;top = top->next;delete temp;return poppedValue;}//Peek Operation:int peek() {if (isEmpty()) {std::cout << "Stack is empty" << endl;return -1;}return top->data;}//Display Operation:void display(){if(top == nullptr){cout << "Stack is empty!" << endl;return;}Node *current = top;cout << "Stack element: ";while(current != nullptr){cout << current->data << " ";current = current->next;}cout << endl;}};int main() {Stack stack;stack.push(10);stack.push(20);stack.push(30);stack.push(40);stack.push(50);cout << "Top element is: " << stack.peek() << endl;cout << "Popped element: " << stack.pop() << endl;cout << "Top element is: " << stack.peek() << endl;stack.display();return 0;}
OUTPUT:
Top element is: 50
Popped element: 50
Top element is: 40
Stack element: 40 30 20 10
⭐Stack - Polish Notation:
1) Types of Notations
- Infix Notation: The operator is placed between operands (e.g.,
A + B). - Prefix Notation (Polish Notation): The operator is placed before its operands (e.g.,
+ A B). - Postfix Notation (Reverse Polish Notation): The operator is placed after its operands (e.g.,
A B +).
2) Polish Notation
This is another term for prefix notation, where operators precede their operands. For example, the infix expression
A + B is represented as + A B in prefix.3) Reverse Polish Notation (RPN)
This is the same as postfix notation. It does not require parentheses to dictate order of operations, making it efficient for stack-based evaluation.
4) Evaluation of Postfix Expression
Example: Evaluate 5 3 4 * + 2 -.
Step-by-Step Evaluation:
- Read the expression from left to right.
- Push operands onto the stack.
- When an operator is encountered, pop the necessary number of operands from the stack, apply the operator, and push the result back.
Evaluation Steps:
5→ Stack:[5]3→ Stack:[5, 3]4→ Stack:[5, 3, 4]*→ Pop3and4, calculate3 * 4 = 12, Stack:[5, 12]+→ Pop5and12, calculate5 + 12 = 17, Stack:[17]2→ Stack:[17, 2]-→ Pop17and2, calculate17 - 2 = 15, Stack:[15]
Final Result: 15
5) Conversion of an Infix Expression to Postfix Expression
Example: Convert A + B * C.
Step-by-Step Conversion:
- Use a stack to hold operators and output the operands.
- Output the operands directly to the result.
- Push the operators onto the stack, considering their precedence.
Conversion Steps:
- Read
A→ Output:A - Read
+→ Push onto stack:Stack: [+] - Read
B→ Output:AB - Read
*→ Push onto stack (higher precedence):Stack: [*, +] - Read
C→ Output:ABC - Pop all operators from the stack → Output:
ABC*+
6) Conversion of an Infix Expression to Prefix Expression
Example: Convert A + B * C.
Step-by-Step Conversion:
- Reverse the infix expression.
- Swap
(with)and vice versa. - Convert to postfix using the previously defined method.
- Reverse the resulting postfix expression to get the prefix.
Conversion Steps:
- Reverse:
C * B + A - Swap:
C * B ) A ( - Convert to postfix:
CB*A+ - Reverse:
+A*BC
🚨Thanks for visiting classpdfindia✨
Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.
💗 Bookmark our site to stay connected and never miss an update!
💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍
.png)