09.2 Stack

Data Structures and Algorithms
Objectives
In this session, you will learn to:

Identify the features of a stack
Implement stacks
Apply stacks to solve programming problems
VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Ver. 1.0 SACHIN BHARDWAJ, PGT(CS), KV NO.1 TEZPUR Session 10
Stacks
Let us play the game of Rummy.
7 7
7 7
6 6
6 6
6 6
6 6
7 7
7 7
6 6
6 6
6 6
6 6

Defining a Stack
What
A is is
stack a Stack ?
a collection of data items that can be accessed at
only one end, called top.
Items can be inserted and deleted in a stack only at the top.
The last item inserted in a stack is the first one to be
deleted.
Therefore, a stack is called a Last-In-First-Out (LIFO) data
structure.

Identifying the Operations on Stacks
PUSH:are
There It istwo
thebasic
process
operations
of inserting
that aare
newperformed
element on the
stacks:
top of a stack.
PUSH
POP
Push an
Element 1
Empty Stack

Identifying the Operations on Stacks (Contd.)
PUSH: It is the process of inserting a new element on the

top of a stack.
Push an
Push an
Element 32
Element
3
2
1

Identifying the Operations on Stacks (Contd.)
POP: It is the process of deleting an element from the top of

a stack.
POP an
Element
3
3 2
2
1

Just a minute
Elements in stacks are inserted and deleted on a

___________ basis.
Answer:
LIFO

Just a minute
List down some real life examples that work on the LIFO
principle.
Answer:
Pile of books: Suppose a set of books are placed one over
the other in a pile. When you remove books from the pile, the
topmost book will be removed first. Similarly, when you have
to add a book to the pile, the book will be placed at the top of
the pile.
Pile of plates: The first plate begins the pile. The second plate
is placed on the top of the first plate and the third plate is
placed on the top of the second plate, and so on. In general, if
you want to add a plate to the pile, you can keep it on the top
of the pile. Similarly, if you want to remove a plate, you can
remove the plate from the top of the pile.
Bangles in a hand: When a person wears bangles, the last
bangle worn is the first one to be removed.
Implementing Stacks
You need to develop a method to check if the parentheses

in an arithmetic expression are correctly nested.
How will you solve this problem?
You can solve this problem easily by using a stack.

