Stacks: Array Representation and Implementation of stack, Operations on Stacks: Push & Pop,Array Representation of Stack, Linked Representation of Stack, Operations Associated with Stacks, Application of stack: Conversion of Infix to Prefix and Postfix Expressions, Evaluation of postfix expression using stack.
>>Send ur suggestion to Mynotes Tab
Stack
1 Introduction
6.2 Definition
6.3 Array Representation
6.4 Linked list Representation
6.6 Operations on stacks: Push & Pop
6.6 Application of stack: Conversion of Infix to Prefix
6.7 Application of stack: Conversion of Postfix Expressions
6.8 Application of stack: Evaluation of Postfix Expressions
Stack is a linear data structure in which insertions and deletions are made at one end, called top of the stack. Stack is based on the principle of Last in First Out(LIFO) or First Come Last Serve(FCLS).To keep track of top of the stack, let us assume that we have a variable TOP. Let us also assume that when stack is empty, then TOP=-1.
Representation of Stack: Stack can be represented in memory using:-
(i) Linear array or
(ii) Linked List.
Linear Array representation of stack:
Let us assume that the name of the linear array be arr and this array can hold maximum 5 integer numbers.
There are two ways two represent the stack using linear arrays:-
6.
(i)
Horizontal representation
and
(ii) Vertical Representation
|
2
|
4
|
6
|
8
|
|
|
|
|
|
8
|
|
6
|
|
4
|
|
2
|
 |
|||
 |
