Lecture 07
Abstract Data Type Stack and Queue
(Array-based Implementation)
CSE225: Data Structures and Algorithms
Stack
A list
Data items can be added and deleted
Maintains Last In First Out (LIFO) order
Specification of StackType
Structure: Elements are added to and removed from the top of the stack.
Definitions (provided by user):
MAX_ITEMS Maximum number of items that might be on the stack.
ItemType Data type of the items on the stack.
Operations (provided by the ADT):
MakeEmpty
Function Sets stack to an empty state.
Postcondition Stack is empty.
Boolean IsEmpty
Function Determines whether the stack is empty.
Precondition Stack has been initialized.
Postcondition Returns true if stack is empty and false otherwise.
Boolean IsFull
Function Determines whether the stack is full.
Precondition Stack has been initialized.
Postcondition Returns true if stack is full and false otherwise.
3
Specification of StackType
Push(ItemType newItem)
Function Adds newItem to the top of the stack.
Precondition Stack has been initialized.
Postcondition If (stack is full), exception FullStack is thrown, else newItem is at
the top of the stack.
Pop()
Function Removes top item from the stack.
Precondition Stack has been initialized.
Postcondition If (stack is empty), exception EmptyStack is thrown, else top
element has been removed from stack.
ItemType Top()
Function Returns a copy of the top item on the stack.
Precondition Stack has been initialized.
Postcondition If (stack is empty), exception EmptyStack is thrown, else a copy of
the top element is returned.
4
stacktype.h
#ifndef STACKTYPE_H_INCLUDED
#define STACKTYPE_H_INCLUDED
const int MAX_ITEMS = 5;
class FullStack
{}; // Exception class thrown by Push when stack is full.
class EmptyStack
{}; // Exception class thrown by Pop and Top when stack is empty.
template <class ItemType>
class StackType
{
public:
StackType();
bool IsFull();
bool IsEmpty();
void MakeEmpty();
void Push(ItemType);
void Pop();
ItemType Top();
private:
int top;
ItemType items[MAX_ITEMS];
};
#endif // STACKTYPE_H_INCLUDED
5
stacktype.cpp
#include "StackType.h" template <class ItemType>
template <class ItemType> void StackType<ItemType>::Push(ItemType
newItem)
StackType<ItemType>::StackType()
{
{
top = -1; if( IsFull() )
} throw FullStack();
template <class ItemType> top++;
bool StackType<ItemType>::IsEmpty() items[top] = newItem;
{ }
return (top == -1); template <class ItemType>
} void StackType<ItemType>::Pop()
void StackType<ItemType>::MakeEmpty() {
{
if( IsEmpty() )
top = -1;
} throw EmptyStack();
template <class ItemType> top--;
bool StackType<ItemType>::IsFull() }
{ template <class ItemType>
return (top == MAX_ITEMS-1); ItemType StackType<ItemType>::Top()
} {
if (IsEmpty())
throw EmptyStack();
return items[top];
}
6
stacktype.cpp
#include "StackType.h" template <class ItemType>
template <class ItemType> void StackType<ItemType>::Push(ItemType
newItem)
StackType<ItemType>::StackType()
{
{
O(1)
top = -1; if( IsFull() )
throw FullStack();
}
template <class ItemType>
bool StackType<ItemType>::IsEmpty()
top++;
items[top] = newItem;
O(1)
{ }
}
return (top == -1);
O(1) template <class ItemType>
void StackType<ItemType>::Pop()
void StackType<ItemType>::MakeEmpty() {
O(1)
{
if( IsEmpty() )
}
top = -1;
template <class ItemType>
throw EmptyStack();
top--;
O(1)
bool StackType<ItemType>::IsFull() }
{ template <class ItemType>
return (top == MAX_ITEMS-1); ItemType StackType<ItemType>::Top()
} {
O(1) if (IsEmpty())
throw EmptyStack();
return items[top]; O(1)
}
7
Application of Stack
()
(())()(()())()
(())()((()
(())))((()
Which of the strings of parentheses are balanced?
8
Application of Stack
Algorithm for matching parentheses string
1. Initialise an empty stack
2. Read next item in the string
a) If item is an opening parentheses, push it into the stack
b) Else, if item is a closing parentheses, pop from stack
3. If there are more items to process, go to step 2
4. Pop the answer off the stack.
Application of Stack
(())()(()())()
10
Application of Stack
(())()(()())()
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack
11
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack (
12
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack ( (
13
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack (
14
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack
15
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack (
16
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack
17
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack (
18
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack ( (
19
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack (
20
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack ( (
21
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack (
22
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack
23
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack (
24
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack
25
Application of Stack
string ( ( ) ) ( ) ( ( ) ( ) ) ( )
stack
empty stack
Indicates balanced string of parentheses
26
Application of Stack
(())()((()
Consider this string. After processing each
item, the stack is not empty.
stack ( (
non-empty stack
Indicates unbalanced string of parentheses
27
Application of Stack
(())))((()
Consider this string. When processing indicated item,
you are trying to pop from empty stack.
stack
unsuccessful pop
Indicates unbalanced string of parentheses
28
Application of Stack
Evaluating arithmatic expressions
Infix Postfix Evaluation
2-3*4+5 234*-5+ -5
(2 - 3) * (4 + 5) 23-45+* -9
2- (3 * 4 +5) 234*5+- -15
Why ? No parentheses necessary !
Application of Stack
Use binary tree to convert the following
expression
(4+8)*(6-5)/((3-2)*(2+2))into Postfix
form
4 8 + 6 5 - * 3 2 – 2 2 + * /
30
Application of Stack
Now let’s evaluate this expression
4 8 + 6 5 - * 3 2 – 2 2 + * /
31
Application of Stack
Algorithm for evaluating a postfix expression
1. Initialise an empty stack
2. Read next item in the expression
a) If item is an operand, push it into the stack
b) Else, if item is an operator, pop top two items off the stack, apply the operator,
and push the answer back into the stack
3. If there are more items to process, go to step 2
4. Pop the answer off the stack.
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack
33
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 4
34
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 4 8
35
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12
36
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 6
37
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 6 5
38
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 1
39
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12
40
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 3
41
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 3 2
42
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 1
43
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 1 2
44
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 1 2 2
45
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 1 4
46
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 12 4
47
Application of Stack
string 4 8 + 6 5 - * 3 2 - 2 2 + * /
stack 3
48
Application of Stack
Only item in stack: indicates valid expression
stack 3
More than one item in stack or unsuccessful pop:
indicates invalid expression
49
Queue
• A list
• Data items can be added and deleted
• Maintains First In First Out (FIFO) order
Specification of QueueType
Structure: Elements are added to the rear and removed from the front of the queue.
Definitions (provided by user):
MAX_ITEMS Maximum number of items that might be on the queue.
ItemType Data type of the items on the queue.
Operations (provided by the ADT):
MakeEmpty
Function Sets queueto an empty state.
Postcondition Queue is empty.
Boolean IsEmpty
Function Determines whether the queueis empty.
Precondition Queue has been initialized.
Postcondition Returns true if queue is empty and false otherwise.
Boolean IsFull
Function Determines whether the queue is full.
Precondition Queue has been initialized.
Postcondition Returns true if queue is full and false otherwise.
51
Specification of QueueType
Enqueue(ItemType newItem)
Function Adds newItem to the rear of the queue.
Precondition Queue has been initialized.
Postcondition If (queue is full), FullQueue exception is thrown, else newItem is
at rear of queue.
Dequeue(ItemType& item)
Function Removes front item from the queue and returns it as item.
Precondition Queue has been initialized.
Postcondition If (queue is empty), EmptyQueue exception is thrown and item is
undefined, else front element has been removed from queue and
item is a copy of removed element.
52
Implementation Issues
• Always insert elements at the back of the array.
• Complexity of deletion: O(N)
Implementation Issues
• Maintain two indices: front and rear
• Increment the indices as enqueue and dequeue are
performed (rear++ for enqueue and front++ for dequeue)
Dead
space
Implementation Issues
• Maintain two indices: front and rear
• Make the indices “wrap around” when they reach the end of the
array:
• For Enqueue: rear = (rear + 1) % maxQue;//maxQue=array
size
• For Dequeue: front = (front + 1) % maxQue;
Implementation Issues
• How do we differentiate between the empty
state and the full state?
Implementation Issues
• Let front indicate the index of the array slot preceding
the front element.
• The array slot preceding the front element is reserved
and items are not assigned in that slot.
Implementation Issues
• Full queue when (rear + 1) % maxQue == front
• Empty queue when front == rear
queuetype.h
#define DEFAULT_SIZE 500
typedef char ItemType;
class FullQueue
{};
class EmptyQueue
{};
template <class ItemType>
class QueType
{
public:
QueType();
QueType(int max);
~QueType();
void MakeEmpty();
bool IsEmpty();
bool IsFull();
void Enqueue(ItemType newItem);
void Dequeue(ItemType& item);
private:
int front;
int rear;
ItemType* items;
int maxQue;
}; 59
queuetype.cpp
#include "QueType.h" void QueType::MakeEmpty()
{
QueType::QueType(int max) front = maxQue - 1;
{ rear = maxQue - 1;
maxQue = max + 1;
front = maxQue - 1; }
rear = maxQue - 1;
items = new ItemType[maxQue]; bool QueType::IsEmpty()
} {
return (rear == front);
QueType::QueType() }
{
maxQue = DEFAULT_SIZE + 1; bool QueType::IsFull()
front = maxQue - 1; {
rear = maxQue - 1;
items = new ItemType[maxQue]; return ((rear+1)%maxQue == front);
} }
QueType::~QueType()
{
delete [] items;
}
60
queuetype.cpp
void QueType::Enqueue(ItemType newItem)
{
if (IsFull())
throw FullQueue();
else
{
rear = (rear +1) % maxQue;
items[rear] = newItem;
}
}
void QueType::Dequeue(ItemType& item)
{
if (IsEmpty())
throw EmptyQueue();
else
{
front = (front + 1) % maxQue;
item = items[front];
}
}
61
queuetype.cpp
#include "QueType.h" void QueType::MakeEmpty()
{
QueType::QueType(int max)
O(1)
front = maxQue - 1;
{ rear = maxQue - 1;
maxQue = max + 1;
front = maxQue - 1;
rear = maxQue - 1;
O(1) }
items = new ItemType[maxQue]; bool QueType::IsEmpty()
} {
QueType::QueType() }
return (rear == front); O(1)
{
maxQue = DEFAULT_SIZE + 1; bool QueType::IsFull()
O(1)
front = maxQue - 1; {
rear = maxQue - 1;
items = new ItemType[maxQue]; return ((rear+1)%maxQue == front);
} }
O(1)
QueType::~QueType()
{
delete [] items; O(1)
}
queuetype.cpp
void QueType::Enqueue(ItemType newItem)
{
if (IsFull())
throw FullQueue();
else
{
rear = (rear +1) % maxQue;
}
items[rear] = newItem;
O(1)
}
void QueType::Dequeue(ItemType& item)
{
if (IsEmpty())
throw EmptyQueue();
else
{
front = (front + 1) % maxQue;
item = items[front];
}
}
O(1)
