Stacks-and-Queues Stack-ADT Notes | EduRev

: Stacks-and-Queues Stack-ADT Notes | EduRev

 Page 1


1
Stacks and Queues
Sections 3.6 and 3.7
Stack ADT
? Collections:
?Elements of some proper type T
? Operations:
?void push(T t)
?void pop()
?T top()
?bool empty()
?unsigned int size()
?constructor and destructor
Uses of ADT Stack
?Depth first search / backtracking
?Evaluating postfix expressions
?Converting infix to postfix
?Function calls (runtime stack)
?Recursion
Stack Model—LIFO
? Empty stack S
?S.empty() is true
?S.top() not defined
?S.size() == 0
? S.push(“mosquito”)
?S.empty() is false
?S.top() == “mosquito”
?S.size() == 1
? S.push(“?sh”)
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Stack Model—LIFO
?S.push(“raccoon”)
?S.empty() is false
?S.top() ==
“raccoon”
?S.size() == 3
?S.pop()
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Queue ADT - FIFO
? Collection
?Elements of some proper type T
? Operations
?void push(T t)
?void pop()
?T front()
?bool empty()
?unsigned int size()
?Constructors and destructors
Page 2


1
Stacks and Queues
Sections 3.6 and 3.7
Stack ADT
? Collections:
?Elements of some proper type T
? Operations:
?void push(T t)
?void pop()
?T top()
?bool empty()
?unsigned int size()
?constructor and destructor
Uses of ADT Stack
?Depth first search / backtracking
?Evaluating postfix expressions
?Converting infix to postfix
?Function calls (runtime stack)
?Recursion
Stack Model—LIFO
? Empty stack S
?S.empty() is true
?S.top() not defined
?S.size() == 0
? S.push(“mosquito”)
?S.empty() is false
?S.top() == “mosquito”
?S.size() == 1
? S.push(“?sh”)
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Stack Model—LIFO
?S.push(“raccoon”)
?S.empty() is false
?S.top() ==
“raccoon”
?S.size() == 3
?S.pop()
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Queue ADT - FIFO
? Collection
?Elements of some proper type T
? Operations
?void push(T t)
?void pop()
?T front()
?bool empty()
?unsigned int size()
?Constructors and destructors
2
Queue Model—FIFO
? Empty Q
animal_parade_queue
front
back
Queue Model—FIFO
?Q.push( “ant” )
?Q.push( “bee” )
?Q.push( “cat” )
?Q.push( “dog” )
front
back
animal_parade_queue
back back back back
Queue Model—FIFO
? Q.pop();
? Q.pop();
? Q.push( “eel” );
? Q.pop();
? Q.pop();
front
animal_parade_queue
back back back back
Uses of ADT Queue
?Buffers
?Breadth first search
?Simulations
?Producer-Consumer Problems
Depth First Search—Backtracking
? Problem
? Discover a path from start
to goal
? Solution
? Go deep
? If there is an unvisited
neighbor, go there
? Backtrack
? Retreat along the path to
find an unvisited neighbor
? Outcome
? If there is a path from start
to goal, DFS finds one such
path
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
Depth First Search—Backtracking (2)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
Push
Page 3


