Data Structures Using C++ 2E

Chapter 7
Stacks

Edited by Malak Abdullah

Jordan University of Science and Technology
 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 how to use a stack to remove recursion

Data Structures Using C++ 2E Edited by Malak Abdullah 2

Jordan University of Science and Technology
 Introduction
• Data structure
– Elements added, removed from one end only
– Last In First Out (LIFO)

FIGURE 7-1 Various examples of stacks

Data Structures Using C++ 2E Edited by Malak Abdullah 3

Jordan University of Science and Technology
 Introduction
• A stack is a list of homogenous elements in which
the addition and deletion of elements occurs only at
one end, called the top of the stack.
• The elements at the bottom of the stack have been
in the stack the longest.
• The top element of the stack is the last element
added to the stack.

Edited by Malak Abdullah 4

Jordan University of Science and Technology
 Introduction
• Because the elements are added and removed
from one end (that is, the top), it follows that the
item that is added last will be removed first. For this
reason, a stack is also called a Last In First Out
(LIFO) data structure.

• Stack: A data structure in which the elements are

added and removed from one end only; a Last In
First Out (LIFO) data structure.

Edited by Malak Abdullah 5

Jordan University of Science and Technology
 Stacks Operations
• Items can be added to the stack.
– we can perform the add operation, called push
– to add an element onto the stack.
• Item at the top can be retrieved from the stack
– we can perform the operation top to retrieve the top
element of the stack.
• Item at the top can be removed from the top of the
stack.
– we can perform the operation pop to remove the top
element of the stack.
Edited by Malak Abdullah 6
Jordan University of Science and Technology
 Stacks Operations
• An element can be removed from the stack only if
there is something in the stack
• An element can be added to the stack only if there
is room.
• The two operations that immediately follow from
push, top, and pop are isFullStack (checks
whether the stack is full) and isEmptyStack
(checks whether the stack is empty).

Data Structures Using C++ 2E Edited by Malak Abdullah 7

Jordan University of Science and Technology
 Stacks Operations
• Because a stack keeps changing as we add and
remove elements, the stack must be empty before
we first start using it.
– We need an operation, initializeStack, which
initializes the stack to an empty state.

Data Structures Using C++ 2E Edited by Malak Abdullah 8

Jordan University of Science and Technology
 Stacks Six Basic Operations
• push operation
– Add element onto the stack
• top operation
– Retrieve top element of the stack
• pop operation
– Remove top element from the stack

Data Structures Using C++ 2E Edited by Malak Abdullah 9

Jordan University of Science and Technology
 Stacks Six Basic Operations

• isFullStack operation
– Checks for full stack
• isEmptyStack operation
– Checks for empty stack
• initializeStack operation
– Initializes stack to an empty state

Data Structures Using C++ 2E Edited by Malak Abdullah 10

Jordan University of Science and Technology
 Stacks Operations

FIGURE 7-2 Empty stack

FIGURE 7-3 Stack operations

Data Structures Using C++ 2E Edited by Malak Abdullah 11
Jordan University of Science and Technology
 Stacks (cont’d.)
• Review code on page 398
– Illustrates class specifying basic stack operations

GURE 7-4 UML class diagram of the class stackADT

Data Structures Using C++ 2E Edited by Malak Abdullah 12
Jordan University of Science and Technology
 Implementation of Stacks as Arrays
• Because all the elements of a stack are of the
same type, you can use an array to implement a
stack.
• The first element of the stack can be put in the first
array slot.
• The second element of the stack in the second
array slot, and so on.
• The top of the stack is the index of the last element
added to the stack.

Data Structures Using C++ 2E Edited by Malak Abdullah 13

Jordan University of Science and Technology
 Implementation of Stacks as Arrays
• First stack element
– Put in first array slot
• Second stack element
– Put in second array slot, and so on
• Top of stack
– Index of last element added to stack

Data Structures Using C++ 2E Edited by Malak Abdullah 14

Jordan University of Science and Technology
 Implementation of Stacks as Arrays