Implementing Stacks (Contd.)
{(a + b) × (c + d) + (c × d)]}
Consider an example.
Suppose the expression is:
{(a + b) × (c + d) + (c × d)]}
Scan the expression from
left to right.
The first entry to be
scanned is ‘{’, which is a left
parenthesis.
Push it into the stack.
{

{(a + b) × (c + d) + (c × d)]}
The next entry to be
scanned is ‘(’, which is a left
parenthesis.
The next entry is ‘a’, which
is an operand. Therefore, it
is discarded.
The next entry is ‘+’, which
is an operator. Therefore, it
is discarded. (
The next entry is ‘b’, which {
is an operand. Therefore, it
is discarded.

{(a + b) × (c + d) + (c × d)]}
scanned is ‘)’, which is a
right parenthesis
POP the topmost entry from
the stack.
Match the two brackets.
( )
Brackets Matched
(
{

The next entry to be scanned

{(a + b) × (c + d) + (c × d)]}
is ‘×’, which is an operator.
Therefore, it is discarded.
is ‘(’, which is a left
parenthesis
Push it into the stack
is ‘c’, which is an operand.
Therefore it is discarded
The next entry to be scanned (
is ‘+’, which is an operator. {
is ‘d’, which is an operand.
{(a + b) × (c + d) + (c × d)]}
right parenthesis.
POP the topmost element
from the stack.
( )
Brackets Matched
(
{


{(a + b) × (c + d) + (c × d)]}
is ‘+’, which is an operator.
is ‘(’, which is a left
parenthesis.
is ‘c’, which is an operand.
The next entry to be scanned (
is ‘×’, which is an operator. {
is ‘d’, which is an operand.
{(a + b) × (c + d) + (c × d)]}
right parenthesis.
from the stack.
( )
Brackets Matched
(
{

{(a + b) × (c + d) + (c × d)]}
scanned is ‘]’, which is a
right parenthesis.
from the stack.
{ ]
Brackets Do Not Match

The Expression is INVALID

Just a minute
In a stack, data can be stored and removed only from one

end of the stack called the ______ of the stack.
Answer:
top

Applications of Stacks
Some of the applications of stacks are:

Implementing function calls
Maintaining the UNDO list for an application
Checking the nesting of parentheses in an expression
Evaluating expressions

Implementing Function Calls
Implementing function calls:

Consider an example. There are three functions, F1, F2, and
F3. Function F1 invokes F2 and function F2 invokes F3, as
shown.

Implementing Function Calls (Contd.)
void F1()
Assuming these instructions at the
{
given locations in the memory.
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5;
1121 F3(x);
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1()
{ The execution starts from
1100 int x; function F1
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5;
1121 F3(x);
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1()
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5;
1121 F3(x);
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1() x=5
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5;
1121 F3(x);
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1() x=5
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5;
1121 F3(x); 1103, x = 5
1122 print(x);
}
Address and the local variable of F1
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1() x=5
10
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5;
1121 F3(x); 1103, x = 5
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1() x = 10
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5; 1122, x = 10
1121 F3(x); 1103, x = 5
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1() 20
x = 10
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5; 1122, x = 10
1121 F3(x); 1103, x = 5
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141
}
void F1() 20
x = 10
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x) 1122, x = 10
{
1120 x = x + 5; 1122, x = 10
1121 F3(x); 1103, x = 5
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141 20
}
void F1() 5
x = 10
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x) 1103, x = 5
{
1120 x = x + 5;
1121 F3(x); 1103, x = 5
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141 20 10
}
void F1() x=5
{
1100 int x;
1101 x = 5;
1102 F2();
1103 print(x);
}
void F2(int x)
{
1120 x = x + 5;
1121 F3(x);
1122 print(x);
}
void F3(int x)
{
1140 x = x × 2;
print x;
1141 20 10 5
}
Maintaining the UNDO list for an Application
Maintaining the UNDO list for an application:

Consider that you made some changes in a Word document.
Now, you want to revert back those changes. You can revert
those changes with the help of an UNDO feature.
The UNDO feature reverts the changes in a LIFO manner.
This means that the change that was made last is the first one
to be reverted.
You can implement the UNDO list by using a stack.

Checking the Nesting of Parentheses in an Expression
Checking the nesting of parentheses in an expression:

You can do this by checking the following two conditions:
The number of left parenthesis should be equal to the number of
right parenthesis.
Each right parenthesis is preceded by a matching left
parenthesis.

Evaluating Expressions
Evaluating an expression by using stacks:

Stacks can be used to solve complex arithmetic expressions.
The evaluation of an expression is done in two steps:
Conversion of the infix expression into a postfix expression.
Evaluation of the postfix expression.

Activity: Implementing a Stack using a Linked List
Problem Statement:
Write a program that accepts an infix expression, and then
converts it into a postfix expression. You can assume that the
entered expression is a valid infix expression.


09.2 Stack

Uploaded by

Copyright:

Available Formats

09.2 Stack

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

09.2 Stack

Uploaded by

Copyright:

Available Formats

Data Structures and Algorithms

In this session, you will learn to:

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Let us play the game of Rummy.

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

PUSH: It is the process of inserting a new element on the

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

POP: It is the process of deleting an element from the top of

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Elements in stacks are inserted and deleted on a

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

You need to develop a method to check if the parentheses

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

The next entry to be scanned

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

The next entry to be scanned

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Brackets Do Not Match

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

In a stack, data can be stored and removed only from one

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Some of the applications of stacks are:

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Implementing function calls:

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Maintaining the UNDO list for an application:

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Checking the nesting of parentheses in an expression:

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

Evaluating an expression by using stacks:

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

VINOD KUMAR VERMA, PGT(CS), KV OEF KANPUR &

You might also like