Transcript LECT#22

Abstract Data Types (ADT) –I
Overview
 What is an Abstract Data type?
 What is Stack ADT?
 Stack ADT Specifications
 Array Implementation of Stack ADT
 Example Applications of Stack
 What is Queue ADT?
 Queue ADT Specifications
 Queue ADT Implementation
 Handling UnderFlow/OverFlow Exceptions
 Preview: Abstract Data Types - II
Lecture 24
1
Abstract Data Types I
 An abstract data type (ADT) is a data type (a set of values and a collection
of operations on those values) that is accessed only through an interface.
 Data structure on the other hand, is a representation (in a computer) for a
collection of related information. Example Array.
 An ADT may be implemented using different data structures, but the client
program must access it through its interface.
 This separation of interface (what) from implementation (how) is very
important and has many advantages. Some of these are:




Allows program code to be more generic/reusable
Hide unnecessary information
Allows Easier software maintenance
Help manage software complexity
 In this lecture and the next two, we shall learn how to design and implement
some basic ADT’s, namely stack, queue and list, using different data
structures.
Lecture 24
2
What is Stack ADT?
 A stack is an ADT which accepts elements one at a time
for storage and presents them for retrieval in reverse order
 a LIFO (last in, first out) structure
 The following Operations are normally defined for a
Stack





push (place an element on the top of the stack)
pop (remove an element from the top of the stack)
peek (return top element on the stack)
isEmpty (boolean function to check for an empty stack)
isFull (optional boolean test to check if stack is full)
Lecture 24
3
Stack..LIFO
Lecture 24
4
Stack
Lecture 24
5
Stack ADT Specification
public class StackArray {
private int maxSize;
private char[] items;
private int stackTop;
public StackArray(int size) {}
public boolean isEmpty() {}
public boolean isFull() {}
public void push(char d) {}
public void pop() {}
public char peek() {}
/* construct Stack of specified size */
/* return TRUE if empty else false */
/* return TRUE if Stack is full */
/* push element onto Stack */
/* remove first element from stack */
/* return first element in Stack */
}
 For simplicity the above specification only caters for Stacks of type
‘char’. Later on we will consider how the stack can store any type.
Lecture 24
6
Stack ADT Implementation using Array
public StackArray(int s) {
maxSize = s;
items = new char[maxSize];
stackTop = -1;
}
public void pop() {
stackTop--;
}
public boolean isEmpty() {
return (stackTop == -1);
public char peek() {
return items[stackTop];
}
}
public boolean isFull() {
return (stackTop == maxSize - 1);
}
public void push(char d) {
items[++stackTop] = d;
Empty Stack
}
b
a
Push a onto stack
Lecture 24
a
a
Push b onto stack
Pop b from
stack
7
Example 1 - String Reversal
 Requirement: method to reverse a string.
public String reverseInput (String input) {
int len = input.length();
StackArray s = new StackArray(len);
for(int i=0; i< len; i++) {
s.push(input.charAt(i));
}
String output = new String();
while (! s.isEmpty()) {
char ch = s.peek();
output=output + ch;
s.pop();
}
return output;
}
Lecture 24
8
Example 2- Bracket Matching
 Stacks are often used in parsing algorithms used by expression
evaluators or compilers.
 Consider an algorithm to validate the delimiters in a line of text.
The delimiters will include square brackets ‘[‘ and ‘]’, braces ‘{‘
and ‘}’, and round brackets ‘(‘ and ‘)’. Each opening delimiter
should be matched by a corresponding closing delimiter. For
example:

Lecture 24
9
Example 2- Bracket Matching (cont)
 Consider the following string: a { b ( c [ d ] e ) f }