• Stack element accessed only through the top
– Problem: array is a random access data structure
(that is, you can directly access any element of the
array.)
– Solution: use another variable (stackTop)
• Keeps track of the top position of the array
– Notes:
• If stackTop is 0, the stack is empty.
• If stackTop is nonzero, the stack is nonempty and the
top element of the stack is given by stackTop – 1
because the first stack element is at position 0.
Data Structures Using C++ 2E Edited by Malak Abdullah 15
Jordan University of Science and Technology
 Implementation of Stacks as Arrays
(cont’d.)
• Review code on page 400
– Illustrates basic operations on a stack as an array

FIGURE 7-5 UML class diagram of the class stackType

Data Structures Using C++ 2E Edited by Malak Abdullah 16
Jordan University of Science and Technology
Max 10
0 1 2 3 .. .
stackTop 0
list

Edited by Malak Abdullah

Jordan University of Science and Technology
 Implementation of Stacks as Arrays
(cont’d.)

FIGURE 7-6 Example of a stack

Data Structures Using C++ 2E Edited by Malak Abdullah 18

Jordan University of Science and Technology
 Initialize Stack
• Value of stackTop if stack empty
– Set stackTop to zero to initialize the stack
• Definition of function initializeStack

FIGURE 7-7 Empty stack

Data Structures Using C++ 2E Edited by Malak Abdullah 19

Jordan University of Science and Technology
 Empty Stack
• Value of stackTop indicates if stack empty
– If stackTop = zero: stack empty
– Otherwise: stack not empty
• Definition of function isEmptyStack

Data Structures Using C++ 2E Edited by Malak Abdullah 20

Jordan University of Science and Technology
 Full Stack
• Stack full
– If stackTop is equal to maxStackSize
• Definition of function isFullStack

Data Structures Using C++ 2E Edited by Malak Abdullah 21

Jordan University of Science and Technology
 Push
• Two-step process
– Store newItem in array component indicated by
stackTop
– Increment stackTop

FIGURE 7-8 Stack before and after the push operation

Data Structures Using C++ 2E Edited by Malak Abdullah 22
Jordan University of Science and Technology
 Push (cont’d.)
• Definition of push operation

Data Structures Using C++ 2E Edited by Malak Abdullah 23

Jordan University of Science and Technology
 Return the Top Element
• Definition of top operation
template <class Type>
Type stackType<Type>::top() const
{
assert(stackTop != 0 );
return list[stackTop-1];
}

Data Structures Using C++ 2E Edited by Malak Abdullah 24

Jordan University of Science and Technology
 Pop
• Remove (pop) element from stack
– Decrement stackTop by one

FIGURE 7-9 Stack before and after the pop operation

Data Structures Using C++ 2E Edited by Malak Abdullah 25
Jordan University of Science and Technology
 Pop (cont’d.)
• Definition of pop operation
• Underflow
– Removing an item from an empty stack
• Check within pop operation (see below)
• Check before calling function pop

Data Structures Using C++ 2E Edited by Malak Abdullah 26

Jordan University of Science and Technology
 Constructor and Destructor

Data Structures Using C++ 2E Edited by Malak Abdullah 27

Jordan University of Science and Technology
 Copy Stack
S1.copyStack(S2)

Max 10 S2 Max 20
10 S1
StackTop 3 StackTop 5
3
List 10 20 30 List 6 9 30
7 8 2
10 20

Data Structures Using C++ 2E Edited by Malak Abdullah 28

Jordan University of Science and Technology
 Copy Constructor
• Definition of the copy constructor

Data Structures Using C++ 2E Edited by Malak Abdullah 29

Jordan University of Science and Technology
 Overloading the Assignment Operator
(=)
• Classes with pointer member variables
– Assignment operator must be explicitly overloaded
• Function definition to overload assignment operator
for class stackType

Data Structures Using C++ 2E Edited by Malak Abdullah 30

Jordan University of Science and Technology
• myStack.h
Stack Header File
– Header file name containing class stackType
definition

Data Structures Using C++ 2E Edited by Malak Abdullah 31

