Transcript Stacks

Stacks
• Objective
After this lecture you will be able to:
• Describe a stack
• Describe the representation of stack using linear
array
• Describe the representation of stack using linear
linked list
• Implementation of various operations on stack
• Describe some applications of stacks
Stack
• Stack is one of the commonly used data
structures.
• Stack is also called last in first out (LIFO)
system
• Stack is a linear list in which insertion and
deletion can take place only at one end
called top.
• This structure operates in much the same
way as stack of trays.
Stack of Trays
•The following figure illustrate a stack, which can
accommodate maximum of 10 elements
figure shows stack after pushing elements 8,10,12,-5,6
9
8
7
6
5
top
4
6
3
-5
2
12
1
10
0
8
Stack after popping top two
elements
9
8
7
6
5
4
3
top
2
12
1
10
0
8
stack after pushing elements 8,10,12,-5,6,9,55
9
8
7
top
6
55
5
9
4
6
3
-5
2
12
1
10
0
8
Operations on stacks
• Createstack(s)—to create s as an empty stack
• Push(s,i)--to push elementi onto stack s.
• Pop(s)—to access and remove the top element
of the stack s
• Peek(s)—to access the top element of the
stacks without removing it from the stack s.
• Isfull(s)—to check whether the stack s is full
• isempty—to check whether the stack s is
empty
Representation of stack in
memory
• Representation of stack using array:
Suppose elements of the stack are integer type and stack can
store maximum 10 elements..
#define MAX 10
typedef struct
{
int top;
int elements[MAX];
}stack;
stack s;
• Here we have defined our own data type named stack.
• First element top will be used to index top element
• Array elements hold the elements of the stack
• Last line declares variable s of type stack
stack
• In addition to the previous declaration, we
will use the declaration
typedef enum {false, true } Boolean;
This statement defined new data type
named Boolean which can take value false
or true.
Representation of stack in memory
0
4
8
1
2
3
4
10 12 -5
6
5
6
7
8
9
top
0
2
8
1
2
3
4
5
6
7
8
9
3
4
5
6
7
8
9
10 12 -5
6
10 12
top
0
6
top
8
1
2
9
55
Creating an empty stack
• Before we can use a stack, it is to be initialized.
• As the index of array elements can take any value in the
range 0 to MAX-1, the purpose of initializing the stack is
served by assigning value -1 to the top of variable.
• This simple task can be accomplished by the following
function.
Void createstack( stack *ps)
{
ps=-1;
}
Testing stack for underflow
Boolean isempty(stack *ps)
{
if(ps->top==-1)
return true;
else
return false;
}
or
Boolean is empty(stack *ps)
{
return ((ps->top==-1)?true:false);
}
Testing stack for overflow
Boolean isfull(stack *ps)
{
if(ps->top==MAX-1)
return true;
else
return false;
}
or
Boolean is empty(stack *ps)
{
return ((ps->top==MAX-1)?true:false);
}
Push Operation
Before the push operation, if the stack is empty, then the
value of the top will be -1and if the stack is not empty
then the value of the top will be the index of the element
currently on the top.
Therefore we place the value onto the stack, the value of
top is incremented so that it points to the new top of
stack, where incoming element is placed.
Void push(stack *ps, int value)
{
ps->top++;
ps->elements[ps->top]=value;
}
Pop Operation
The element on the top of the stack is assigned to a local variable,
which later on will be returned via the return statement.
After assigning the top element to a local variable, the variable top is
decremented so that it points to a new top
Int pop(stack *ps)
{
int temp;
temp=ps->elements[ps->top];
ps->top--;
return temp;
}
Accessing top element
There may be instances where we want to
access the top element of the stack
without removing it from the stack.
Int peek( stack *ps)
{
return(ps->elements[ps->top]);
}
Representing a stack using a linked
list
A stack represented using a linked list is also known as
linked stack.
The array based representation of stack suffers from
following limitations.
• Size of the stack must be known in advance
• We may come across situation when an attempt to push
an element causes overflow.
However stack is an abstract data structure can not be full.
Hence, abstractly, it is always possible to push an
element onto stack. Therefore stack as an array prohibits
the growth of the stack beyond the finite number of
elements.
Declaration of stack
The linked list representation allows a stack to grow to a
limit of the computer’s memory.
Typedef struct nodetype
{
int info;
struct nodetype *next;
}stack;
Stack *top;
Here I have defined my own data type named stack,
which is a self referential structure and whose first
element info hold the element of the stack and the
second element next hold the address of the element
under it in the stack.
The last line declares a pointer variable top of type
stack.
Representation of stack in memory
top
6
-5
12
10
8
X
top
6
-5
12
X
top
55
9
6
-5
12
10
8
X
Creating an empty stack
Before we can use a stack, it is to be initialized.
To initialize a stack, we will create an empty
linked list.
The empty linked list is created by setting pointer
variable top to value NULL.
Void createstack(stack **top)
{
*top=NULL;
}
Testing stack for underflow
Boolean isempty(stack *top)
{
if(top==NULL)
return true;
else
return false;
}
or
Boolean is empty(stack *top)
{
return ((top==NULL)?true:false);
}
Testing stack for overflow
Since stack represented using a linked list
can grow to a limit of computers memory,
there overflow condition never occurs.
Hence this operation is not implemented
for linked list.
Push operation
To push a new element onto the stack, the element is inserted in
the beginning of the linked list.
void push(stack **top, int value)
{
stack *ptr;
ptr=(stack*)malloc(sizeof(stack));
if(ptr==NULL)
{
printf(“\n unable to allocate memory for new node…”);
printf(“\npress any key to exit..”);
getch();
return;
}
ptr->info=value;
ptr->next=*top;
*top=ptr;
}
Pop operation
To pop an element from the stack, the element is removed
from the beginning of the linked list.
Int pop(stack **top)
{
int temp;
stack *ptr;
temp=(*top)->info;
ptr=*top;
*top=(*top)->next;
free(ptr);
return temp;
}
Accessing top element
Int peek(stack *top)
{
return(top->info)
}
Dispose a stack
Because the stack is implemented using linked lists,
therefore it is programmers job to write the code to
release the memory occupied by the stack.
Void disposestack(stack **top)
{
stack *ptr;
while(*top!=NULL)
{
ptr=*top;
*top=(*top)->next;
free(ptr);
}
}
Applications of Stacks
•
Stacks are used to pass parameters between
functions. On a call to function, parameter and local
variables are stored on stack.
• High level programming languages, such as Pascal
c etc. that provide support for recursion use stack
for book keeping. In each recursive call, there is
need to save the current values of parameters, local
variables and the return address.
In addition to above stack are used to solve the various
problems….
1. Parenthesis checker
2. Mathematical notation translation
1. Polish (prefix) notation
2. Reverse polish (postfix) Notation
3. Quick sort algorithm
Parenthesis checker
• Parenthesis checker is a program that checks
whether a mathematical expression is properly
parenthesized.
• We will consider three sets of grouping symbols:
– The standard parenthesis ”( )”
– The braces “{ }”
– the brackets “[ ]”
For an input expression, it verifies that for each left
parenthesis, braces or racket, there is a corresponding
closing symbol and the symbols are appropriately nested.
Examples of valid inputs
Valid Input
invalid Input
()
[(( )
( { } [ ])
( { } [ ]))
({[][]})
(( { [ ] [ ] } )
[ { { { } ( )} [ ] } [ ] ( ) { } ]
([ { { { } ( )} [ ] } }[ ] ( ) { } ]
Inside parenthesis there can be any valid arithmetic expression.
Parenthesis Checker Algo
parenthesisChecker(exp)
Begin
Read: exp
Create empty stack
For each character c in exp
if(current character is left symbol) then
push the character onto stack
else if(current character is right symbol) then
if(stack is empty) then
print: “Error No matching open symbol”
exit
else
pop a symbol s from the stack
if( s doesn’t correspond to c) then
print: “Error incorrect nesting of symbol”
exit
endif
endif
endif
Endfor
If(stack is not empty) then
print:”Error missing closing symbol”
Else
print: input expression is ok”
End
Mathematical notation
Translation
Symbol used
Precedence
* (asterisk)
Operation
performed
Multiplication
/ (slash)
Division
Highest
% (percentage) Modulus
Highest
+ (plus)
Addition
Lowest
- (hyphen)
subtraction
lowest
Highest
Infix notation
In this notation, the operator symbol is placed
between its two operands.
• To add A to B we can write as A+B or B+A
• To subtract D from C we write as C-D, but we
can not write D-C as this operation is not
commutative.
In this notation we must distinguish between
(A+B)/C and A+(B/C)
Polish (prefix) notation
In this notation, named after the polish
mathematician Jan Lukasiewiez, the operator
symbol is placed before its two operands.
• To add A to B we write as +AB or +BA
• To subtract D from C we have to writ as –CD
not as -DC
Infix to polish notation
In order to translate an arithmetic expression in infix notation to
polish notation, we do step by step using rackets ([]) to indicate
the partial translations.
• Consider the following expression in infix notation:
(A-B/C)*(A*K-L)
The partial translation may look like:
(A-[/BC])*([*AK]-L)
[-A/BC]*[-*AKL]
*-A/BC-*AKL
The fundamental property of polish notation is that the order in
which the operations to perform is completely determined by
the position of the operators and operands in the expression.
Accordingly one never needs parenthesis when writing expression
in polish notation.
Reverse Polish (Postfix) Notation
In this notation the operator symbol is placed
after its two operands.
• To add A to B we can write as AB+ or BA+
• To subtract D from C we have to write as CDnot as DC-.
Infix to reverse polish
notation
Consider the following expression in infix
notation:
(A-B/C)*(A/K-L)
The partial translation may look like:]
(A-[BC/])*([AK/]-L)
[ABC/-]*[AK/L-]
ABC/-AK/L-*
Evaluating Mathematical
Expressions
Generally we use infix notation, where one can not tell the
order in which the operator should be applied by looking
at the expression.
The expression in postfix notation is very easy to evaluate,
as the operands appear before the operator, there is no
need of operator precedence or parentheses for
operation.
In order to evaluate a postfix expression it is scanned from
left to right.
As operands are encountered, they are pushed on a stack.
When an operator encountered, pop top one or two
operands depending on the operator, perform the
operation and place the result back on the stack.
Infix to postfix procedure
Consider the following infix expression q:
(7-5)*(9/2)
Character scanned
stack
Expression p
(
(
7
(
7
-
(-
7
5
(-
75
)
empty
75-
*
*
75-
(
*(
75-
9
*(
75–9
/
*(/
75–9
2
*(/
75–92
)
*
75–92/
End of expression
Empty
75–92/*
Evaluating expression in postfix
notation
Evaluate postfixnotation(p,result)
Begin
Create empty stack
while(not end of exp p) do
if(element is operand) then
push element onto stack
else
pop two elements and let first one is a
and the second one is b
evalute b@a, let its value be c, where @ is
operator
push c onto stack
endif
endwhile
pop stack and assign this value to parameter result
end
Evaluating expression in postfix
notation
Consider the following postfix expression p:
75–92/*
Character Scanned
Stack
7
7
5
75
-
2
9
29
2
292
/
2 4.5
*
9
End of expression
9
Additional Notes
• Stacks structures are usually implemented
using arrays or linked lists.
• For both implementations, the running
time is O(n).
• We will be examining common Stack
Applications.
Stack Applications
•
Reversing Data: We can use stacks to reverse data.
(example: files, strings)
Very useful for finding palindromes.
Consider the following pseudocode:
1) read (data)
2) loop (data not EOF and stack not full)
1) push (data)
2) read (data)
3) Loop (while stack notEmpty)
1) pop (data)
2) print (data)
Stack Applications
•
Converting Decimal to Binary: Consider the following pseudocode
1)
2)
Read (number)
Loop (number > 0)
1) digit = number modulo 2
2) print (digit)
3) number = number / 2
// from Data Structures by Gilbert and Forouzan
The problem with this code is that it will print the binary
number backwards. (ex: 19 becomes 11001000 instead of 00010011. )
To remedy this problem, instead of printing the digit right away, we can
push it onto the stack. Then after the number is done being converted, we
pop the digit out of the stack and print it.
Stack Applications
• Postponement: Evaluating arithmetic expressions.
• Prefix: + a b
• Infix:
a + b (what we use in grammar school)
• Postfix: a b +
• In high level languages, infix notation cannot be used to
evaluate expressions. We must analyze the expression
to determine the order in which we evaluate it. A
common technique is to convert a infix notation into
postfix notation, then evaluating it.
Infix to Postfix Conversion
• Rules:
– Operands immediately go directly to output
– Operators are pushed into the stack (including parenthesis)
- Check to see if stack top operator is less than current operator
- If the top operator is less than, push the current operator onto stack
- If the top operator is greater than the current, pop top operator and
push onto stack, push current operator onto stack
- Priority 2: * /
- Priority 1: + - Priority 0: (
If we encounter a right parenthesis, pop from stack until we get
matching left parenthesis. Do not output parenthesis.
Infix to Postfix Example
A + B * C - D / E
Infix
Postfix
a) A + B * C b)
+ B * C c)
B * C d)
* C e)
C f)
g)
h)
i)
j)
k)
Stack(bot->top)
D
D
D
D
D
D
D
/
/
/
/
/
/
/
/
E
E
E
E
E
E
E
E
E
A
+
+
+
+
+
+
+
+ - /
*
*
- /
A
A B
A B
A B C
A B C *
A B C * D
A B C * D
A B C * D E
A B C * D E / - +
Infix to Postfix Example #2
A * B - ( C + D ) + E
Infix
a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
k)
l)
m)
n)
o)
A * B * B B -
C
C D
C D +
C D + C D + +
(
(
(
(
(
(
C
C
C
C
C
C
C
+
+
+
+
+
+
+
D
D
D
D
D
D
D
D
D
)
)
)
)
)
)
)
)
)
+
+
+
+
+
+
+
+
+
E
E
E
E
E
E
E
E
E
Stack(bot->top)
Postfix
empty
empty
*
*
empty
- (
- (
empty
A
A
A B
A B *
A B *
A B *
A B * C
- ( +
A B *
- ( +
A B *
+ E
-
A B *
+ E
empty
A B *
+
A B *
) + E
E
+
empty
A B * C D + - E
A B * C D + - E
Postfix Evaluation
Operand: push
Operator: pop 2 operands, do the math, pop result
back onto stack
1 2 3 + *
Postfix
a) 1 2
b)
2
c)
d)
e)
f)
1 *
Stack( bot -> top )
3 + *
3 + *
3 + *
+ *
*
5
1
1 2
1 2 3
1 5
// 5 from 2 + 3
5
// 5 from
Backtracking
• Stacks can be used to backtrack to
achieve certain goals.
• Usually, we set up backtrack tokens to
indicate a backtrack opportunity.
References
• Our class textbook
• Data Structures: A Pseudocode Apporoach with C. Gilberg, Richard
F., Forouzan, Behrouz A.. PWS Publishing Company: 1998
Token Operator
Precedence1 Associativity
()
[]
-> .
-- ++
function call
17
array element
struct or union member
increment, decrement2 16
left-to-right
-- ++
!
-+
&*
sizeof
(type)
decrement, increment3
logical not
one’s complement
unary minus or plus
address or indirection
size (in bytes)
type cast
15
right-to-left
14
right-to-left
*/%
mutiplicative
13
Left-to-right
left-to-right
+-
binary add or subtract
12
left-to-right
<< >> shift
11
left-to-right
> >=
< <=
== !=
relational
10
left-to-right
equality
9
left-to-right
&
bitwise and
8
left-to-right
^
bitwise exclusive or
7
left-to-right
bitwise or
6
left-to-right
&&
logical and
5
left-to-right

logical or
4
left-to-right
?:
conditional
3
right-to-left
= += -= assignment
/= *= %=
<<= >>=
&= ^= 
=
2
right-to-left
,
1
left-to-right
comma
user
compiler
Infix
Postfix
2+3*4
a*b+5
(1+2)*7
a*b/c
(a/(b-c+d))*(e-a)*c
a/b-c+d*e-a*c
234*+
ab*5+
12+7*
ab*c/
abc-d+/ea-*c*
ab/c-de*ac*-
Postfix: no parentheses, no precedence
Token
6
2
/
3
4
2
*
+
Stack
[1]
[0]
6
6
6/2
6/2
6/2-3
6/2-3
6/2-3
6/2-3
6/2-3+4*2
2
3
4
4
4*2
Top
[2]
0
1
0
1
0
1
2 2
1
0
Infix to Postfix
Assumptions:
operators: +, -, *, /, %
operands: single digit integer
#define MAX_STACK_SIZE 100 /* maximum stack size */
#define MAX_EXPR_SIZE 100 /* max size of expression */
typedef enum{lparan, rparen, plus, minus, times, divide,
mod, eos, operand} precedence;
int stack[MAX_STACK_SIZE]; /* global stack */
char expr[MAX_EXPR_SIZE]; /* input string */
Evaluation of Postfix Expressions
int eval(void)
{
/* evaluate a postfix expression, expr, maintained as a
global variable, ‘\0’ is the the end of the expression.
The stack and top of the stack are global variables.
get_token is used to return the token type and
the character symbol. Operands are assumed to be single
character digits */
precedence token;
char symbol;
int op1, op2;
int n = 0; /* counter for the expression string */
int top = -1;
token = get_token(&symbol, &n);
while (token != eos) {
if (token == operand)
push(&top, symbol-’0’); /* stack insert */
else { /* remove two operands, perform operation, and
return result to the stack */
op2 = pop(&top); /* stack delete */
op1 = pop(&top);
switch(token) {
case plus: push(&top, op1+op2); break;
case minus: push(&top, op1-op2); break;
case times: push(&top, op1*op2); break;
case divide: push(&top, op1/op2); break;
case mod: push(&top, op1%op2);
}
}
token = get_token (&symbol, &n);
}
return pop(&top); /* return result */
}
precedence get_token(char *symbol, int *n)
{
/* get the next token, symbol is the character
representation, which is returned, the token is
represented by its enumerated value, which
is returned in the function name */
*symbol =expr[(*n)++];
switch (*symbol) {
case ‘(‘ : return lparen;
case ’)’ : return rparen;
case ‘+’: return plus;
case ‘-’ : return minus;
case ‘/’ : return divide;
case ‘*’ : return times;
case ‘%’ : return mod;
case ‘\0‘ : return eos;
default : return operand;
/* no error checking, default is operand */
}
}
Infix to Postfix Conversion
(Intuitive Algorithm)
(1)
Fully parenthesized expression
a / b - c + d * e - a * c -->
((((a / b) - c) + (d * e)) – (a * c))
(2)
All operators replace their corresponding right
parentheses.
((((a / b) - c) + (d * e)) – (a * c))
(3)
/
-
Delete all parentheses.
ab/c-de*+ac*two passes
+
*
-*
The orders of operands in infix and postfix are the same.
a + b * c, * > +
Token
a
+
b
*
c
eos
Stack
[0] [1] [2]
+
+
+
+
*
*
Top
-1
0
0
1
1
-1
Output
a
a
ab
ab
abc
abc*=
Rules
(1)
Operators are taken out of the stack as long as their
in-stack precedence is higher than or equal to the
incoming precedence of the new operator.
(2)
( has low in-stack precedence, and high incoming
precedence.
isp
icp
(
0
20
)
19
19
+
12
12
12
12
*
13
13
/
13
13
%
13
13
eos
0
0
precedence stack[MAX_STACK_SIZE];
/* isp and icp arrays -- index is value of precedence
lparen, rparen, plus, minus, times, divide, mod, eos */
static int isp [ ] = {0, 19, 12, 12, 13, 13, 13, 0};
static int icp [ ] = {20, 19, 12, 12, 13, 13, 13, 0};
isp: in-stack precedence
icp: incoming precedence
Infix to Postfix
void postfix(void)
{
/* output the postfix of the expression. The expression
string, the stack, and top are global */
char symbol;
precedence token;
int n = 0;
int top = 0; /* place eos on stack */
stack[0] = eos;
for (token = get _token(&symbol, &n); token != eos;
token = get_token(&symbol, &n)) {
if (token == operand)
printf (“%c”, symbol);
else if (token == rparen ){
Infix to Postfix (cont’d)
/*unstack tokens until left parenthesis */
while (stack[top] != lparen)
print_token(delete(&top));
pop(&top); /*discard the left parenthesis */
}
else{
/* remove and print symbols whose isp is greater
than or equal to the current token’s icp */
while(isp[stack[top]] >= icp[token] )
print_token(delete(&top));
push(&top, token);
}
}
while ((token = pop(&top)) != eos)
print_token(token);
print(“\n”);
}