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.

  1. Design a Queue Class, ArrayQueue, to implement the operations of the Queue data structure using an array.  Implement the class using the following methods:

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.