STack
1
Stack
is a particular kind of Abstract Data Type in which the
main operations on the collection are the addition of an
item to the collection, known as push, only to the top of
the stack and removal of an item, known as pop, only
from the top of the stack.
3
Stack
4
Rule: LIFO( Last
In First Out )
This strategy states that the element
that is inserted last will come out first.
You can take a pile of plates kept on
top of each other as a real-life
example. The plate which we put last is
on the top and since we remove the
plate that is at the top, we can say
that the plate that was put last comes
out first.
5
Basic Operations on Stack
push() pop() top()/peek()
to insert an element into the to remove an element from Returns the top element of
stack the stack the stack
isEmpty() isFull() print()
returns true if stack is empty returns true if stack is Full Prints stack items
else false else false
6
Pseudo Code for
Stack
public class Stack
{
private int[] stackArray;
1. Define a class `Stack` private int top;
private int capacity;
a. Declare private variables:
- `stackArray`: Array to store stack elements. // Constructor to initialize the stack
- `top`: Index of the top element in the stack. public Stack(int size)
- `capacity`: Maximum size of the stack. {
b. Define a constructor `Stack(size)`: stackArray = new int[size];
- Initialize `stackArray` with size `size`. capacity = size;
top = -1; // Stack is initially empty
- Set `capacity` to `size`.
}
- Set `top` to -1 (stack is empty).
7
Pseudo Code for
Stack
public bool IsEmpty()
{
c. Define method `IsEmpty()`: return top == -1;
}
- Return `true` if `top == -1`, else `false`
// Method to check if the stack is full
d. Define method `IsFull()`: public bool IsFull()
{
return top == capacity - 1;
- Return `true` if `top == capacity - 1`, else `false`
}
8
Pseudo Code for
Stack public void Push(int item)
{
if (IsFull())
e. Define method `Push(item)`: {
- If stack is full (`top == capacity - 1`): [Link]("Stack Overflow!
- Print "Stack Overflow! Cannot push item, Cannot push item, stack is full.");
stack is full." return;
- Return }
- Increment `top` by 1 stackArray[++top] = item;
[Link]($"Pushed {item} to
- Add `item` to `stackArray[top]`
the stack.");
- Print "Pushed [item] to the stack." }
9
Pseudo Code for
Stack public int Pop()
{
if (IsEmpty())
f. Define method `Pop()`:
{
- If stack is empty (`top == -1`): [Link]("Stack Underflow!
- Print "Stack Underflow! Cannot pop Cannot pop item, stack is empty.");
item, stack is empty." return -1;
- Return -1 }
- Store `stackArray[top]` in int poppedItem = stackArray[top--];
[Link]($"Popped
`poppedItem`
{poppedItem} from the stack.");
- Decrement `top` by 1 return poppedItem;
- Print "Popped [poppedItem] from the }
stack."
- Return `poppedItem`
10
Pseudo Code for
Stack
public int Peek()
g. Define method `Peek()`: {
if (IsEmpty())
- If stack is empty (`top == -1`): {
[Link]("Stack is
- Print "Stack is empty." empty.");
return -1;
- Return -1 }
return stackArray[top];
- Return `stackArray[top]` }
11
Pseudo Code for
Stack
public void PrintStack()
{
if (IsEmpty())
h. Define method `PrintStack()`: {
[Link]("Stack is
- If stack is empty (`top == -1`): empty.");
return;
- Print "Stack is empty." }
[Link]("Stack elements:");
- Return for (int i = top; i >= 0; i--)
{
- Print "Stack elements:" [Link](stackArray[i]);
}
- Loop from `top` to `0`: }
- Print `stackArray[i]`
14
Possible Applications
Undo/Redo in
text editors Reverse String Bracket Matching
Moving
back/forward in
browsers
15
Prefix, Infix, Postfix expression (notation)
A. () [] {} 8+2*5-(5+3)
B. */% 8+2*5-8
C. +- 8+10-8
18-8
10
16
2
Prefix, Infix, Postfix expression
notation
Prefix, postfix, and infix are three different notations for
writing expressions, particularly in the context of arithmetic
and logical operations.
17
Infix Notation
Infix Notation
Definition: In infix notation, operators are placed between
operands.
Example:
Expression: A + B
More complex: (A + B) * C
18
Prefix Notation (Polish Notation)
Prefix Notation (Polish Notation)
Definition: In prefix notation, also known as Polish notation,
operators are placed before their operands.
Example:
Expression: + A B
More complex: * + A B C → (which represents (A + B) * C)
19
Postfix Notation (Reverse Polish Notation)
Postfix Notation (Reverse Polish Notation)
Definition: In postfix notation, also known as Reverse Polish
Notation (RPN), operators are placed after their operands.
Example:
Expression: A B +
More complex: A B + C * (which represents (A + B) * C)
20
Infix to postfix
Infix: 3+2*5
Postfix: ?
solve
1- Operator Precedence:/ and * have higher precedence than +.Operators of
the same precedence are evaluated based on associativity (left to right for
+ and -, and * and /).
()بحدد أولية العمليات الحسابية
3+2*5
3+2 5*
325*+
21
Infix to postfix
Infix: ((A+B)*C-D)*E
Postfix: ?
solve
((A+B)*C-D) * E
( (A+B) *C-D)*E
(A B+ *C -D) *E
(AB+ C*- D )*E
AB+C*D-*E
AB+C*D-E*
22
Infix to prefix
Infix: 3+2*5
Prefix: ?
solve
1- Operator Precedence:/ and * have higher precedence than +
3+2*5
*3+2 5
+*325
23
Infix to prefix
Infix: ((A+B)*C-D)*E
Prefix: ?
solve
((A+B)*C-D) * E
( (A+B) *C-D)*E
+(A B *C -D) *E
*+(AB C- D )*E
-*+ABC D*E
*-*+ABCDE
24
Infix to postfix using stack
Infix: 3+2*5
Postfix: ?
Solve
Output: 3 2 5 * +
push push pop
25
Infix to postfix using stack
1. Initialize:
○ An empty stack (for operators and parentheses).
○ An empty output queue (for the postfix expression).
2. Scan the expression from left to right:
○ If the token is an operand (E, D, C, B, A), add it to the output queue.
○ If the token is an operator (*, -, +), push it onto the stack while respecting
precedence and associativity, if operator has a higher associativity pop
it first then push the next operator.
○ If the token is an opening parenthesis (, push it onto the stack.
○ If the token is a closing parenthesis ), pop from the stack to the output
queue until an opening parenthesis is encountered.
3. After scanning, pop any remaining operators from the stack to the output
queue.
26
Infix to postfix using stack
Infix: (3+2)*5
Postfix: ?
Solve
Output: 3 2+5 *
push push pop push pop
27
Infix to postfix using stack
Infix: ((A+B)*C-D)*E
Postfix: ?
Solve
Output: AB+C*D-E*
28
Code of convert Infix to postfix using stack
private static bool IsOperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
// Function to determine the precedence of an operator
private static int Precedence(char op)
{
switch (op)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return 0;
}
}
29
Code of convert Infix to postfix using stack
// If the character is a closing parenthesis, pop from the stack to the output
else if (c == ')')
{
public static string ConvertToPostfix(string infix) while ([Link] > 0 && [Link]() != '(')
{ {
Stack<char> stack = new Stack<char>(); // Stack to hold postfix += [Link]();
}
operators [Link](); // Remove the '(' from the stack
string postfix = ""; // Output postfix expression }
// If the character is an operator
foreach (char c in infix) else if (IsOperator(c))
{
{ while ([Link] > 0 && Precedence([Link]()) >=
// If the character is an operand, add it to the output Precedence(c))
if ([Link](c)) {
{ postfix += [Link]();
}
postfix += c; [Link](c);
} }
// If the character is an opening parenthesis, push it } // end of foreach
to the stack
// Pop all the remaining operators from the stack
else if (c == '(') while ([Link] > 0)
{ {
[Link](c); postfix += [Link]();
} }
return postfix;
}
30
Code of convert Infix to postfix using stack
Steps:
1. ( is pushed onto the stack.
2. A is added to the output.
3. + is pushed onto the stack.
static void Main(string[] args) 4. B is added to the output.
{
string infixExpression = "(A+B)*C-D"; 5. ) is encountered, so + is popped from the stack and
[Link]("Infix Expression: " + infixExpression); added to the output.
string postfixExpression = 6. * is pushed onto the stack.
ConvertToPostfix(infixExpression);
[Link]("Postfix Expression: " + 7. C is added to the output.
postfixExpression);
} 8. - is encountered. Since - has lower precedence than *, * is
popped from the stack and added to the output. Then -
is pushed onto the stack.
9. D is added to the output.
10. The remaining operator - is popped from the stack and
added to the output.