0% found this document useful (0 votes)

6 views113 pages

CSE225Lecture07StackQueue Array

The document provides an overview of stack and queue data structures, focusing on the stack's Last In First Out (LIFO) behavior and its array-based implementation. It details the operations of a stack, including Push, Pop, and Top, along with their preconditions and postconditions, and includes exception handling for full and empty stacks. Additionally, it discusses applications of stacks in matching parentheses and converting infix expressions to postfix notation.

Uploaded by

tasnia.tahosin.241

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

6 views113 pages

CSE225Lecture07StackQueue Array

Uploaded by

tasnia.tahosin.241

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

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 stack3 is full and false otherwise.
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
[Link]
#include "StackType.h" template <class ItemType>
template <class ItemType> void StackType<ItemType>::Push(ItemType
newItem)
StackType<ItemType>::StackType() {
{
if( IsFull() )
top = -1;
} 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
[Link]
#include "StackType.h" template <class ItemType>
template <class ItemType> void StackType<ItemType>::Push(ItemType
newItem)
StackType<ItemType>::StackType() {
{
if( IsFull() )
}
top = -1;
O(1) 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() {
{ if( IsEmpty() )
}
top = -1; O(1) throw EmptyStack(); O(1)
template <class ItemType> top--;
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
Algorithm for Infix to Postfix
1. Examine the next element in the input.
2. If it is operand, output it.
3. If it is opening parenthesis, push it on stack.
4. If it is an operator, then
• Pop until the top of the stack has an element of lower
precedence
• Then push it
5. If it is a closing parenthesis, pop operators from stack and output them
until an opening parenthesis is encountered. pop and discard the opening
parenthesis.
6. If there is more input go to step 1
7. If there is no more input, pop the remaining operators to output.

30
Application of Stack