CS210 ALGORITHMS & DATA
STRUCTURES I
LABORATORY 3
14/10/05
Mr. T. Lysaght
QUEUE DATA STRUCTURE
The purpose of this
Laboratory session is the implementation of the QUEUE data structure using
Arrays and Circular ArrayLists.
ArrayQueue (int size)
// Sets the size of the stack
and initializes instance variables
Enquque (int S)
// Add an element to the back of
the queue (increment back and currentsize)
Dequque()
// remove the front element of the queue (increment front and decrement
currentsize)
getFront()
// Return the front element of the queue
print()
//prints the queue front front to back
IsEmpty()
//Returns True if the queue is empty
IsFull() //
Return true if queue is full
//
Currentsize==Maxsize
MakeEmpty()
//front =0, back= -1, Currentsize = 0
The
instance variables in the class are:
private int Maxsize // the capacity of the queue or
size of the array
private int Currentsize // the current size of the
queue or number of elements in the queue
private int front, back // index of front and back of
queue
private int [] Qarray; // the array
Write a Tester program to test the
stack program.
i.
Push 4
integers onto the queue
ii.
Print
the front element of the queue.
iii.
Remove
one element. Print the front element
and then print the complete queue.
iv.
Empty
the queue. Attempt to print the front
element.
2.
Implement
the above queue program using a circular array implemented as an
ArrayList. Implement the ArrayList
queue class, CircularArrayListQueue, using ArrayList methods. Use method add() to implement Enqueue, remove() to implement Dequeue, get() to implement getFront. Include methods IncrementBack and
IncrementFront to implement wrapround of back and front in the circular array.
private void IncrementBack()
private void IncrementFront()
Note:
It may be necessary to have a similar method to decrement back with the
ArrayList implementation.
private void
DecrementBack()
Use
any other ArrayList methods where needed e.g., size(). Initialize the empty queue with:
front=0;
back=Maxsize-1;
Use the generalised for loop where appropriate.
3.
Use
the ArrayStack Class and the CircleArrayListQueue classes to test whether a
string is a palindrome e.g., “{ { { } } }”, or abababa. Store the strings
initially in a stack and a queue. The
first character in the string is the front of the queue and the last character
in the string is the top of the stack.