STACK LAB
Manual
Outline
• Stack Implementation using array
• Stack Implementation using Linked List
• Application of Stack
• Infix to Postfix expression
Stack
•A stack is a list with the restriction that insertions and deletions
can be performed in only one position, namely, the end of the list,
called the top.
•A stack is also an Abstract Data Type (ADT), commonly used in
most programming languages.
• It is named stack as it behaves like a real-world stack,
• for example – a deck of cards or a pile of plates, stack of chairs etc.
3
Stack Operations
Basic Operations
• Push - Pushing (storing) an element on the stack.
• Pop - Removing (accessing) an element from the stack.
Supportive operations
• GetTop - reads (only reading, not deleting) an element from the
top of the stack
• Stack_initialization - sets up the stack in an empty condition
• isEmpty - checks whether the stack is empty
• isFull - checks whether the stack is full
Stack implementation (using
array)
• One of the two sides of the array can be considered as the top (upper)
side and the other as the bottom (lower)
• the upper side is most commonly used
• The first element is stored at Stack[0], the second element at Stack[1]
…..last Stack[n-1]
• Associated with the array will be an integer variable, top, which points to
the top element in the stack.
• The initial value of top is -1 when the stack is empty.
• It can hold the elements from index 0, and can grow to a maximum of n - 1 as
this is a static stack using arrays.
Data Structure and Algorithm
Stack implementation (using
linked list)
• In linked list implementation of stack, the nodes are maintained non contiguous in
the memory.
• Stack is said to be overflown if the space left in the memory is not enough to
create a node.
algorithm to convert an infix to a
postfix
• The order of the operand remains the same in the infix and the postfix notations.(from
observation)
• The sequence of operands, output postfix = input infix expression.
• Hence, the operands from the infix expression can be immediately sent to the output as they
occur.
• To handle the operators, the operands are stored in the stack until the right moment and they
are unstacked (removed from the stack); they are then passed to the output.
• Try 1
• If in stack operator priority is greater than the incoming operator, pop the operator otherwise push it
Data Structure and Algorithm 11
Infix to Postfix Conversion
The following is a simple algorithm to convert infix expression to postfix:
Scans characters in given expression from left to right.
If character is an operand
Immediately place onto the output
If character is an operator
If top operator has lower priority or left parentheses
Push operator onto stack
Otherwise
Pop operator from the stack and place onto the output until find an entry of lower priority or until we find left
parentheses
If character is parenthesis
If it is right parentheses
Pop entries from the stack and place onto the output until find left parentheses, pop the left parentheses too
but do not place onto the output
Otherwise
Push the left parenthesis onto stack
If no character (reach end of the expression)
Pop entries from the stack and place onto the output until the stack is empty
