What is a stack?
• Stores a set of elements in a particular order.
• Stack principle: LAST IN FIRST OUT= LIFO
• It means: the last element inserted is the first one to be
removed.
Stack Representation
• Can be implemented by means of Array, Structure,
Pointers and Linked List.
• Stack can either be a fixed size or dynamic. 2
push
pop
create
STACK
isempty
isfull
3
STACK: Last-In-First-Out (LIFO)
• void push (stack *s, int element);
/* Insert an element in the stack */
• int pop (stack *s);
/* Remove and return the top
element */
• void create (stack *s);
/* Create a new stack */
• int isempty (stack *s);
/* Check if stack is empty */
• int isfull (stack *s);
/* Check if stack is full */
4
Stack using Linked List
5
Push using Linked List
PUSH OPERATION
top
6
Pop using Linked List
POP OPERATION
top
7
Stack Creation
void create (stack *s) void create (stack **top)
{ {
s->top = -1; *top = NULL;
/* s->top points to /* top points to NULL,
last element indicating empty
pushed in; stack */
initially -1 */ }
}
ARRAY LINKED LIST
8
Pushing an element into stack
void push (stack *s, int element) void push (stack **top, int element)
{ {
stack *new;
if (s->top == (MAXSIZE-1))
{ new = (stack *)malloc (sizeof(stack));
printf (“\n Stack overflow”); if (new == NULL)
exit(-1); {
} printf (“\n Stack is full”);
exit(-1);
else
}
{
s->top++; new->value = element;
s->st[s->top] = element; new->next = *top;
} *top = new;
}
}
ARRAY LINKED LIST
9
Popping an element from stack
int pop (stack **top)
{
int pop (stack *s) int t;
{ stack *p;
if (s->top == -1) if (*top == NULL)
{ {
printf (“\n Stack underflow”); printf (“\n Stack is empty”);
exit(-1);
exit(-1); }
} else
else {
{ t = (*top)->value;
p = *top;
return (s->st[s->top--]); *top = (*top)->next;
} free (p);
} return t;
}
}
ARRAY LINKED LIST
10
Checking for stack empty
int isempty (stack *s) int isempty (stack *top)
{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }
ARRAY LINKED LIST
11
Infix and Postfix Notations
• Infix: operators placed between operands:
A+B*C
• Postfix: operands appear before their
operators:-
ABC*+
• There are no precedence rules to learn in
postfix notation, and parentheses are never
needed
CS 11001 : Programming and Data
Lecture #00: © DSamanta 13
Structures
Infix to postfix conversion
• Use a stack for processing operators (push and
pop operations).
• Scan the sequence of operators and operands from
left to right and perform one of the following:
• output the operand,
• push an operator of higher precedence,
• pop an operator and output, till the stack top contains
operator of a lower precedence and push the present
operator.
CS 11001 : Programming and Data
Lecture #00: © DSamanta 15
Structures
The algorithm steps
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto
the stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until
you see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If
the association is left to right, pop and print the top of the stack and then push the
incoming operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop
the stack and print the top operator. Then test the incoming operator against the new top
of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)
CS 11001 : Programming and Data
Lecture #00: © DSamanta 17
Structures
Infix to Postfix Rules
Current Operator Postfix string
Expression: symbol Stack
1 A A
A * (B + C * D) + E 2 * * A
3 ( *( A
becomes
4 B *( AB
ABC D * +* E+ 5 + *(+ AB
6 C *(+ ABC
7 * *(+* ABC
8 D *(+* ABCD
Postfix notation 9 ) * ABCD*+
is also called as
10 + + ABCD*+*
Reverse Polish
11 E + ABCD*+*E
Notation (RPN)
12 ABCD*+*E+
Autumn 2016 19