Data structures throw Java M.Tech Lab part2
17. Write Java programs to implement the following
using an array.
(a) Stack ADT
(b) Queue ADT
Stack ADT
A Stack is an
Abstract Data Type (ADT) that supports the following methods:
push(obj): Add object obj at the top of the stack.
Input:
Object; Output: None.
obj pop(): Delete an item from the top of the stack and
returns object obj; an error occurs if the stack
is empty.
Input: None;
Output: Object.
obj peek():
Returns the top object obj on the stack , without removing it; an error occurs
if the stack
is empty.
Input: None;
Output: Object.
boolean
isEmpty(): Returns a boolean indicating if the stack is empty.
Input: None;
Output: boolean (true or false).
int size():
Returns the number of items on the stack.
Input: None;
Output: integer.
Type Object may be any type that can be stored in
the stack. The actual type of the object will be
provided by the user. The ADT is translated into a
Java interface in Program 17(a).
Program 17(a): A Stack Interface
public
interface Stack
{ public void push(Object ob);
public Object
pop();
public Object
peek();
public
boolean isEmpty();
public int
size();
}
The push, pop, peek, empty, and size operations are
translated directly into specifications for methods
named push(), pop(), peek(), isEmpty(), and size()
respectively. These are conventional names
for stack operations. Each method is defined by
specifying its return value and any changes that it
makes to the object.
Stack Implementation
There are several ways to implement the Stack
interface. The simplest is to use an ordinary array.
This is done in Program 17(b). The ArrayStack
implementation uses an array a[] to store elements
of the stack. Its other data field is the integer
top, which refers top element of the stack. The top is
also used to count the current number of items in
the stack. 4. Stacks and Queues
33
Program 17(b): An ArrayStack Class
public class ArrayStack implements Stack
{
private
Object a[];
private int
top; // stack top
public
ArrayStack(int n) // constructor
{ a = new
Object[n]; // create stack array
top = -1; //
no items in the stack
}
public void
push(Object item) // add an item on top of stack
{
if(top ==
a.length-1)
{
System.out.println("Stack is full");
return;
}
top++; //
increment top
a[top] =
item; // insert an item
}
public Object
pop() // remove an item from top of stack
{
if( isEmpty()
)
{
System.out.println("Stack is empty");
return null;
}
Object item =
a[top]; // access top item
top--; //
decrement top
return item;
}
public Object
peek() // get top item of stack
{ if(
isEmpty() ) return null;
return
a[top];
}
public
boolean isEmpty() // true if stack is empty
{ return (top
== -1); }
public int
size() // returns number of items in the stack
{ return
top+1; }
}
The constructor creates a new stack of a size, n
specified in its argument. The variable top stores
the index of the item on the top of the stack.
The push() method increments top so it points to the
space just above the previous top, and
stores a data item there. Notice that top is
incremented before the item is inserted. The pop() method
returns the value at top and then decrements top.
This effectively removes the item from the stack; it
is inaccessible, although the value remains in the
array (until another item is pushed into the cell). The
peek() method simply returns the value at top,
without changing the stack. The specifications for the
pop() and peek() methods in the Stack interface
require that the stack be not empty. The
isEmpty() method returns true if the stack is empty.
The top variable is at –1 if the stack is empty.
The
ArrayStack class is tested in the Program 17(c). 34 Lab Manual Data Structures
through Java
Program 17(c): Testing ArrayStack Class
class ArrayStackDemo
{
public static
void main(String[] args)
{
ArrayStack
stk = new ArrayStack(4); // create stack of size 4
Object item;
stk.push('A'); // push 3 items onto stack
stk.push('B');
stk.push('C');
System.out.println("size(): "+
stk.size());
item =
stk.pop(); // delete item
System.out.println(item + " is deleted");
stk.push('D'); // add three more items to the
stack
stk.push('E');
stk.push('F');
System.out.println(stk.pop() + " is
deleted");
stk.push('G'); // push one item
item =
stk.peek(); // get top item from the stack
System.out.println(item + " is on top of
stack");
}
}
Output of this program is:
size(): 3
C is deleted
Stack is full
E is deleted
G is on top
of stack
Queue ADT
The elements in a queue are of generic type Object.
The queue elements are linearly ordered from the
front to the rear. Elements are inserted at the rear
of the queue (enqueued) and are removed from the
front of the queue (dequeued). A Queue is an
Abstract Data Type (ADT) that supports the following
methods:
insert(obj): Adds object obj at the rear of a queue.
Input: Object;
Output: None.
obj remove(): Deletes an item from the front of a
queue and returns object obj; an error occurs if
the queue is empty.
Input: None;
Output: Object.
obj peek():
Returns the object obj at the front of a queue , without removing it; an error
occurs if
the queue is empty.
Input: None;
Output: Object.
boolean
isEmpty(): Returns a boolean indicating if the queue is empty. 4. Stacks and Queues
35
Input: None;
Output: boolean (true or false).
int size():
Returns the number of items in the queue.
Input: None;
Output: integer.
Type Object may be any type that can be stored in
the queue. The actual type of the object will be
provided by the user. The ADT is translated into a
Java interface in Program 17(d).
Program 17(d): A Queue Interface
public interface Queue
{
public void
insert(Object ob);
public Object
remove();
public Object
peek();
public
boolean isEmpty();
public int
size();
}
Note the similarities between these specifications
and that of the stack interface. The only real
difference, between the names of the operations, is
that the queue adds new elements at the opposite
end from which they are accessed, while the stack
adds them at the same end.
Queue Implementation
The ArrayQueue implementation of queue interface is
done by taking an array, que[n] and treating it
as if it were circular. The elements are inserted by
increasing rear to the next free position. When rear
= n-1, the next element is entered at que[0] in case
that spot is free. That is, the element que[n-1]
follows que[0]. Program 17(e) implements the
ArrayQueue class, and Program 17(f) tests this class.
Program 17(e): An ArrayQueue Class
class ArrayQueue implements Queue
{ private int maxSize; // maximum queue size
private
Object[] que; // que is an array
private int
front;
private int
rear;
private int
count; // count of items in queue (queue size)
public
ArrayQueue(int s) // constructor
{ maxSize =
s;
que = new
Object[maxSize];
front = rear
= -1;
count = 0;
}
public void
insert(Object item) // add item at rear of queue
{
if( count ==
maxSize )
{
System.out.println("Queue is Full"); return; }
if(rear ==
maxSize-1 || rear == -1)
{ que[0] =
item;
rear = 0;
if( front ==
-1) front = 0; 36 Lab Manual Data Structures through Java
}
else
que[++rear] = item;
count++; //
update queue size
}
public Object
remove() // delete item from front of queue
{
if( isEmpty()
)
{System.out.println("Queue is
Empty"); return 0; }
Object tmp =
que[front]; // save item to be deleted
que[front] =
null; // make deleted item’s cell empty
if( front ==
rear )
rear = front
= -1;
else if(
front == maxSize-1 ) front = 0;
else front++;
count--; //
less one item from the queue size
return tmp;
}
public Object
peek() // peek at front of the queue
{ return
que[front]; }
public
boolean isEmpty() // true if the queue is empty
{ return
(count == 0); }
public int
size() // current number of items in the queue
{ return
count; }
public void
displayAll()
{
System.out.print("Queue: ");
for( int i =
0; i < maxSize; i++ )
System.out.print( que[i] + " ");
System.out.println();
}
}
Program 17(f): Testing ArrayQueue class
class QueueDemo
{
public static
void main(String[] args)
{
/* queue
holds a max of 5 items */
ArrayQueue q
= new ArrayQueue(5);
Object item;
q.insert('A'); q.insert('B'); q.insert('C');
q.displayAll();
item =
q.remove(); // delete item
System.out.println(item + " is
deleted");
item =
q.remove();
System.out.println(item + " is
deleted");
q.displayAll();
q.insert('D');
// insert 3 more items
q.insert('E');
q.insert('F');
4. Stacks and Queues
37
q.displayAll();
item =
q.remove();
System.out.println(item + " is
deleted");
q.displayAll();
System.out.println("peek(): " +
q.peek());
q.insert('G');
q.displayAll();
System.out.println("Queue size: " +
q.size());
}
}
Output of
this program is as follows:
Queue: A B C null null
A is deleted
B is deleted
Queue: null
null C null null
Queue: F null
C D E
C is deleted
Queue: F null null D E
peek(): D
Queue: F G
null D E
Queue size: 4
Infix to Postfix Conversion
18. Write a java program that reads an infix
expression, converts the expression to postfix form
and then evaluates the postfix expression (use stack
ADT).
Program 18(a) translates an infix expression to a
postfix expression. The main method of the
InfixToPostfix class is toPostfix(). This method
takes “infix” string as an input parameter and
returns “postfix” string. In the process, we use a
stack as a temporary storage. So, instead of writing a
separate program for stack operations, the
InfixToPostfix class uses java.util.Stack class.
Program 18(a): Infix to Postfix Conversion
class InfixToPostfix
{
java.util.Stack<Character> stk =
new
java.util.Stack<Character>();
public String
toPostfix(String infix)
{
infix =
"(" + infix + ")"; // enclose infix expr within parentheses
String
postfix = "";
/* scan the
infix char-by-char until end of string is reached */
for( int i=0;
i<infix.length(); i++)
{
char ch,
item;
ch =
infix.charAt(i);
if(
isOperand(ch) ) // if(ch is an operand), then
postfix =
postfix + ch; // append ch to postfix string 38 Lab Manual Data Structures
through Java
if( ch == '('
) // if(ch is a left-bracket), then
stk.push(ch);
// push onto the stack
if(
isOperator(ch) ) // if(ch is an operator), then
{
item =
stk.pop(); // pop an item from the stack
/* if(item is
an operator), then check the precedence of ch and item*/
if(
isOperator(item) )
{
if(
precedence(item) >= precedence(ch) )
{
stk.push(item);
stk.push(ch);
}
else
{ postfix =
postfix + item;
stk.push(ch);
}
}
else
{
stk.push(item);
stk.push(ch);
}
} // end of
if(isOperator(ch))
if( ch == ')'
)
{
item =
stk.pop();
while( item
!= '(' )
{
postfix =
postfix + item;
item =
stk.pop();
}
}
} // end of
for-loop
return
postfix;
} // end of
toPostfix() method
public
boolean isOperand(char c)
{ return(c
>= 'A' && c <= 'Z'); }
public
boolean isOperator(char c)
{
return(
c=='+' || c=='-' || c=='*' || c=='/' );
}
public int
precedence(char c)
{
int rank = 1;
// rank = 1 for '*’ or '/'
if( c == '+'
|| c == '-' ) rank = 2;
return rank;
}
}
///////////////////////// InfixToPostfixDemo.java
///////////////
class InfixToPostfixDemo
{
public static
void main(String args[])
{ 4. Stacks and Queues
39
InfixToPostfix obj = new InfixToPostfix();
String infix
= "A*(B+C/D)-E";
System.out.println("infix: " + infix
);
System.out.println("postfix:"+obj.toPostfix(infix)
);
}
}
Output of this program is:
infix:
A*(B+C/D)-E
postfix:
ABCD/+*EEvaluation
of postfix expression
One of the most useful characteristics of postfix
expression is that the value of postfix expression can
be computed easily with the aid of a stack. The
components of a postfix expression are processed from
left to right as follows:
Item scanned from
Postfix Expression Action
Operand Push operand onto the stack
Operator Pop the top two operands from the stack,
apply the
operator to them, and evaluate it. Push this result
onto the stack.
This algorithm finds the value of postfix
expression, P. Each character of the expression, P is denoted
by ch. We use a variable stack, which is an array of
integers. Initially stack is empty. The result, tmp1
and tmp2 are integer variables.
Program 18(b)
illustrates the evaluation of postfix expression. The program works for
expressions
that contain only single-digit integers and the four
arithmetic operators. The program uses
java.util.Stack class for creating a stack of
integer values.
Program 18(b): Evaluation of postfix expression
class EvaluatePostfixExpression
{
public static
void main(String args[])
{
String
postfix = "5 6 2 + * 8 4 / -";
java.util.Stack<Integer>stk =
new
java.util.Stack<Integer>();
char ch;
for( int i =
0; i < postfix.length(); i++ )
{
ch =
postfix.charAt(i);
if(
isDigit(ch) )
stk.push( new
Integer(Character.digit(ch,10)));
if(
isOperator(ch) )
{
int tmp1 =
stk.pop();
int tmp2 =
stk.pop(); 40 Lab Manual Data Structures through Java
int result =
evaluate(tmp2, tmp1, ch);
stk.push(result);
}
}
System.out.println("Value of postfix expr
= " + stk.pop());
}
static
boolean isDigit(char c)
{ return( c
>= '0' && c <= '9' ); }
static
boolean isOperator(char c)
{ return(
c=='+' || c=='-' || c=='*' || c=='/' ); }
static int
evaluate(int a, int b, char op)
{ int res =
0;
switch(op)
{
case '+' :
res = (a+b); break;
case '-' :
res = (a-b); break;
case '*' :
res = (a*b); break;
case '/' :
res = (a/b); break;
}
return res;
}
}
Output of this program is: Value of postfix expr =
38
Matching Brackets (Delimiters)
19. Write a Java program that determines whether
parenthetic symbols ( ), { } and [ ] are nested
correctly in a string of characters (use stack ADT).
A stack is used to check for matching the left and
right brackets in an expression. We want to ensure
that the parentheses are nested correctly; that is,
we need to check that (1) there are an equal number of
left and right parentheses, and (2) every right
parenthesis is preceded by a matching left parenthesis.
For example,
the expressions such as [A+(B*C))] or {X*Y+(Z–5} violate condition (1), and
expressions {)A+B(-C} or [(A+B))-(C+D] violate
condition (2).
The Program 19 uses Arraystack to check for matching
left and right brackets: [ ], { }, and ( ) in
an expression. The elements of the stack are
characters. Here, we are concerned about the brackets.
The items of the stack contain only left brackets.
The valid is a boolean variable, which is initially
made false.
The isExpressionValid() method makes use of the
Arraystack class. Notice how easy it is
to reuse this class. All the code you need is in one
place. This is one of the payoffs for object-oriented
programming.
Program 19: Matching left and right brackets in an
expression using Stack
class Expression
{
private
String expression;
Expression(
String str ) // constructor
{ expression
= str; }
public
boolean isExpressionValid() 4. Stacks and Queues
41
{ int n =
expression.length(); // get max size (chars) of expression
ArrayStack
stk = new ArrayStack(n); // create stack
char ch, chx;
// ch: char scanned and chx: char popped
boolean valid
= false;
for(int i =
0; i < n; i++) // get a char until ‘n’ chars are scanned
{
ch =
expression.charAt(i); // get char
if( ch == '['
|| ch == '{' || ch == '(' )
stk.push(ch);
if( ch == ']'
|| ch == '}' || ch == ')' )
{ if(
stk.isEmpty() )
valid =
false;
else
{ chx =
(Character)stk.pop(); // pop a char from stack
if( chx ==
'[' && ch == ']' ) valid = true;
if( chx ==
'{' && ch == '}' ) valid = true;
if( chx ==
'(' && ch == ')' ) valid = true;
}
}
}
if(
!stk.isEmpty() ) // stack not empty
valid =
false;
return valid;
}
}
///////////////////// ExpressionDemo.java
/////////////////////
class ExpressionDemo
{
public static
void main(String[] args)
{
String expr =
“[A+25*{Y*(B+C-X)-K}/D*(E+13)+M]”;
Expression ob
= new Expression(expr);
System.out.println("expression: " +
expr);
if(
ob.isExpressionValid() )
System.out.println("expression is
valid");
else
System.out.println("expression is not
valid");
}
}
Output of this program is:
expression: [A+25*{Y*(B+C-X)-K}/D*(E+13)+M]
expression is
valid
Palindrome
20. Write a Java program that uses both stack and
queue to test whether the given string is a
palindrome.
First the characters are extracted one by one from
the input string and pushed onto the stack. Then they
are popped from the stack and compared with each
character of the given string. It is enough to
compare with first half of the string. Because of
its last-in-first-out characteristic, the stack reverses the
order of the characters. Program 20(a) uses the
java.util.Stack (Refer chapter 10: Stacks).42 Lab Manual Data Structures
through Java
Program 20(a): Testing whether the given string is a
palindrome using stack
import java.util.Stack;
class Palindrome
{
public static void main(String args[])
{
String str =
"MALAYALAM";
if(
isPalindrome(str) )
System.out.println( str + " is a
Palindrome");
else
System.out.println( str + " is not a
Palindrome");
}
static
boolean isPalindrome(String str)
{
Stack<Character> stk = new
Stack<Character>();
for( int i=0;
i < str.length(); i++ )
stk.push(str.charAt(i));
for( int i=0;
i < str.length()/2; i++ )
if(
str.charAt(i) != stk.pop() ) return false;
return true;
}
}
First the characters are extracted one by one from
the input string and inserted into the queue. Then
they are removed from the queue and compared with
each character of the given string (in the reverse
order of the string). It is enough to compare with
second half of the string (of course in the reverse
order). Because of its first-in-first-out
characteristic, the characters are deleted from the queue in the
order of the characters of the string. Program 20(b)
uses the java.util.LinkedList to implement
the queue (Refer chapter 11: Queues).
Program 20(b): Testing whether the given string is a
palindrome using queue
import java.util.LinkedList;
class Palindrome
{
public static
void main(String args[])
{
String str = "RADAR";
if(
isPalindrome(str) )
System.out.println( str + " is a
Palindrome");
else
System.out.println( str + " is not a
Palindrome");
}
static
boolean isPalindrome(String str)
{
LinkedList<Character> que = new
LinkedList<Character>();
int n = str.length(); 4. Stacks and Queues
43
for( int i=0;
i < n; i++ )
que.addLast(str.charAt(i));
for( int
i=n-1; i > n/2; i-- )
if(
str.charAt(i) != que.removeFirst() ) return false;
return true;
}
}
Linked Stack
21. Write Java programs to implement the following
using a singly linked list.
(a) Stack ADT
(b) Queue ADT
Another way to represent a stack is by using a
linked list. A stack can be represented by using nodes of
the linked list. Each node contains two fields: data
(info) and next (link). The data field of each
node contains an item in the stack and the
corresponding next field points to the node containing the
next item in the stack. The next field of the last
node is null – that is, the bottom of the stack. The
top refers to the topmost node (the last item
inserted) in the stack. The empty stack is represented by
setting top to null. Because the way the nodes are
pointing, push and pop operations are easy to
accomplish. Program 21(a) is a complete listing,
demonstrating the push and pop operations of a stack
using singly linked list.
Program 21(a): Linked Implementation of a Stack
class Node
{ int data; // data item
Node next; //
next node in linked-stack
Node( int d )
// constructor
{ data = d; }
// next is automatically set to null
}
class LinkedStack
{
Node top; //
top refers to top-node
Node p; // p
refers to current node
public void
push(int item) // add item onto stack
{
p = new
Node(item); // create new node
p.next = top;
// new node refers to old top
top = p; //
top refers to new node
}
public Node
pop() // remove a node from the stack
{
if( isEmpty()
)
{
System.out.println("Stack is empty");
return null;
}
Node tmp =
top; // tmp saves reference to top node
top =
tmp.next; // now, top refers to next node of old top 44 Lab Manual Data
Structures through Java
return tmp;
// return the popped item
}
public Node
peek() // get top node from the stack, without deleting
{
if( isEmpty()
)
{
System.out.println("Stack is empty");
return null;
}
return top;
}
public void
displayStack()
{
p = top; // p
refers to top
System.out.print("\nContents of Stack: [
");
while( p !=
null ) // start printing from top of stack to bottom of stack
{
System.out.print(p.data + " "); //
print data
p = p.next;
// move to next node
}
System.out.println("]");
}
public
boolean isEmpty() // true if stack is empty
{ return (top
== null); }
}
///////////////////////// LinkedStackDemo.java
/////////////////
class LinkedStackDemo
{
public static
void main(String[] args)
{
LinkedStack
stk = new LinkedStack(); // create stack object
Node item; //
item stores popped node
stk.push(20);
// add 20, 35, 40 to stack
stk.push(35);
stk.push(40);
stk.displayStack(); // print contents of stack
item = stk.pop();
// remove a node from the top and print it
if( item !=
null )
{
System.out.println("Popped item: " +
item.data);
stk.displayStack();
}
stk.push(65);
// insert 65, 70, 75
stk.push(70);
stk.push(75);
stk.displayStack(); // display contents of stack
item =
stk.pop(); // remove a node from the top and display it
if( item !=
null )
{
System.out.println(“Popped item: ” +
item.data);
stk.displayStack();
}
System.out.println(“peek(): ” + stk.peek());//
get top item 4. Stacks and Queues
45
stk.push(90);
// insert 90
stk.displayStack();
}
}
Output from LinkedStack operations program:
Contents of Stack: [ 40 35 20 ]
Popped item: 40
Contents of Stack: [ 35 20 ]
Contents of Stack: [ 75 70 65 35 20 ]
Popped item: 75
peek(): 70
Contents of Stack: [ 70 65 35 20 ]
Contents of
Stack: [ 90 70 65 35 20 ]
No comments:
Post a Comment