Jordan University of Science and Technology
 Stack Header File (cont’d.)

Time complexity of the operations of the class stackType on a stack with n elements
32
Data Structures Using C++ 2E
 To Print the contents
of the stack
Max 100 obj
StackTop
List 9 10 4 6 3

Max 100 TempObj

StackTop
List 3 6 4 10 9

Print the stack elements

9 10 4 6 3
Edited by Malak Abdullah
Jordan University of Science and Technology
 Delete number 4

Max 100 obj

StackTop
List 9 10 4 6 3

Edited by Malak Abdullah

Jordan University of Science and Technology
 Delete number 4

Max 100 obj

StackTop
List 9 10 4 6 3

Max 100 TempObj

StackTop
List 3 6 10 9

Edited by Malak Abdullah

Jordan University of Science and Technology
 Delete number 4

Max 100 obj

StackTop
List 9 10 6 3

Max 100 TempObj

StackTop
List 3 6 10 9

Edited by Malak Abdullah

Jordan University of Science and Technology
 Linked Implementation of Stacks
• Disadvantage of array (linear) stack representation
– Fixed number of elements can be pushed onto stack
• Solution
– Use pointer variables to dynamically allocate, deallocate
memory
– Use linked list to dynamically organize data
• Value of stackTop: linear representation
– Indicates number of elements in the stack
• Gives index of the array
– Value of stackTop – 1
• Points to top item in the stack
Data Structures Using C++ 2E Edited by Malak Abdullah 37
Jordan University of Science and Technology
 Linked Implementation of Stacks
(cont’d.)
• Value of stackTop: linked representation
– Locates top element in the stack
• Gives address (memory location) of the top element of
the stack
• Review program on page 415
– Class specifying basic operation on a stack as a
linked list

Data Structures Using C++ 2E Edited by Malak Abdullah 38

Jordan University of Science and Technology
stackTop

stackTop 3 7 5

Edited by Malak Abdullah

Jordan University of Science and Technology
 Linked Implementation of Stacks (cont’d.)
• Example 7-2
– Stack: object of type linkedStackType

FIGURE 7-10 Empty and nonempty linked stacks

Data Structures Using C++ 2E Edited by Malak Abdullah 40
Jordan University of Science and Technology
 Default Constructor
• When stack object declared
– Initializes stack to an empty state
– Sets stackTop to NULL
• Definition of the default constructor

Data Structures Using C++ 2E Edited by Malak Abdullah 41

Jordan University of Science and Technology
 Empty Stack and Full Stack
• Stack empty if stackTop is NULL
• Stack never full
– Element memory allocated/deallocated dynamically
– Function isFullStack always returns false value

Data Structures Using C++ 2E Edited by Malak Abdullah 42

Jordan University of Science and Technology
 Initialize Stack
• Reinitializes stack to an empty state
• Because stack might contain elements and you are
using a linked implementation of a stack
– Must deallocate memory occupied by the stack
elements, set stackTop to NULL
• Definition of the initializeStack function

Data Structures Using C++ 2E Edited by Malak Abdullah 43

Jordan University of Science and Technology
 Initialize Stack (cont’d.)
4 8 9
stackTop

temp

Data Structures Using C++ 2E Edited by Malak Abdullah 44

Jordan University of Science and Technology
 Push
• newElement added at the beginning of the linked
list pointed to by stackTop
• Value of pointer stackTop updated

FIGURE 7-11 Stack before the push operation

Data Structures Using C++ 2E Edited by Malak Abdullah 45

Jordan University of Science and Technology
 Push (cont’d.)

FIGURE 7-12 Push operation

Data Structures Using C++ 2E Edited by Malak Abdullah 46
Jordan University of Science and Technology
 Push (cont’d.)

• Definition of the push function

Data Structures Using C++ 2E Edited by Malak Abdullah 47

Jordan University of Science and Technology
 Return the Top Element
• Returns information of the node to which
stackTop pointing
• Definition of the top function

Data Structures Using C++ 2E Edited by Malak Abdullah 48

Jordan University of Science and Technology
 Pop