|||
horizontal Representaion
Vertical Representation
Operations on stack: The following operations are performed on stacks:-
(i) Init_Stack(): Creates an empty stack.
(ii) Stack_Empty(): Checks whether the stack is empty.
(iii) Stack_Full(): Checks whether the stack is full.
(iv) Push(): Add an item in the stack.
(v) Pop(): Remove an item from the stack.
(vi) MutiPop(): Remove k top items from the stack.
To implement the stack, we need the following:-
(i) A linear array to hold the items of the stack. Let us assume that the name of the array is arr.
(ii) A variable that holds the position of top of the stack. Let us assume that the name of the variable is Top.
We also assume that when the stack is empty, the variable Top holds -1 and our array is going to store maximum 10 integer numbers, although stack can hold any type of data.
We will use declaration:-
typedef enum{FALSE,TRUE}Boolean;
This declaration defines new data type named boolean, which can take values FALSE or TRUE.
We also declare the size of stack and the structure as follows:-
#define MAX 10
typedef struct
{
int Top;
int arr[MAX];
}Stack;
Now, we are in a position to define the stack operations.
(i) Init_Stack(): Creates an empty stack. Before we can use a stack, it is to be initialize. This operation initializes the Top variable to the value -1, meaning stack is empty.
void Init_Stack(Stack *ps)
{
ps -> top=-1;
}
(ii) Stack_Empty(): Checks whether the stack is empty. Before we remove an item from a stack it is necessary to test
that whether the stack is empty or not. This is done by comparing the value of Top variable with -1. If Top variable contains -1, then this operation returns TRUE, otherwise, this operation returns FALSE.
boolean Stack_Empty( Stack *ps)
{
if( ps -> top=-1)
return TRUE;
else
return FALSE;
}
(iii) Stack_Full(): Checks whether the stack is full. Before we add new item on to the stack, we test whether stack have some space to accommodate the incoming item, i.e. we test whether the stack is full or not. If the stack is full, we can not add more items on to the stack. This is done by comparing the value of Top with (MAX - 1). If Top variable contains (MAX -1), then Stack_Full() function returns TRUE, otherwise this function returns FALSE.
boolean Stack_Full(Stack *ps)
{
if ( ps -> Top==(MAX – 1))
return TRUE;
else
return FALSE;
}
(iv) Push(): Add an item in the stack. Before we add new item on
to the stack, we test whether stack have some space to
accommodate the incoming item, i.e. we test whether the stack
is full or not. If the stack is full, we can not add more
items on to the stack. If the stack is not full then, we
increment the value of Top by one so that it points to the
new top of the stack, where the incoming item is placed.
void Push(Stack *ps, int item)
{
if(Stack_Full())
printf(“\n Overflow”);
else
ps -> Top++;
ps -> arr[ps->Top]=item;
}
(v) Pop(): Remove an item from the stack. Before we remove an
item from a stack it is necessary to test that whether the
stack is empty or not. If the stack is not empty, then the
item on the top of the stack is assigned to a local variable,
which later on returned via the return statement. After
assigning the top item to the local variable, the value of Top
variable is decremented by one so that it now points to the
new top of the stack.
int Pop(Stack *ps)
{
int temp;
if(Stack_Empty())
{
printf(“\Underflow”);
exit;
}
else
{
temp=ps -> arr[ps->Top];
ps ->Top--;
}
return temp;
}
(vi) MutiPop(): Removes k top items from the stack. This function
pops k top items from the stack or pops the entire stack if it
contains fewer than k objects.
void MultiPop(Stack *ps,int k)
{
while((!Stack_Empty( ) && k!=-1)
{
Pop(&ps);
k=k-1;
}
}
Application of stack:
There are three types of notation for mathematical expression:-
I. Infix Notation
II. Prefix Notation or Polish Notation
III. Postfix Notation or Suffix Notation
In infix notation, a binary operator is placed in-between its operands. The operations are normally carried out from left to right.
(i) A + B – C
(ii) A + ( B * C ) – (D/E)
(iii) ( A * B ) + C + ( D * E )
In prefix notation a binary operator is placed before its operands. The prefix notation is also known as Polish notation in the honor of the Polish mathematicians Jan Lukasiewicz who developed this notation.
(i) - + A B C
(ii) - + A * B C / D E
(iii) + + * A B C * D E
In postfix notation a binary operator is placed after its operands. The prefix notation is also known as Suffix notation or reverse Police notation.
(i) A B + C –
(ii) A B C * + D E / -
(iii) A B * C + D E * +
Note: In Prefix and Postfix notation no parentheses or brackets are used.
Conversion of infix to Prefix: Algorithm
Step 1: Initialize the stack or create empty stack
Step 2: Reverse the given infix expression
Step 3:[Scan the characters from left to right while there is character left]
Step 3(a): If the character scanned is space or tab then skip.
Step 3(b): If the character scanned is digit or alphabet, then
push to the target string.
Step 3(c): If character scanned is a closing parenthesis, then
push into the stack.
Step 3(d): If the character scanned is operator, then pop the
topmost element from the stack and
(i) if the priority of character popped is higher than the character scanned, then character popped is pushed to the target string and character scanned is pushed in the stack.
(ii) If the priority of the character popped is lower than or equal to the character scanned, then first push back the character popped into the stack and then the character scanned into the stack.
Step 3(e): If the character scanned happens to be an opening
parenthesis, then pop the topmost element of the
stack and push it into target string till it does not
encounter the closing parenthesis.
Step 4: If some operators are still left in the stack, pop them one
by one and push into target string.
Example
Ø Infix Expression: A $ B * C – C + D / A / (E + F)
Ø
Reversed Infix :
) F + E ( / A
/ D + C – C * B $ A
|
Character Scanned
|
Stack Content
|
Target String
|
|
)
|
)
|
Empty
|
|
F
|
)
|
F
|
|
+
|
)+
|
F
|
|
E
|
)+
|
EF
|
|
(
|
Empty
|
+EF
|
|
/
|
/
|
+EF
|
|
A
|
/
|
A+EF
|
|
/
|
//
|
A+EF
|
|
D
|
//
|
DA+EF
|
|
+
|
+
|
// DA+EF
|
|
C
|
+
|
C//DA+EF
|
|
-
|
+-
|
C//DA+EF
|
|
C
|
+-
|
CC//DA+EF
|
|
*
|
+-*
|
CC//DA+EF
|
|
B
|
+-*
|
BCC//DA+EF
|
|
$
|
+-*$
|
BCC//DA+EF
|
|
A
|
+-*$
|
ABCC//DA+EF
|
|
|
|
$ABCC//DA+EF
|
|
|
|
*$ABCC//DA+EF
|
|
|
|
-*$ABCC//DA+EF
|
|
|
empty
|
+-*$ABCC//DA+EF
|
Step 2:[Scan the characters from left to right while there is character left]
Step 3(a): If the character scanned is space or tab then skip.
Step 3(b): If the character scanned is digit or alphabet, then
push to the target string.
Step 3(c): If character scanned is a opening parenthesis, then
push into the stack.
Step 3(d): If the character scanned is operator, then pop the
topmost element from the stack and
(i) if the priority of character popped is higher than or equal to the character scanned, then character popped is pushed to the target string and character scanned is pushed in the stack.
(ii) If the priority of the character popped is
lower than the character scanned, then
first push back the character popped into
the stack and then the character scanned
into the stack.
Step 3(e): If the character scanned happens to be an closing
parenthesis, then pop the topmost element of the
stack and push it into target string till it does not
encounter the opening parenthesis.
Step 4: If some operators are still left in the stack, pop them one
by one and push into target string.
Example
Ø Infix Expression: A $ B * C – C + D / A / (E + F)
|
Character Scanned
|
Stack Content
|
Target String
|
|
A
|
Empty
|
A
|
|
$
|
$
|
A
|
|
B
|
$
|
AB
|
|
*
|
*
|
AB$
|
|
C
|
*
|
AB$C
|
|
-
|
-
|
AB$C*
|
|
C
|
-
|
AB$C*C
|
|
+
|
+
|
AB$C*C-
|
|
D
|
+
|
AB$C*C-D
|
|
/
|
+/
|
AB$C*C-D
|
|
A
|
+/
|
AB$C*C-DA
|
|
/
|
+/
|
AB$C*C-DA/
|
|
(
|
+/(
|
AB$C*C-DA/
|
|
E
|
+/(
|
AB$C*C-DA/E
|
|
+
|
+/(+
|
AB$C*C-DA/E
|
|
F
|
+/(+
|
AB$C*C-DA/EF
|
|
)
|
+/
|
AB$C*C-DA/EF+
|
|
|
+
|
AB$C*C-DA/EF+/
|
|
|
Empty
|
AB$C*C-DA/EF+/+
|
expr: is the arithmetic expression in the postfix notation.
result: is a variable that returns the evaluated value.
Begin
Create empty stack
While(not end of expr) do
If( element is operand) then
Push element onto stack
Else
Pop two elements, say, a and b. Evaluate
c o a, let value be c, where o is an operator.
Push c on to stack.
End If
End While
Pop the stack and assign c to result.
End
Example
Evaluate the following postfix expression: 8 5 3 + 9 * + 4 +
|
Character Scanned
|
Stack Content
|
|
8
|
8
|
|
5
|
8 5
|
|
3
|
8 5 3
|
|
+
|
8 8
|
|
9
|
8 8 9
|
|
*
|
8 72
|
|
+
|
80
|
|
4
|
80 4
|
|
+
|
84
|
|
|
Result=84
|
|
|
|