1
Stacks and Queues
Sections 3.6 and 3.7
Stack ADT
? Collections:
?Elements of some proper type T
? Operations:
?void push(T t)
?void pop()
?T top()
?bool empty()
?unsigned int size()
?constructor and destructor
Uses of ADT Stack
?Depth first search / backtracking
?Evaluating postfix expressions
?Converting infix to postfix
?Function calls (runtime stack)
?Recursion
Stack Model—LIFO
? Empty stack S
?S.empty() is true
?S.top() not defined
?S.size() == 0
? S.push(“mosquito”)
?S.empty() is false
?S.top() == “mosquito”
?S.size() == 1
? S.push(“?sh”)
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Stack Model—LIFO
?S.push(“raccoon”)
?S.empty() is false
?S.top() ==
“raccoon”
?S.size() == 3
?S.pop()
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Queue ADT - FIFO
? Collection
?Elements of some proper type T
? Operations
?void push(T t)
?void pop()
?T front()
?bool empty()
?unsigned int size()
?Constructors and destructors
2
Queue Model—FIFO
? Empty Q
animal_parade_queue
front
back
Queue Model—FIFO
?Q.push( “ant” )
?Q.push( “bee” )
?Q.push( “cat” )
?Q.push( “dog” )
front
back
animal_parade_queue
back back back back
Queue Model—FIFO
? Q.pop();
? Q.pop();
? Q.push( “eel” );
? Q.pop();
? Q.pop();
front
animal_parade_queue
back back back back
Uses of ADT Queue
?Buffers
?Breadth first search
?Simulations
?Producer-Consumer Problems
Depth First Search—Backtracking
? Problem
? Discover a path from start
to goal
? Solution
? Go deep
? If there is an unvisited
neighbor, go there
? Backtrack
? Retreat along the path to
find an unvisited neighbor
? Outcome
? If there is a path from start
to goal, DFS finds one such
path
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
Depth First Search—Backtracking (2)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
Push
3
Depth First Search—Backtracking (3)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
Push
Push
Depth First Search—Backtracking (4)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
Push
Push
Push
Depth First Search—Backtracking (5)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
Push
Push
Push
Push
Depth First Search—Backtracking (6)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
9
Push
Push
Push
Push
Push
Depth First Search—Backtracking (7)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
Push
Push
Push
Push
Pop
Depth First Search—Backtracking (8)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
Push
Push
Push
Pop
Page 4


1
Stacks and Queues
Sections 3.6 and 3.7
Stack ADT
? Collections:
?Elements of some proper type T
? Operations:
?void push(T t)
?void pop()
?T top()
?bool empty()
?unsigned int size()
?constructor and destructor
Uses of ADT Stack
?Depth first search / backtracking
?Evaluating postfix expressions
?Converting infix to postfix
?Function calls (runtime stack)
?Recursion
Stack Model—LIFO
? Empty stack S
?S.empty() is true
?S.top() not defined
?S.size() == 0
? S.push(“mosquito”)
?S.empty() is false
?S.top() == “mosquito”
?S.size() == 1
? S.push(“?sh”)
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Stack Model—LIFO
?S.push(“raccoon”)
?S.empty() is false
?S.top() ==
“raccoon”
?S.size() == 3
?S.pop()
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Queue ADT - FIFO
? Collection
?Elements of some proper type T
? Operations
?void push(T t)
?void pop()
?T front()
?bool empty()
?unsigned int size()
?Constructors and destructors
2
Queue Model—FIFO
? Empty Q
animal_parade_queue
front
back
Queue Model—FIFO
?Q.push( “ant” )
?Q.push( “bee” )
?Q.push( “cat” )
?Q.push( “dog” )
front
back
animal_parade_queue
back back back back
Queue Model—FIFO
? Q.pop();
? Q.pop();
? Q.push( “eel” );
? Q.pop();
? Q.pop();
front
animal_parade_queue
back back back back
Uses of ADT Queue
?Buffers
?Breadth first search
?Simulations
?Producer-Consumer Problems
Depth First Search—Backtracking
? Problem
? Discover a path from start
to goal
? Solution
? Go deep
? If there is an unvisited
neighbor, go there
? Backtrack
? Retreat along the path to
find an unvisited neighbor
? Outcome
? If there is a path from start
to goal, DFS finds one such
path
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
Depth First Search—Backtracking (2)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
Push
3
Depth First Search—Backtracking (3)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
Push
Push
Depth First Search—Backtracking (4)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
Push
Push
Push
Depth First Search—Backtracking (5)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
Push
Push
Push
Push
Depth First Search—Backtracking (6)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
9
Push
Push
Push
Push
Push
Depth First Search—Backtracking (7)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
Push
Push
Push
Push
Pop
Depth First Search—Backtracking (8)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
Push
Push
Push
Pop
4
Depth First Search—Backtracking (9)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
Push
Push
Pop
Depth First Search—Backtracking (10)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
Push
Pop
Depth First Search—Backtracking (11)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
3
Push
Push
Depth First Search—Backtracking (12)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
3
7
Push
Push
Push
Depth First Search—Backtracking (13)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
3
7
10
Push
Push
Push
Push
DFS Implementation
DFS() {
stack<location> S;
// mark the start location as visited
S.push(start);
while (S is not empty) {
t = S.top();
if (t == goal) Success(S);
if (// t has unvisited neighbors) {
// choose an unvisited neighbor n
// mark n visited;
S.push(n);
} else {
BackTrack(S);
}
}
Failure(S);
}
Page 5