• Removes top element of the stack
– Node pointed to by stackTop removed
– Value of pointer stackTop updated

FIGURE 7-14 Pop operation

Data Structures Using C++ 2E Edited by Malak Abdullah 49
Jordan University of Science and Technology
 Pop (cont’d.)

• Definition of the pop function

Data Structures Using C++ 2E Edited by Malak Abdullah 50

Jordan University of Science and Technology
 Copy Stack
• Makes an identical copy of a stack
• Definition similar to the definition of copyList for linked lists
• Definition of the copyStack function

4 8 9
stackTop

current current current

4 If there is any
8 thing delete it 9
stackTop

last last

Data Structures Using C++ 2E Edited by Malak Abdullah 51

Jordan University of Science and Technology
Data Structures Using C++ 2E Edited by Malak Abdullah 52
Jordan University of Science and Technology
 Constructors and Destructors
• Definition of the functions to implement the copy
constructor and the destructor

Data Structures Using C++ 2E Edited by Malak Abdullah 53

Jordan University of Science and Technology
 Overloading the Assignment Operator
(=)
• Definition of the functions to overload the
assignment operator

Data Structures Using C++ 2E Edited by Malak Abdullah 54

Jordan University of Science and Technology
 Overloading the Assignment Operator
(=) (cont’d.)
TABLE 7-2 Time complexity of the operations of the class
linkedStackType on a stack with n elements

Data Structures Using C++ 2E Edited by Malak Abdullah 55

Jordan University of Science and Technology
 Stack as Derived from the class
unorderedLinkedList
• Stack push function, list insertFirst function
– Similar algorithms
– initializeStack and initializeList,
isEmptyList and isEmptyStack, etc.
– Shows that class linkedStackType is derived
from class linkedListType
• Functions pop and isFullStack implemented for
linked stack
– class linkedListType: abstract class
– class unorderedLinkedListType: derived
from class linkedListType

Data Structures Using C++ 2E Edited by Malak Abdullah 56

Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator
• Arithmetic notations
– Infix notation: operator between operands
– Prefix (Polish) notation: operator precedes operands
– Reverse Polish notation: operator follows operands
• Stack use in compliers
– Translate infix expressions into some form of postfix
notation
– Translate postfix expression into machine code

Data Structures Using C++ 2E Edited by Malak Abdullah 57

Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator
• The usual notation for writing arithmetic expressions
is called infix notation, in which the operator is
written between the operands.
– For example: in the expression a + b, the operator +
is between the operands a and b.
• In infix notation, the operators have precedence.
That is, we must evaluate expressions from left to
right, and multiplication and division have higher
precedence than addition and subtraction.

Data Structures Using C++ 2E Edited by Malak Abdullah 58

Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator
• To evaluate the expression in a different order, we
must include parentheses.
– For example: in the expression a + b * c, we first
evaluate * using the operands b and c, and then we
evaluate + using the operand a and the result of b * c.
• Jan Lukasiewicz discovered that if operators were
written before the operands (prefix or Polish notation;
for example, + a b), the parentheses can be omitted.

Data Structures Using C++ 2E Edited by Malak Abdullah 59

Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator
• Charles L. Hamblin proposed a scheme in which the
operators follow the operands (postfix operators),
resulting in the Reverse Polish notation.
• This has the advantage that the operators appear in
the order required for computation.
– For example: the expression: a + b * c
in a postfix expression is: a b c * +

Data Structures Using C++ 2E Edited by Malak Abdullah 60

Jordan University of Science and Technology
• InFix Notation
• (4 + 5) * 2 – 7  9 * 2 – 7 18 - 7 11

• PreFix
• - * + 4 5 2 7  - * 9 2 7  - 18 7  11

• PostFix (Polish)
• 4 5 + 2 * 7 -  9 2 * 7 -  18 7 -  11
Edited by Malak Abdullah
Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator

Data Structures Using C++ 2E Edited by Malak Abdullah 62

Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator
• Postfix notation had important applications in computer
science.
– Many compilers use stacks to first translate infix
expressions into some form of postfix notation and then
translate this postfix expression into machine code.
• Postfix expressions can be evaluated using the following
algorithm:
– Scan the expression from left to right.
– When an operator is found, back up to get the required
number of operands
– perform the operation, and continue.
63
 Application of Stacks: Postfix
Expressions Calculator (cont’d.)
• Postfix expression: 6 3 + 2 * =

6
9 3
2

Push (6)
Push(2)
(3)

Pop
Pop
Push (6+3)

Data Structures Using C++ 2E Edited by Malak Abdullah 64

Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator (cont’d.)
• Postfix expression: 6 3 + 2 * =

18
9 2

Pop
Pop
Push( 9 *2)

Data Structures Using C++ 2E Edited by Malak Abdullah 65

Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator (cont’d.)
• Postfix expression: 6 3 + 2 * =

FIGURE 7-15 Evaluating the postfix expression: 6 3 + 2 * =

Data Structures Using C++ 2E Edited by Malak Abdullah 66
Jordan University of Science and Technology
 Application of Stacks: Postfix
Expressions Calculator (cont’d.)
• Main algorithm pseudocode
– Broken into four functions for simplicity
• Function evaluateExpression
• Function evaluateOpr
• Function discardExp
• Function printResult

Data Structures Using C++ 2E Edited by Malak Abdullah 67

Jordan University of Science and Technology
 Edited by Malak Abdullah
Jordan University of Science and Technology
#include<iostream>
#include<stack>
using namespace std;

void main()
{
stack <int> PostFix;
char i;
cout<<"Please insert our expression ";
cin>>i;

int x, y;
while(i != '=')
{
switch (i)
{
case '+':
x=PostFix.top();
PostFix.pop();
y=PostFix.top();
PostFix.pop();
PostFix.push(y + x);
break;
case '-':
x=PostFix.top();
PostFix.pop();
y=PostFix.top();
PostFix.pop();
PostFix.push(y - x);
break;
case '*':
x=PostFix.top();
PostFix.pop();
y=PostFix.top();
PostFix.pop();
PostFix.push(y * x);
break;
case '/':
x=PostFix.top();
PostFix.pop();
y=PostFix.top();
PostFix.pop();
PostFix.push(y / x);
break;

default:
PostFix.push(i-48);
}
cin>>i;
}

cout<<"The result is "<<PostFix.top()<<endl;

}
Edited by Malak Abdullah
Jordan University of Science and Technology
 Edited by Malak Abdullah
Jordan University of Science and Technology
 Removing Recursion: Nonrecursive
Algorithm to Print a Linked List Backward
• Stack
– Used to design nonrecursive algorithm
• Print a linked list backward
• Use linked implementation of stack

Data Structures Using C++ 2E Edited by Malak Abdullah 71

Jordan University of Science and Technology
FIGURE 7-16 Linked list
FIGURE 7-17 List after the statement
current = first; executes

FIGURE 7-18 List and stack after the statements stack.push(current); and
current = current->link; execute
Data Structures Using C++ 2E Edited by Malak Abdullah 72
Jordan University of Science and Technology
FIGURE 7-19 List and stack after the
while statement executes

FIGURE 7-20 List and stack after the statements current = stack.top(); and
stack.pop(); execute
Data Structures Using C++ 2E Edited by Malak Abdullah 73
Jordan University of Science and Technology
 STL class stack
• Standard Template Library (STL) library class
defining a stack
• Header file containing class stack definition
– stack
TABLE 7-3 Operations on a stack object

Data Structures Using C++ 2E Edited by Malak Abdullah 74

Jordan University of Science and Technology
 Summary
• Stack
– Last In First Out (LIFO) data structure
– Implemented as array or linked list
– Arrays: limited number of elements
– Linked lists: allow dynamic element addition
• Stack use in compliers
– Translate infix expressions into some form of postfix
notation
– Translate postfix expression into machine code
• Standard Template Library (STL)
– Provides a class to implement a stack in a program
Data Structures Using C++ 2E Edited by Malak Abdullah 75
Jordan University of Science and Technology