Transcript ppt

Chapter 7
Stacks
Data Structures Using C++
1
Chapter Objectives
•
•
•
•
•
•
•
Learn about stacks
Examine various stack operations
Learn how to implement a stack as an array
Learn how to implement a stack as a linked list
Discover stack applications
Learn to use a stack to remove recursion
Become aware of the STL class stack
Data Structures Using C++
2
Stacks
• Definition: list of homogeneous elements,
wherein the addition and deletion of
elements occur only at one end, called the
top of the stack
• Last In First Out (LIFO) data structure
• Used to implement function calls
• Used to convert recursive algorithms
(especially not tail recursive) into
nonrecursive algorithms
Data Structures Using C++
3
Various Types of Stacks
Data Structures Using C++
4
LIFO
• Last In First Out (LIFO) data structure
– Top element of stack is last element to be added
to stack
– Elements added and removed from one end
(top)
– Item added last are removed first
Data Structures Using C++
5
Empty Stack
Data Structures Using C++
6
Stack Operations
Data Structures Using C++
7
Basic Operations on a Stack
• initializeStack: Initializes the stack to an
empty state
• destroyStack: Removes all the elements
from the stack, leaving the stack empty
• isEmptyStack: Checks whether the stack is
empty. If empty, it returns true; otherwise, it
returns false
Data Structures Using C++
8
Basic Operations on a Stack
• isFullStack: Checks whether the stack is full. If
full, it returns true; otherwise, it returns false
• push:
– Add new element to the top of the stack
– The input consists of the stack and the new element.
– Prior to this operation, the stack must exist and must
not be full
Data Structures Using C++
9
Basic Operations on a Stack
• top: Returns the top element of the stack.
Prior to this operation, the stack must exist
and must not be empty.
• pop: Removes the top element of the stack.
Prior to this operation, the stack must exist
and must not be empty.
Data Structures Using C++
10
Example of a Stack
Data Structures Using C++
11
Empty Stack
Data Structures Using C++
12
initializeStack and destroyStack
template<class Type>
void stackType<Type>::initializeStack()
{
stackTop = 0;
}//end initializeStack
template<class Type>
void stackType<Type>::destroyStack()
{
stackTop = 0;
}//end destroyStack
Data Structures Using C++
13
emptyStack and fullStack
template<class Type>
bool stackType<Type>::isEmptyStack()
{
return(stackTop == 0);
}//end isEmptyStack
template<class Type>
bool stackType<Type>::isFullStack()
{
return(stackTop == maxStackSize);
}//end isFullStack
Data Structures Using C++
14
Push
Data Structures Using C++
15
Push
template<class Type>
void stackType<Type>::push(const Type& newItem)
{
if(!isFullStack())
{
list[stackTop] = newItem;
//add newItem at the top
//of the stack
stackTop++;
//increment stackTop
}
else
cerr<<"Cannot add to a full stack."<<endl;
}//end push
Data Structures Using C++
16
Return Top Element
template<class Type>
Type stackType<Type>::top()
{
assert(stackTop != 0);
return list[stackTop - 1];
//if the stack is empty,
//terminate the program
//return the element of the
//stack indicated by
//stackTop - 1
}//end top
Data Structures Using C++
17
Pop
template<class Type>
void stackType<Type>::pop()
{
if(!isEmptyStack())
stackTop-;
//decrement stackTop
else
cerr<<"Cannot remove from an empty stack."<<endl;
}//end pop
Data Structures Using C++
18
Pop
Data Structures Using C++
19
copyStack
template<class Type>
void stackType<Type>::copyStack(const stackType<Type>& otherStack)
{
delete [] list;
maxStackSize = otherStack.maxStackSize;
stackTop = otherStack.stackTop;
list = new Type[maxStackSize];
assert(list != NULL);
//copy otherStack into this stack
for(int j = 0; j < stackTop; j++)
list[j] = otherStack.list[j];
}//end copyStack
Data Structures Using C++
20
Copy Constructor
template<class Type>
stackType<Type>::stackType(const stackType<Type>& otherStack)
{
list = NULL;
copyStack(otherStack);
}//end copy constructor
Data Structures Using C++
21
Overloading the Assignment
Operator (=)
template<class Type>
const stackType<Type>& stackType<Type>::operator=
(const stackType<Type>& otherStack)
{
if(this != &otherStack) //avoid self-copy
copyStack(otherStack);
return *this;
}//end operator=
Data Structures Using C++
22
Time-Complexity of Operations
of class stackType
Data Structures Using C++
23
Stack Header File
//Header file: myStack.h
#ifndef H_StackType
#define H_StackType
#include <iostream>
#include <cassert>
using namespace std;
//Place the definition of the class template stackType, as given
//previously in this chapter, here.
//Place the definitions of the member functions, as discussed in
//this chapter, here.
#endif
Data Structures Using C++
24
Programming Example: Highest
GPA
Input The program reads an input file consisting of each
student’s GPA, followed by the student’s name. Sample
data is:
3.8
3.6
3.9
3.7
3.4
3.9
3.4
Lisa
John
Susan
Kathy
Jason
David
Jack
Data Structures Using C++
25
Programming Example: Highest
GPA (Algorithm)
1.
2.
3.
4.
Declare the variables.
Open the input file.
If the input file does not exist, exit the program.
Set the output of the floating-point numbers to a
fixed decimal format with a decimal point and
trailing zeroes. Also, set the precision to two
decimal places.
5. Read the GPA and student name.
6. highestGPA = GPA;
7. Initialize the stack.
Data Structures Using C++
26
Programming Example: Highest
GPA (Algorithm)
8. while (not end of file)
{
8.1 if (GPA > highestGPA)
{
8.1.1 destroyStack(stack);
8.1.2 push(stack, student name);
8.1.3 highestGPA = GPA;
}
8.2 else
if(GPA is equal to highestGPA)
push(stack, student name);
8.3 Read the GPA and student name;
}
Data Structures Using C++
27
Programming Example: Highest
GPA (Algorithm)
9. Output the highest GPA.
10. Output the names of the students having the highest
GPA.
Data Structures Using C++
28
Programming Example: Highest
GPA (Sample Run)
Input File (Ch7_HighestGPAData.txt)
3.4
3.2
2.5
3.4
3.8
3.8
3.6
3.5
3.8
3.7
3.9
3.8
3.9
2.7
3.9
3.4
Holt
Bolt
Colt
Tom
Ron
Mickey
Pluto
Donald
Cindy
Dome
Andy
Fox
Minnie
Goofy
Doc
Danny
Data Structures Using C++
29
Programming Example: Highest
GPA (Sample Run)
Output
Highest GPA = 3.90
The students holding the highest GPA are:
Doc
Minnie
Andy
Data Structures Using C++
30
Empty and Nonempty
Linked Stack
Empty linked stack
Nonempty linked stack
Data Structures Using C++
31
Default Constructor
template<class Type> //default constructor
linkedStackType<Type>::linkedStackType()
{
stackTop = NULL;
}
Data Structures Using C++
32
Destroy Stack
template<class Type>
void linkedStackType<Type>::destroyStack()
{
nodeType<Type> *temp;
//pointer to delete the node
while(stackTop != NULL)
//while there are elements
//in the stack
{
temp = stackTop;
//set temp to point to
//the current node
stackTop = stackTop->link; //advance stackTop
//to the next node
delete temp;
//deallocate the memory
//occupied by temp
}
}//end destroyStack
Data Structures Using C++
33
initializeStack and isStackEmpty
template<class Type>
void linkedStackType<Type>:: initializeStack()
{
destroyStack();
}
template<class Type>
bool linkedStackType<Type>::isEmptyStack()
{
return(stackTop == NULL);
}
template<class Type>
bool linkedStackType<Type>::isFullStack()
{
return false;
Data Structures Using C++
34
Push
Stack before the push
operation
Stack and newNode
Data Structures Using C++
35
Push
Stack after the statement
newNode->link = stackTop;
executes
Stack after the statement
stackTop = newNode;
executes
Data Structures Using C++
36
Return Top Element
template<class Type>
Type linkedStackType<Type>::top()
{
assert(stackTop != NULL);
return stackTop->info;
}//end top
//if the stack is empty,
//terminate the program
//return the top element
Data Structures Using C++
37
Pop
Stack before the pop operation
Data Structures Using C++
38
Pop
Stack after the statements temp = stackTop;
and stackTop = stackTop->link; execute
Stack after the statement delete temp;
executes
Data Structures Using C++
39
Application of Stacks:
Postfix Expression Calculator
• Prefix/Polish Notation
• Suffix/Postfix/Reverse Polish Notation
Data Structures Using C++
40
Application of Stacks:
Postfix Expression Calculator
Data Structures Using C++
41
Application of Stacks:
Postfix Expression Calculator
Stack after pushing 6
Stack after pushing 3
Stack after retrieving the top two elements
and popping twice
Stack after pushing the result of op1 +
op2, which is 9
Data Structures Using C++
42
Application of Stacks:
Postfix Expression Calculator
Stack after pushing the result of op1 *
op2, which is 18
Stack after pushing 2
Stack after retrieving the top two elements
and popping twice
Stack after popping the element
Data Structures Using C++
43
Postfix Expression Calculator (Main Algorithm)
Data Structures Using C++
44
Nonrecursive Algorithm to Print
Linked List
current = first;
while(current != NULL)
{
stack.push(current);
current = current->link;
}
Data Structures Using C++
//Line 1
//Line 2
//Line 3
//Line 4
45
List After Execution of Statement
current = first;
Data Structures Using C++
46
Repeated Execution of:
stack.push(current);
current = current->link;
Data Structures Using C++
47
STL class stack
(Stack Container Adapter)
• Standard Template Library (STL) provides a
class to implement a stack in a program
• Name of the class defining a stack is stack
• Name of the header file containing the
definition of the class stack is stack
Data Structures Using C++
48
Operations on a stack Object
Data Structures Using C++
49
Chapter Summary
•
•
•
•
•
•
•
Stack Data Structure
Last In First Out (LIFO)
Stacks Implemented as Arrays
Stacks Implemented as Linked Lists
Postfix Expression Calculator
Nonrecursive Algorithm to Print Linked List
STL class stack
Data Structures Using C++
50