INTRODUCTION OF STACK IN DATA STRUCTURE
A stack is a
fundamental data structure in computer science that follows the Last In, First
Out (LIFO) principle.
In a stack, the
last element added is the first one to be removed.
A stack, is a
collection of items where new items are added or removed from the same end,
commonly referred to as the "top" of the stack.
Key
characteristics of a stack: (Features of the stack in the data structure.)
The stack is a
fundamental data structure with several key features that make it useful in
various computing applications.
The main features
of a stack:
1. Last In, First Out (LIFO) Principle:
- The primary characteristic of a stack is
that it follows the Last In, First Out (LIFO) order. The last element added to
the stack is the first one to be removed. This behavior is similar to a stack
of plates or a pile of books.
2. Dynamic Size:
- Stacks can dynamically grow or shrink in
size as elements are pushed onto or popped off the stack. The size is not
fixed, and it can change during the program's execution.
3. Operations:
- Push Operation: Adds an element to
the top of the stack.
- Pop Operation: Removes the element
from the top of the stack.
- Peek or Top Operation: Retrieves
the element at the top of the stack without removing it.
- IsEmpty Operation: Checks if the
stack is empty.
- Size Operation: Returns the number
of elements in the stack.
4. Applications in Memory Management:
- Stacks are crucial for managing function
calls and local variables in memory during program execution. The call stack is
a specific implementation of a stack in memory.
5. Expression Evaluation:
- Stacks are used for evaluating
expressions, especially in converting infix expressions to postfix or prefix
form. The stack helps maintain the correct order of operations.
6. Undo Mechanisms:
- Stacks are employed in applications to
implement undo functionalities. Each action is recorded on the stack, allowing
for easy reversal.
7. Backtracking:
- In algorithms and recursion, stacks are
often used to store the state for backtracking. The stack allows the program to
return to previous states or choices.
8. Data Storage in Reverse Order:
- Stacks are used to reverse the order of
data. For example, if you push a sequence of elements onto a stack and then pop
them off, you get the elements in reverse order.
9. Efficient Implementation:
- Stacks can be implemented using arrays or
linked lists. Both implementations provide efficient access to the top of the
stack, making push-and-pop operations fast.
10. Nested Structures:
- Stacks are used to manage nested
structures, such as nested function calls or nested loops. Each level of
nesting corresponds to a level in the stack.
11. Memory Efficiency:
- Stacks have relatively low memory
overhead, making them efficient for certain applications where memory usage is
a concern.
12. Clear and Simple Abstraction:
- The simplicity of the stack's operations
makes it a clear and straightforward abstraction. This simplicity is valuable
in algorithm design and understanding.
----------------------------------------------------
Advantage of the stack
Stacks offer
several advantages in data structure and algorithm design, making them a
valuable and versatile tool in various computing applications. Here are some of
the key advantages of using stacks:
1. Last In, First Out (LIFO) Order:
- The LIFO property of stacks simplifies the
organization of data, making it easier to manage and retrieve the most recently
added elements.
2. Simple and Efficient Operations:
- Stack operations (push, pop, peek) are
simple and can be implemented efficiently using arrays or linked lists. This
simplicity leads to faster execution and better performance.
3. Memory Efficiency:
- Stacks have low memory overhead, as they
only need to store the elements and a reference to the top of the stack. This
efficiency is crucial in memory-constrained environments.
4. Function Call Management:
- Stacks are used to manage function calls
and local variables during program execution. Each function call and its
associated data are pushed onto the call stack, facilitating function
invocation and return.
5. Expression Evaluation:
- Stacks are employed in evaluating
expressions, especially in converting infix expressions to postfix or prefix
form. This simplifies the order of operations and enhances the efficiency of
expression evaluation algorithms.
6. Undo Mechanism:
- Stacks are essential for implementing undo
functionalities in applications. Each action is recorded on the stack, allowing
users to reverse the sequence of operations.
7. Backtracking:
- In algorithms and recursive procedures,
stacks are used to store the state of the program. This enables backtracking,
allowing the program to revisit and explore alternative paths or choices.
8. Nested Structures:
- Stacks are used to manage nested
structures, such as nested function calls, loops, and conditional statements.
Each level of nesting corresponds to a level in the stack.
9. Data Reversal:
- Stacks provide an easy and efficient way
to reverse the order of data. By pushing elements onto a stack and then popping
them off, the elements are retrieved in reverse order.
10. History Tracking:
- Stacks can be employed to maintain a
history of operations or user interactions. This is useful in applications
where users may need to navigate backward through a sequence of actions.
11. Parsing and Syntax Checking:
- Stacks are utilized in parsing algorithms
and syntax checking to ensure the correct nesting of symbols and the validity
of expressions.
12. Memory Management:
- In embedded systems and
resource-constrained environments, stacks are advantageous for managing limited
memory efficiently.
13. Algorithmic Simplicity:
- The use of stacks often simplifies the
design and implementation of algorithms, making them easier to understand and
maintain.
---------------------------------------------
The disadvantage of the stack
some of the
disadvantages of using stacks in data structures:
1. Limited Access:
- Stacks provide access to only the top
element. If there is a need to access elements in the middle or at the bottom
of the stack, a different data structure, such as an array or linked list, may
be more suitable.
2. Fixed Size (in
Array Implementation):
- In array-based implementations of stacks,
the size of the stack is often fixed at the time of creation. This limitation
can lead to overflow or underflow issues if the number of elements exceeds the
predefined size.
3. No Random
Access:
- Stacks do not support random access to
elements. Accessing elements at arbitrary positions requires popping elements
off the stack until the desired element is reached, which can be inefficient.
4. Memory
Constraints:
- Stacks are not suitable for storing large
datasets or when memory efficiency is a critical concern. The dynamic nature of
certain data structures, like linked lists, may be more appropriate in such
cases.
5. Function Call
Overhead:
- While stacks efficiently manage function
calls, excessive recursion or deep function call hierarchies can lead to a
stack overflow, causing the program to crash. Some programming languages have
limitations on the maximum stack depth.
6. Limited Search
Capability:
- Searching for a specific element in a
stack requires popping elements until the desired element is found. This linear
search can be inefficient compared to other data structures that support direct
access or have better search capabilities.
7. Sequential
Processing:
- Stacks are inherently sequential
structures, and parallel processing or concurrent access to elements is not
straightforward. Other data structures, like queues, may be more suitable for
parallel processing.
8. Inefficient for
Some Operations:
- Certain operations, such as finding the
middle element or reversing the order of elements, can be less efficient when
using a stack compared to other data structures designed for these specific
tasks.
9. Difficulty in
Handling Multiple Data Types:
- Stacks are typically designed to store
elements of a single data type. Handling multiple data types in a stack can be
challenging and may require additional type-checking mechanisms.
10. Overhead in
Dynamic Memory Allocation:
- In linked list implementations, dynamic
memory allocation for each node can introduce overhead, leading to increased
memory usage and potential fragmentation.
11. Potential for
Stack Overflow:
- In recursive algorithms or deep function
call chains, there is a risk of a stack overflow if the available stack space
is exhausted. This can lead to program termination.
----------------------------------------
Applications of the stack
Stacks find
applications in various areas of computer science and software development due
to their Last In, First Out (LIFO) nature and efficient operations.
Some common
applications of stacks:
1. Function Call
Management:
- Stacks are used to manage function calls
and local variables in programs. When a function is called, its parameters and
local variables are pushed onto the stack, and when the function completes, the
stack is popped.
2. Expression
Evaluation:
- Stacks are utilized in evaluating
expressions, especially in converting infix expressions to postfix or prefix
form. This simplifies the order of operations and enhances the efficiency of
expression evaluation algorithms.
3. Undo Mechanism:
- Stacks are essential for implementing undo
functionalities in applications. Each action is recorded on the stack, allowing
users to reverse the sequence of operations.
4. Backtracking:
- Stacks are used to store the state of a
program, enabling backtracking in algorithms. This is particularly useful in
search algorithms and puzzles.
5. Memory
Management:
- The call stack is employed for memory
management in programming languages. It keeps track of function calls,
parameters, and local variables, allowing for efficient memory allocation and
deallocation.
6. Syntax Parsing:
- Stacks are used in the parsing phase of
compilers to check the correctness of the syntax in source code. They help
ensure that opening and closing brackets, braces, and parentheses are correctly
matched.
7. Algorithm
Implementations:
- Stacks are used in various algorithms,
such as depth-first search (DFS) in graph traversal, where they help in
tracking and backtracking through the nodes.
8. Parenthesis
Matching:
- Stacks are employed to check the
correctness of parenthesis expressions by keeping track of the opening and
closing brackets.
9. Expression
Conversion:
- Stacks are used to convert expressions
between different forms, such as converting infix expressions to postfix or
prefix notation.
10. History
Tracking:
- Stacks can be used to maintain a history
of operations or user interactions. This is useful in applications where users
may need to navigate backward through a sequence of actions.
11. Task
Scheduling:
- Stacks are used in managing task
scheduling in operating systems. For example, when interrupts occur, the system
can save the current state on the stack before handling the interrupt.
12. Text Editors:
- Stacks are utilized in text editors to
keep track of the cursor position and maintain a history of changes for undo
and redo functionalities.
13. Expression
Matching:
- Stacks are used in matching delimiters
and expressions, such as validating HTML tags or ensuring proper nesting in
programming constructs.
14. Postfix
Evaluation:
- Stacks are employed in evaluating postfix
expressions efficiently. The operands are pushed onto the stack, and operators
are applied when encountered.
15. Browser
History:
- Stacks are used to implement the back and
forward navigation in web browsers, allowing users to revisit previously viewed
pages.
These applications
demonstrate the versatility of stacks in solving various problems across
different domains. The simplicity and efficiency of stack operations make them
a fundamental and widely used data structure.
----------------------------------------
Structure of stack
The structure of a
stack in a computer's memory can be implemented using either an array or a
linked list. Components and characteristics of a stack structure:
Array-Based Implementation:
In an array-based implementation, a fixed-size array is used to represent the stack.
1. Array:
- An array to hold the elements of the
stack.
- The size of the array is fixed during the
stack's creation.
2. Top Pointer:
- A variable (often called "top")
that keeps track of the index of the top element in the stack.
- Initially set to -1 when the stack is
empty.
3. Operations:
- Push Operation:
- Increment the top pointer and place the
new element at the updated top index.
- Pop Operation:
- Remove the element at the top index and
decrement the top pointer.
- Peek (or Top) Operation:
- Retrieve the element at the top index
without modifying the stack.
Linked List-Based Implementation:
In a linked list-based implementation, a linked list is used to represent the stack.
Pictures:- From web resource
The key components
include:
1. Node:
- A node structure that holds the data
element and a pointer to the next node.
- The top of the stack corresponds to the
head of the linked list.
2. Top Pointer:
- A variable (often called "top")
that points to the head node of the linked list.
- Initially set to null when the stack is
empty.
3. Operations:
- Push Operation:
- Create a new node, set its data, and
make it the new head of the linked list. Update the top pointer.
- Pop Operation:
- Remove the head node from the linked
list. Update the top pointer to the next node.
- Peek (or Top) Operation:
- Retrieve the data from the head node
without modifying the stack.
Example of a stack
structure in C++ using an array-based implementation:
#include
<iostream>
#define MAX_SIZE
100
class Stack {
private:
int arr[MAX_SIZE];
int top;
public:
Stack() {
top = -1;
}
void push(int value) {
if (top < MAX_SIZE - 1) {
arr[++top] = value;
std::cout << "Pushed:
" << value << std::endl;
} else {
std::cout << "Stack
Overflow: Cannot push " << value << "." <<
std::endl;
}
}
void pop() {
if (top >= 0) {
std::cout << "Popped:
" << arr[top--] << std::endl;
} else {
std::cout << "Stack
Underflow: Cannot pop from an empty stack." << std::endl;
}
}
int peek() {
if (top >= 0) {
return arr[top];
} else {
std::cout << "Stack is
empty." << std::endl;
return -1; // Placeholder for an
empty stack
}
}
};
int main() {
Stack stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "Top element:
" << stack.peek() << std::endl;
stack.pop();
stack.pop();
stack.pop();
stack.pop(); // Trying to pop from an empty
stack
return 0;
}
------------------------------------------
Basic overview of
the operations:
----------------------------------------
In a stack data
structure, several primitive operations are commonly defined to manipulate and
manage the stack.
The fundamental
operations include:
1. Push Operation:
- Description: Adds an element to the top of
the stack.
- Algorithm:
Algorithm Push(stack, element):
1. Increment the top pointer.
2. Set the value of the top index to
the new element.
2. Pop Operation:
- Description: Removes the element from the
top of the stack.
- Algorithm:
Algorithm Pop(stack):
1. If the stack is not empty:
a. Retrieve the value at the top
index.
b. Decrement the top pointer.
c. Return the retrieved value.
2. Otherwise, indicate that the stack
is empty.
3. Peek (or Top)
Operation:
- Description: Retrieves the element at the
top of the stack without removing it.
- Algorithm:
Algorithm Peek(stack):
1. If the stack is not empty:
a. Return the value at the top
index.
2. Otherwise, indicate that the stack
is empty.
4. IsEmpty
Operation:
- Description: Checks if the stack is empty.
- Algorithm:
Algorithm IsEmpty(stack):
1. Return true if the top pointer is
-1 (indicating an empty stack); otherwise, return false.
5. Size Operation:
- Description: Returns the number of
elements currently in the stack.
- Algorithm:
Algorithm Size(stack):
1. Return the value of the top pointer
+ 1.
------------------------------
Examples of
primitive operations of the stack according to c++ and Python
C++ Example:
#include
<iostream>
#define MAX_SIZE 5
class Stack {
private:
int arr[MAX_SIZE];
int top;
public:
Stack() {
top = -1;
}
void push(int element) {
if (top < MAX_SIZE - 1) {
arr[++top] = element;
std::cout << "Pushed:
" << element << std::endl;
} else {
std::cout << "Stack
Overflow: Cannot push " << element << "." <<
std::endl;
}
}
int pop() {
if (top >= 0) {
int poppedValue = arr[top--];
std::cout << "Popped:
" << poppedValue << std::endl;
return poppedValue;
} else {
std::cout << "Stack
Underflow: Cannot pop from an empty stack." << std::endl;
return -1; // Placeholder for an
empty stack
}
}
int peek() {
if (top >= 0) {
return arr[top];
} else {
std::cout << "Stack is
empty." << std::endl;
return -1; // Placeholder for an
empty stack
}
}
bool isEmpty() {
return top == -1;
}
int size() {
return top + 1;
}
};
int main() {
Stack stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "Top element:
" << stack.peek() << std::endl;
stack.pop();
stack.pop();
stack.pop();
stack.pop(); // Trying to pop from an empty
stack
return 0;
}
-------------------------------------------
Python Example:
class Stack:
def __init__(self):
self.arr = []
def push(self, element):
self.arr.append(element)
print(f"Pushed: {element}")
def pop(self):
if not self.is_empty():
popped_value = self.arr.pop()
print(f"Popped:
{popped_value}")
return popped_value
else:
print("Stack Underflow: Cannot
pop from an empty stack.")
return None # Placeholder for an empty stack
def peek(self):
if not self.is_empty():
return self.arr[-1]
else:
print("Stack is empty.")
return None # Placeholder for an empty stack
def is_empty(self):
return len(self.arr) == 0
def size(self):
return len(self.arr)
# Example Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Top
element:", stack.peek())
stack.pop()
stack.pop()
stack.pop()
stack.pop() # Trying to pop from an empty stack
-------------------------------------------------
INFIX, POSTFIX,
PREFIX IN STACK.
In computer
science and mathematics, infix, postfix, and prefix notations are ways to
represent mathematical expressions.
These notations
describe the placement of operators and operands within an expression.
Stacks are often
used in the conversion between these notations.
1. Infix Notation:
In infix notation,
operators are written between their operands. This is the typical mathematical
notation that we use, where operators are placed in the middle of expressions.
Example:
Infix: 3 + 4 * (2 - 7)
2. Postfix (or Reverse Polish Notation)
Notation:
In postfix
notation, also known as Reverse Polish Notation (RPN), operators are placed
after their operands. To evaluate a postfix expression, you can use a stack
data structure.
Example:
Postfix: 3 4 2 7 -
* +
3. Prefix (or Polish Notation) Notation:
In prefix
notation, also known as Polish Notation, operators are placed before their
operands. Similar to postfix notation, a stack can be used to evaluate a prefix
expression.
Example:
Prefix: + 3 * 4 -
2 7
Conversion between Notations:
1. Infix to
Postfix:
- Use a stack to convert an infix expression
to postfix.
The stack helps
maintain the correct order of operators.
- Algorithm:
- Scan the infix expression from left to
right.
- Use a stack to keep track of operators.
- Output operands as they arrive.
- For each operator encountered, pop
operators from the stack and output them until the stack is empty or an
operator with lower precedence is encountered. Then, push the current operator
onto the stack.
- At the end, pop any remaining operators
from the stack and output them.
2. Infix to
Prefix:
- Similar to infix to postfix conversion but
in reverse order. Use a stack to keep track of operators and operands.
- Algorithm:
- Reverse the infix expression.
- Use a stack to convert the reversed
infix expression to postfix.
- Reverse the result obtained to get the
final prefix expression.
3. Postfix to
Infix:
- Use a stack to convert a postfix
expression to infix. Operand values are pushed onto the stack, and operators
are popped and applied when encountered.
- Algorithm:
- Scan the postfix expression from left to
right.
- Use a stack to keep track of operands.
- When an operand is encountered, push it
onto the stack.
- When an operator is encountered, pop the
required number of operands from the stack, apply the operator, and push the
result back onto the stack.
4. Prefix to
Infix:
- Similar to postfix to infix conversion but
in reverse order.
- Algorithm:
- Reverse the prefix expression.
- Use a stack to convert the reversed
prefix expression to postfix.
- Reverse the result obtained to get the
final infix expression.
These notations
are useful in evaluating expressions and can be preferred in certain
situations, such as for parsing or when building calculators.
----------------------------------
Examples of Infix,
postfix, prefix in stack with c++ and python
C++ Examples: # Infix to Postfix Conversion:
#include
<iostream>
#include
<stack>
#include
<unordered_map>
bool
isOperator(char c) {
return c == '+' || c == '-' || c == '*' ||
c == '/';
}
int
getPrecedence(char op) {
std::unordered_map<char, int>
precedence;
precedence['+'] = precedence['-'] = 1;
precedence['*'] = precedence['/'] = 2;
return precedence[op];
}
std::string
infixToPostfix(const std::string& infix) {
std::stack<char> stack;
std::string postfix;
for (char c : infix) {
if (isalnum(c)) {
postfix += c; // Operand, append to
the result
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (!stack.empty() &&
stack.top() != '(') {
postfix += stack.top();
stack.pop();
}
stack.pop(); // Discard '('
} else if (isOperator(c)) {
while (!stack.empty() &&
getPrecedence(stack.top()) >= getPrecedence(c)) {
postfix += stack.top();
stack.pop();
}
stack.push(c);
}
}
while (!stack.empty()) {
postfix += stack.top();
stack.pop();
}
return postfix;
}
int main() {
std::string infixExpression = "3 + 4 *
(2 - 7)";
std::string postfixExpression =
infixToPostfix(infixExpression);
std::cout << "Infix Expression:
" << infixExpression << std::endl;
std::cout << "Postfix
Expression: " << postfixExpression << std::endl;
return 0;
}
# Postfix to Infix
Conversion:
#include
<iostream>
#include
<stack>
bool
isOperator(char c) {
return c == '+' || c == '-' || c == '*' ||
c == '/';
}
std::string
postfixToInfix(const std::string& postfix) {
std::stack<std::string> stack;
for (char c : postfix) {
if (isalnum(c)) {
stack.push(std::string(1, c)); //
Operand, push to stack
} else if (isOperator(c)) {
std::string operand2 = stack.top();
stack.pop();
std::string operand1 = stack.top();
stack.pop();
std::string result = "("
+ operand1 + c + operand2 + ")";
stack.push(result);
}
}
return stack.top();
}
int main() {
std::string postfixExpression =
"3427-*+";
std::string infixExpression =
postfixToInfix(postfixExpression);
std::cout << "Postfix
Expression: " << postfixExpression << std::endl;
std::cout << "Infix Expression:
" << infixExpression << std::endl;
return 0;
}
Python Examples: # Infix to Postfix Conversion:
def
infix_to_postfix(infix):
stack = []
postfix = ""
precedence = {'+': 1, '-': 1, '*': 2, '/':
2}
for c in infix:
if c.isalnum():
postfix += c
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.pop() # Discard '('
elif c in precedence:
while stack and
precedence[stack[-1]] >= precedence[c]:
postfix += stack.pop()
stack.append(c)
while stack:
postfix += stack.pop()
return postfix
infix_expression =
"3 + 4 * (2 - 7)"
postfix_expression
= infix_to_postfix(infix_expression)
print("Infix
Expression:", infix_expression)
print("Postfix
Expression:", postfix_expression)
# Postfix to Infix
Conversion:
def
postfix_to_infix(postfix):
stack = []
for c in postfix:
if c.isalnum():
stack.append(c)
elif c in {'+', '-', '*', '/'}:
operand2 = stack.pop()
operand1 = stack.pop()
result =
f"({operand1}{c}{operand2})"
stack.append(result)
return stack[0]
postfix_expression
= "3427-*+"
infix_expression =
postfix_to_infix(postfix_expression)
print("Postfix
Expression:", postfix_expression)
print("Infix
Expression:", infix_expression)
-----------------------------------------------------
Conversions of
Infix, postfix, prefix.
In Python implement
functions for each conversion:
Infix to Postfix Conversion:
def
infix_to_postfix(infix):
stack = []
postfix = ""
precedence = {'+': 1, '-': 1, '*': 2, '/':
2}
for c in infix:
if c.isalnum():
postfix += c
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.pop() # Discard '('
elif c in precedence:
while stack and
precedence[stack[-1]] >= precedence[c]:
postfix += stack.pop()
stack.append(c)
while stack:
postfix += stack.pop()
return postfix
# Example
infix_expression =
"3 + 4 * (2 - 7)"
postfix_expression
= infix_to_postfix(infix_expression)
print("Infix
to Postfix:")
print("Infix
Expression:", infix_expression)
print("Postfix
Expression:", postfix_expression)
Infix to Prefix Conversion:
def
infix_to_prefix(infix):
stack = []
prefix = ""
precedence = {'+': 1, '-': 1, '*': 2, '/':
2}
for c in infix[::-1]: # Reverse the infix expression
if c.isalnum():
prefix += c
elif c == ')':
stack.append(c)
elif c == '(':
while stack and stack[-1] != ')':
prefix += stack.pop()
stack.pop() # Discard ')'
elif c in precedence:
while stack and
precedence[stack[-1]] > precedence[c]:
prefix += stack.pop()
stack.append(c)
while stack:
prefix += stack.pop()
return prefix[::-1] # Reverse the result to get the prefix
expression
# Example
infix_expression =
"3 + 4 * (2 - 7)"
prefix_expression
= infix_to_prefix(infix_expression)
print("\nInfix
to Prefix:")
print("Infix
Expression:", infix_expression)
print("Prefix
Expression:", prefix_expression)
Postfix to Infix Conversion:
def
postfix_to_infix(postfix):
stack = []
for c in postfix:
if c.isalnum():
stack.append(c)
elif c in {'+', '-', '*', '/'}:
operand2 = stack.pop()
operand1 = stack.pop()
result =
f"({operand1}{c}{operand2})"
stack.append(result)
return stack[0]
# Example
postfix_expression
= "3427-*+"
infix_expression =
postfix_to_infix(postfix_expression)
print("\nPostfix
to Infix:")
print("Postfix
Expression:", postfix_expression)
print("Infix
Expression:", infix_expression)
Prefix to Infix Conversion:
def
prefix_to_infix(prefix):
stack = []
for c in reversed(prefix): # Reverse the prefix expression
if c.isalnum():
stack.append(c)
elif c in {'+', '-', '*', '/'}:
operand1 = stack.pop()
operand2 = stack.pop()
result =
f"({operand1}{c}{operand2})"
stack.append(result)
return stack[0]
# Example
prefix_expression
= "+3*42-7"
infix_expression =
prefix_to_infix(prefix_expression)
print("\nPrefix
to Infix:")
print("Prefix
Expression:", prefix_expression)
print("Infix
Expression:", infix_expression)
-----------------------------------------------
Examples of
Conversions of Infix, postfix, prefix in stack with c++ and python.
C++ Examples: # Infix to Postfix
Conversion:
#include
<iostream>
#include
<stack>
#include
<unordered_map>
bool
isOperator(char c) {
return c == '+' || c == '-' || c == '*' ||
c == '/';
}
int
getPrecedence(char op) {
std::unordered_map<char, int>
precedence;
precedence['+'] = precedence['-'] = 1;
precedence['*'] = precedence['/'] = 2;
return precedence[op];
}
std::string
infixToPostfix(const std::string& infix) {
std::stack<char> stack;
std::string postfix;
for (char c : infix) {
if (isalnum(c)) {
postfix += c; // Operand, append to
the result
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (!stack.empty() &&
stack.top() != '(') {
postfix += stack.top();
stack.pop();
}
stack.pop(); // Discard '('
} else if (isOperator(c)) {
while (!stack.empty() &&
getPrecedence(stack.top()) >= getPrecedence(c)) {
postfix += stack.top();
stack.pop();
}
stack.push(c);
}
}
while (!stack.empty()) {
postfix += stack.top();
stack.pop();
}
return postfix;
}
int main() {
std::string infixExpression = "3 + 4 *
(2 - 7)";
std::string postfixExpression =
infixToPostfix(infixExpression);
std::cout << "Infix Expression:
" << infixExpression << std::endl;
std::cout << "Postfix
Expression: " << postfixExpression << std::endl;
return 0;
}
# Postfix to Infix
Conversion:
#include
<iostream>
#include
<stack>
bool
isOperator(char c) {
return c == '+' || c == '-' || c == '*' ||
c == '/';
}
std::string
postfixToInfix(const std::string& postfix) {
std::stack<std::string> stack;
for (char c : postfix) {
if (isalnum(c)) {
stack.push(std::string(1, c)); //
Operand, push to stack
} else if (isOperator(c)) {
std::string operand2 = stack.top();
stack.pop();
std::string operand1 = stack.top();
stack.pop();
std::string result = "("
+ operand1 + c + operand2 + ")";
stack.push(result);
}
}
return stack.top();
}
int main() {
std::string postfixExpression =
"3427-*+";
std::string infixExpression =
postfixToInfix(postfixExpression);
std::cout << "Postfix
Expression: " << postfixExpression << std::endl;
std::cout << "Infix Expression:
" << infixExpression << std::endl;
return 0;
}
Python Examples: # Infix to Postfix
Conversion:
def
infix_to_postfix(infix):
stack = []
postfix = ""
precedence = {'+': 1, '-': 1, '*': 2, '/':
2}
for c in infix:
if c.isalnum():
postfix += c
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.pop() # Discard '('
elif c in precedence:
while stack and
precedence[stack[-1]] >= precedence[c]:
postfix += stack.pop()
stack.append(c)
while stack:
postfix += stack.pop()
return postfix
# Example
infix_expression =
"3 + 4 * (2 - 7)"
postfix_expression
= infix_to_postfix(infix_expression)
print("Infix
Expression:", infix_expression)
print("Postfix
Expression:", postfix_expression)
# Postfix to Infix
Conversion:
def
postfix_to_infix(postfix):
stack = []
for c in postfix:
if c.isalnum():
stack.append(c)
elif c in {'+', '-', '*', '/'}:
operand2 = stack.pop()
operand1 = stack.pop()
result =
f"({operand1}{c}{operand2})"
stack.append(result)
return stack[0]
# Example
postfix_expression
= "3427-*+"
infix_expression =
postfix_to_infix(postfix_expression)
print("Postfix
Expression:", postfix_expression)
print("Infix
Expression:", infix_expression)
-----------------------------------------------------------------
Recursion Array in
stack.
1. Recursion:
- Recursion is a programming concept where a
function calls itself in its definition. In the context of data structures,
recursive algorithms are often used to solve problems by breaking them down
into simpler subproblems.
- Recursive functions typically have a base
case that defines the termination condition, and they make progress toward
reaching the base case.
2. Array:
- An array is a data structure that stores
elements of the same type in contiguous memory locations. Elements in an array
can be accessed using an index.
3. Stack:
- A stack is a data structure that follows
the Last In, First Out (LIFO) principle. It supports two main operations: push
(to add an element to the top) and pop (to remove the top element).
depth-first search
(DFS) algorithms often use recursion to explore elements in an array-like
structure, and the call stack is effectively used to keep track of the
recursive calls.
-------------------------------------------------------------------
Recursion Array in
stack.
A recursive
algorithm involving arrays and a stack-like structure.
Example:- a
depth-first search (DFS) on a graph or tree.
Recursion is often
used, and the call stack implicitly acts as a stack to keep track of the
traversal.
Algorithm for a
recursive DFS using an array and a stack-like structure:
Algorithm
RecursiveDFS(graph, startNode, visited):
1. If the startNode is not visited:
a. Mark the startNode as visited.
b. Process the startNode (perform any
desired operation).
// Recursive step for each adjacent
node
c. For each neighborNode of startNode:
i. Recursively call
RecursiveDFS(graph, neighborNode, visited).
2. End.
// Example usage
visited = Array of
size |V| (initialized to all false, where |V| is the number of nodes)
RecursiveDFS(graph,
startNode, visited)
In this algorithm:
- `graph` represents the graph (adjacency list or matrix).
- `startNode` is
the node from which the DFS starts.
- `visited` is an
array to keep track of visited nodes.
The algorithm starts the DFS from the `startNode` and recursively explores its neighbors. The `visited` array is used to avoid processing the same node multiple times.
Example:- implementation in Python for an undirected
graph represented as an adjacency list:
def
recursive_dfs(graph, node, visited):
if not visited[node]:
visited[node] = True
print(f"Visited node:
{node}")
for neighbor in graph[node]:
recursive_dfs(graph, neighbor,
visited)
# Example usage
graph = {0: [1,
2], 1: [0, 3], 2: [0, 4], 3: [1], 4: [2]}
visited = [False]
* len(graph)
recursive_dfs(graph,
0, visited)
C++ Example:
#include
<iostream>
#include
<vector>
#include
<stack>
void recursiveDFS(const std::vector<std::vector<int>>& graph, int startNode, std::vector<bool>& visited) {
if (!visited[startNode]) {
visited[startNode] = true;
std::cout << "Visited node:
" << startNode << std::endl;
for (int neighbor : graph[startNode]) {
recursiveDFS(graph, neighbor,
visited);
}
}
}
int main() {
std::vector<std::vector<int>>
graph = {{1, 2}, {0, 3}, {0, 4}, {1}, {2}};
std::vector<bool>
visited(graph.size(), false);
recursiveDFS(graph, 0, visited);
return 0;
}
Python Example:
def recursive_dfs(graph,
start_node, visited):
if not visited[start_node]:
visited[start_node] = True
print(f"Visited node:
{start_node}")
for neighbor in graph[start_node]:
recursive_dfs(graph, neighbor,
visited)
# Example usage
graph = {0: [1,
2], 1: [0, 3], 2: [0, 4], 3: [1], 4: [2]}
visited = [False]
* len(graph)
recursive_dfs(graph,
0, visited)
---------------------------------------------------
Linked Representation of Stack
The linked
representation of a stack involves implementing a stack using a linked list
data structure.
In this
representation, each element of the stack is a node in a linked list, and the
top of the stack is the head of the linked list.
Key components and
characteristics of the linked representation of a stack:
1. Node Structure:
- Each node in the linked list contains two
parts: a data part to store the element, and a link (or pointer) part to
reference the next node in the list.
2. Top of the
Stack:
- The top of the stack corresponds to the
head of the linked list.
3. Push Operation:
- To push an element onto the stack, a new
node is created, the data is stored in the new node, and the new node becomes
the new head of the linked list.
4. Pop Operation:
- To pop an element from the stack, the head
node is removed, and the next node (if any) becomes the new head.
5. Peek Operation:
- The peek operation can be implemented by
accessing the data in the head node without modifying the stack.
Example:- linked
representation of a stack in C++:
#include
<iostream>
// Node structure
template
<typename T>
struct Node {
T data;
Node* next;
Node(T value) : data(value), next(nullptr)
{}
};
// Stack class
using linked representation
template
<typename T>
class LinkedStack
{
private:
Node<T>* top;
public:
LinkedStack() : top(nullptr) {}
void push(T value) {
Node<T>* newNode = new
Node<T>(value);
newNode->next = top;
top = newNode;
}
void pop() {
if (!isEmpty()) {
Node<T>* temp = top;
top = top->next;
delete temp;
} else {
std::cout << "Stack
Underflow: Cannot pop from an empty stack." << std::endl;
}
}
T peek() const {
if (!isEmpty()) {
return top->data;
} else {
std::cout << "Stack is
empty." << std::endl;
return T(); // Placeholder for an
empty stack
}
}
bool isEmpty() const {
return top == nullptr;
}
};
int main() {
LinkedStack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "Top element:
" << stack.peek() << std::endl;
stack.pop();
stack.pop();
stack.pop();
stack.pop(); // Trying to pop from an empty
stack
return 0;
}
Example:-
#include
<iostream>
template <typename T>
struct Node {
T data;
Node* next;
Node(T value) : data(value), next(nullptr)
{}
};
template
<typename T>
class LinkedStack
{
private:
Node<T>* top;
public:
LinkedStack() : top(nullptr) {}
void push(T element) {
Node<T>* newNode = new
Node<T>(element);
newNode->next = top;
top = newNode;
}
void pop() {
if (!isEmpty()) {
Node<T>* temp = top;
top = top->next;
delete temp;
} else {
std::cout << "Stack
Underflow: Cannot pop from an empty stack." << std::endl;
}
}
T peek() const {
if (!isEmpty()) {
return top->data;
} else {
std::cout << "Stack is
empty." << std::endl;
return T(); // Placeholder for an
empty stack
}
}
bool isEmpty() const {
return top == nullptr;
}
};
int main() {
LinkedStack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "Top element:
" << stack.peek() << std::endl;
stack.pop();
stack.pop();
stack.pop();
stack.pop(); // Trying to pop from an empty
stack
return 0;
}
C++ Example:
#include
<iostream>
template
<typename T>
struct Node {
T data;
Node* next;
Node(T value) : data(value), next(nullptr)
{}
};
template
<typename T>
class LinkedStack
{
private:
Node<T>* top;
public:
LinkedStack() : top(nullptr) {}
void push(T element) {
Node<T>* newNode = new
Node<T>(element);
newNode->next = top;
top = newNode;
}
void pop() {
if (!isEmpty()) {
Node<T>* temp = top;
top = top->next;
delete temp;
} else {
std::cout << "Stack
Underflow: Cannot pop from an empty stack." << std::endl;
}
}
T peek() const {
if (!isEmpty()) {
return top->data;
} else {
std::cout << "Stack is
empty." << std::endl;
return T(); // Placeholder for an
empty stack
}
}
bool isEmpty() const {
return top == nullptr;
}
};
int main() {
LinkedStack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << "Top element:
" << stack.peek() << std::endl;
stack.pop();
stack.pop();
stack.pop();
stack.pop(); // Trying to pop from an empty
stack
return 0;
}
----------------------------------------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedStack:
def __init__(self):
self.top = None
def push(self, element):
new_node = Node(element)
new_node.next = self.top
self.top = new_node
def pop(self):
if not self.is_empty():
temp = self.top
self.top = self.top.next
del temp
else:
print("Stack Underflow: Cannot
pop from an empty stack.")
def peek(self):
if not self.is_empty():
return self.top.data
else:
print("Stack is empty.")
return None
def is_empty(self):
return self.top is None
# Example usage
stack =
LinkedStack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Top
element:", stack.peek())
stack.pop()
stack.pop()
stack.pop()
stack.pop() # Trying to pop from an empty stack
The linked
representation of a stack is widely used in various applications where a
dynamic and flexible data structure is required.
Some common use
cases and scenarios where the linked representation of a stack is beneficial:
1. Dynamic Memory
Management:
- Linked representation allows for dynamic
memory allocation and deallocation, making it suitable for scenarios where the
size of the stack is not known in advance.
2. Function Call
Management (Call Stack):
- In programming languages that support
recursion or function calls, a stack is used to manage the execution context of
each function call. The linked representation is well-suited for this purpose.
3. Undo Mechanism
in Applications:
- In applications where an "undo"
mechanism is needed (e.g., text editors, graphic design tools), a stack can be
used to maintain the history of operations. The linked representation
facilitates easy undo and redo operations.
4. Expression
Evaluation:
- The linked stack is commonly used in
expression evaluation algorithms, such as converting infix expressions to
postfix or prefix notations and evaluating postfix or prefix expressions.
5. Backtracking
Algorithms:
- Backtracking algorithms, such as those
used in solving puzzles or searching for solutions, often rely on a stack to
keep track of choices. The linked representation supports the dynamic nature of
these algorithms.
6. Memory
Management in Operating Systems:
- Operating systems use stacks for managing
function calls, interrupt handling, and storing local variables. The linked
representation allows for efficient memory usage.
7. Undo/Redo in
Software Applications:
- In software applications, especially
graphic design tools or document editors, the linked representation of a stack
can be employed to implement undo and redo functionality.
8. Parenthesis
Matching and Syntax Parsing:
- Linked stacks are useful in algorithms
that involve checking for balanced parentheses, syntax parsing, and validation
of expressions.
9. Transaction
Management in Databases:
- In database systems, linked stacks can be
used to manage transactions. The ability to roll back transactions and maintain
a transaction history is crucial.
10. Algorithmic
Problem Solving:
- Various algorithmic problems, especially
those involving depth-first search, backtracking, and tree traversal, can be
efficiently solved using a linked stack.
======================
0 Comments