character read
a
{
b
(
c
[
d
]
e
)
f
}
stack contents
{
{
{(
{(
{([
{([
{(
{(
{
{
 On reading opening
delimiter, place it on
stack. On reading a
closing delimiter remove
top element from stack
and compare. If delimiter
removed from stack does
not match closing
delimiter then the
expression is invalid.
Lecture 24
10
What is Queue ADT?
 A queue is a linear data type consisting of elements of a single
type. Elements join a queue at one end and leave at the other.
 a FIFO (first in first out) structure.
 What happens at an orderly bus stop is a reasonable model for
the operations that apply to a queue.
 enqueue (place element at end of queue)
 dequeue (remove element from start of queue)
 front (return first element in queue)
 isEmpty (boolean check for empty queue)
 size (return number of items in the queue)
 isFull (optional boolean test for a full queue)
Lecture 24
11
FIFO Queue
Lecture 24
12
Circular Queue
Lecture 24
13
Queue Implementation
 2 options for fixed size implementation as an array
 (1) Flat array - inefficient
J
J
J
Head
J
Tail
 (2) Circular array - much better
J
Head
J
J
J
Tail
Lecture 24
14
Queue ADT Specification (Circular Array)
public class QueueArray {
private int maxSize;
private char[] queArray;
private int front, rear, nItems;
public QueueArray(int s) {};
public boolean isEmpty() {};
public boolean isFull() {};
public int size() {};
public void enqueue(char c) {};
public void dequeue() {};
public char front() {};
/* create new queue of fixed size */
/* test if Queue is empty */
/* test if Queue is full */
/* return length of Queue */
/* add element c to queue */
/* remove first element in queue*/
/* return first element in Queue */
}
 For simplicity the above specification only caters for Queues of type
’char’. Later on we will consider how the queue can store any type.
Lecture 24
15
Queue ADT Implementation
public QueueArray(int s) {
front = 0; rear = -1; nItems = 0;
maxSize = s;
queArray = new char[maxSize];
}
public void enqueue(char j) {
rear = (rear+1) % maxSize;
queArray[rear] = j;
nItems++;
}
public void dequeue() {
nItems--;
front = (front+1) % maxSize;
}
public char front() {
return queArray[front];
}
public boolean isEmpty() {
return (nItems==0);
}
public boolean isFull() {
return (nItems==maxSize);
}
public int size() {
return nItems;
}
Lecture 24
16
Dealing With Exceptional Conditions
 Neither of the implementations for Stacks or Queues handled
exceptional conditions. For example:
 adding an element to a full stack or queue
 removing an element from an empty stack or queue
StackArray s = new StackArray(2);
QueueArray q = new QueueArray(2);
s.pop();
// error stack underflow
s.push(‘1’);
s.push(‘2’);
s.push(‘3’); // error stack overflow
s.pop();
s.pop();
s.top();
// error stack empty
q.dequeue(); // error queue underflow
q.enqueue(‘1’);
q.enqueue(‘2’);
q.enqueue(‘3’); // error queue overflow
q.dequeue();
q.dequeue);
q.front();
// error queue empty
 We can use Java Exception Handling Mechanism to deal
with these unexpected events
Lecture 24
17
Throwing an Exception in Java
 The following implementation of the stack pop method now checks
for stack underflow (i.e the stack is already empty) and if it occurs an
exception is thrown to indicate the error. NOTE the exception is not
handled locally but is propagated to the calling method
public void pop() throws Exception {
if (this.isEmpty())
// check for underflow
throw new Exception(“stack underflow”);
else
stacktop--;
}
 A generic Exception is thrown. In the next slide we will see
how to create a new StackOutOfBoundsException for use in
our Stack class.
Lecture 24
18
Creating an Exception Class in Java
 If none of the standard Java exception classes are suitable you can
create your own by deriving it from the base class Exception or a child
class such as IndexOutOfBoundsException
import java.lang.IndexOutOfBoundsException;
class StackOutOfBoundsException extends IndexOutOfBoundsException {
public StackOutOfBoundsException() {}
// default constructor
public StackOutOfBoundsException(String problem) {
super(problem); // let superclass constructor handle the argument
}
}
 As the above StackOutOfBoundsException inherits from
IndexOutOfBoundsException it is an example of a runtime
exception and therefore there is no obligation to catch this type of
exception, but doing so will stop the program from terminating
with an error.
Lecture 24
19