3.
STACK
WHAT IS STACK?
• A stack is an ordered list in which insertion and deletion are done at one end,
called top.
• The last element inserted is the first one to be deleted. Hence, it is called the
Last in
First out (LIFO) or First in Last out (FILO) list.
• Other names used for stacks are “piles” and “push-down lists”
• Examples : stack of dishes, stack of folded towels.
BASIC OPERATIONS
• Two basic operations:
• Push: is the term used to insert an element into a
stack.
• Pop: is the term used to delete an element from a
stack.
ARRAY REPRESENTATION OF STACK
• Push
• [Stack already filled?]
If TOP=MAXSTK, then Print:OVERFLOW, and
Return
• Set TOP:=TOP+1
• Set STACK[TOP]:=ITEM
• Return
ARRAY REPRESENTATION OF STACK
• Pop
• [Stack has an item to be removed?]
If TOP=0, then Print:UNDERFLOW, and
Return
• Set ITEM:=STACK[TOP]
• Set TOP=TOP-1
• Return
LINKED REPRESENTATION OF STACK (PUSH)
• [OVERFLOW?],Write:OVERFLOW and Exit.
[Remove first node from AVAIL list]
• Set NEW:=AVAIL and AVAIL:=LINK[AVAIL]
• Set INFO[NEW]:=ITEM [Copies new data into new
node]
• Set LINK[NEW]:=TOP
• Set TOP:=NEW
• EXIT
LINKED REPRESENTATION OF STACK (POP)
• [UNDERFLOW?], Write:UNDERFLOW and Exit. (TOP=NULL)
• Set ITEM:=INFO[TOP]
• Set TEMP:=TOP and TOP=LINK[TOP]
• Set LINK[TEMP]:=AVAIL and AVAIL:=TEMP [Return deleted node to AVAIL
list]
• EXIT
DISCUSS HOW STACKS CAN BE USED FOR
CHECKING BALANCING OF SYMBOLS.
• a) Create a stack.
• b) while (end of input is not reached) {
• 1) If the character read is not a symbol to be balanced, ignore it.
• 2) If the character is an opening symbol like (, [, {, push it onto the stack
• 3) If it is a closing symbol like ),],}, then if the stack is empty report an error.
Otherwise pop
the stack.
• 4) If the symbol popped is not the corresponding opening symbol, report an error.}
• c) At end of input, if the stack is not empty report an error
EXAMPLES
LET US ASSUME THAT THE INPUT IS: () (()
[()])
INFIX TO POSTFIX CONVERSION ALGORITHM
USING STACK.
• An infix expression is a single letter, or an operator, proceeded by one infix
string and followed by another Infix string.
• Prefix: A prefix expression is a single letter, or an operator, followed by two
prefix strings. Every prefix string longer than a single variable contains an
operator, first operand and second operand.
• A postfix expression (also called Reverse Polish Notation) is a single
letter or an operator, preceded by two postfix strings. Every postfix
string longer than a single variable contains first and second operands
followed by an operator.
EXAMPLE
INFIX TO POSTFIX CONVERSION ALGORITHM
USING STACK.
• a) Create a stack
• b) for each character t in the input
stream
• c) pop and output tokens until the stack is
empty
INFIX TO POSTFIX CONVERSION ALGORITHM
USING STACK.
example: A * B- (C + D) +
E
INFIX TO POSTFIX CONVERSION ALGORITHM
USING STACK.
• infix to postfix conversion algorithm using
stack.
POSTFIX EVALUATION USING STACKS
1. Scan the Postfix string from left to right.
2. Initialize an empty stack.
3. Repeat steps 4 and 5 till all the characters are scanned.
4. If the scanned character is an operand, push it onto the stack.
5. If the scanned character is an operator, and if the operator is a unary operator, then pop an
element from the stack. If the operator is a binary operator, then pop two elements from
the stack. After popping the elements, apply the operator to those popped elements. Let
the result of this operation be retVal onto the stack.
6. After all characters are scanned, we will have only one element in the stack.
7. Return top of the stack as result.
POSTFIX EVALUATION USING STACKS
POSTFIX EVALUATION USING STACKS
POSTFIX EVALUATION USING STACKS
ARRAY REPRESENTATION OF STACK (PUSH)
void
push(void);
void
pop(void);
void push()
{ if(top>=n-1)
{ printf("\n\tSTACK is over flow"); }
else { printf(" Enter a value to be
pushed:"); s scanf("%d",&x);
top++;
stack[top]=x;
}
}
ARRAY REPRESENTATION OF STACK (POP)
void pop() { if(top<=-1)
{ printf("\n\t Stack is under flow"); }
else { printf("\n\t The popped elements is
%d",stack[top]);
top--; }
}
void display()
{
printf("\n The elements in STACK
\n"); for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
}
LINKED REPRESENTATION OF STACK (PUSH)
struct Node
{ int data;
struct Node *next;
}; Node* top =
NULL;
void push(int value)
{
struct Node *newNode;
newNode = (struct Node *)malloc(sizeof(struct
Node)); newNode->data = value;
newNode->next = top;
top = newNode; // top always points to the newly
created node
printf("Node is Inserted\n\n"); }
LINKED REPRESENTATION OF STACK (POP)
struct Node
{ int data;
struct Node *next;
}; Node* top =
NULL;
int pop()
{ if (top == NULL)
{ printf("\nEMPTY STACK");
} else {
struct Node *temp = top;
int temp_data = top->data; //to store data of
top node
top = top->next;
free(temp); //deleting the node return
temp_data; } return temp_data; } }