1
Stacks and Queues
Sections 3.6 and 3.7
Stack ADT
? Collections:
?Elements of some proper type T
? Operations:
?void push(T t)
?void pop()
?T top()
?bool empty()
?unsigned int size()
?constructor and destructor
Uses of ADT Stack
?Depth first search / backtracking
?Evaluating postfix expressions
?Converting infix to postfix
?Function calls (runtime stack)
?Recursion
Stack Model—LIFO
? Empty stack S
?S.empty() is true
?S.top() not defined
?S.size() == 0
? S.push(“mosquito”)
?S.empty() is false
?S.top() == “mosquito”
?S.size() == 1
? S.push(“?sh”)
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Stack Model—LIFO
?S.push(“raccoon”)
?S.empty() is false
?S.top() ==
“raccoon”
?S.size() == 3
?S.pop()
?S.empty() is false
?S.top() == “?sh”
?S.size() == 2
food chain stack
Queue ADT - FIFO
? Collection
?Elements of some proper type T
? Operations
?void push(T t)
?void pop()
?T front()
?bool empty()
?unsigned int size()
?Constructors and destructors
2
Queue Model—FIFO
? Empty Q
animal_parade_queue
front
back
Queue Model—FIFO
?Q.push( “ant” )
?Q.push( “bee” )
?Q.push( “cat” )
?Q.push( “dog” )
front
back
animal_parade_queue
back back back back
Queue Model—FIFO
? Q.pop();
? Q.pop();
? Q.push( “eel” );
? Q.pop();
? Q.pop();
front
animal_parade_queue
back back back back
Uses of ADT Queue
?Buffers
?Breadth first search
?Simulations
?Producer-Consumer Problems
Depth First Search—Backtracking
? Problem
? Discover a path from start
to goal
? Solution
? Go deep
? If there is an unvisited
neighbor, go there
? Backtrack
? Retreat along the path to
find an unvisited neighbor
? Outcome
? If there is a path from start
to goal, DFS finds one such
path
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
Depth First Search—Backtracking (2)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
Push
3
Depth First Search—Backtracking (3)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
Push
Push
Depth First Search—Backtracking (4)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
Push
Push
Push
Depth First Search—Backtracking (5)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
Push
Push
Push
Push
Depth First Search—Backtracking (6)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
9
Push
Push
Push
Push
Push
Depth First Search—Backtracking (7)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
6
Push
Push
Push
Push
Pop
Depth First Search—Backtracking (8)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
5
Push
Push
Push
Pop
4
Depth First Search—Backtracking (9)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
2
Push
Push
Pop
Depth First Search—Backtracking (10)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
Push
Pop
Depth First Search—Backtracking (11)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
3
Push
Push
Depth First Search—Backtracking (12)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
3
7
Push
Push
Push
Depth First Search—Backtracking (13)
? Stack
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
3
7
10
Push
Push
Push
Push
DFS Implementation
DFS() {
stack<location> S;
// mark the start location as visited
S.push(start);
while (S is not empty) {
t = S.top();
if (t == goal) Success(S);
if (// t has unvisited neighbors) {
// choose an unvisited neighbor n
// mark n visited;
S.push(n);
} else {
BackTrack(S);
}
}
Failure(S);
}
5
DFS Implementation (2)
BackTrack(S) {
while (!S.empty() && S.top() has no unvisited neighbors) {
S.pop();
}
}
Success(S) {
// print success
while (!S.empty()) {
output(S.top());
S.pop();
}
}
Failure(S) {
// print failure
while (!S.empty()) {
S.pop();
}
}
Breadth First Search
? Problem
?Find a shortest path from start to goal
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
Breadth First Search (2)
? Queue
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
1
push
Breadth First Search (3)
? Queue
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
pop
Breadth First Search (4)
? Queue
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
4 3 2
pop pop pop
Breadth First Search (5)
? Queue
1
2 3 4
5 6 8 7
9 10 12 11
start
goal
pop
4 3
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!