INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS202 : DATA STRUCTURES

LAB  #04 :  Stacks and Queues

Objectives:

1.       Studying the implementation of a stack as a container whose underlying data structure is a singly-linked list.

2.       Studying the implementation of a queue as a container whose underlying data structure is a singly-linked list.

3.    Implementing an algorithm to check whether a given valid infix expression is correctly parathensesized or not.

4.       Implementing an iterative algorithm to evaluate a valid postfix expression.

5.    Implementing a priority queue using a singly-linked list.

1.  Downloadables:

Download lab04.zip and unzip it in the ics202 main folder. WinZip will automatically create a subfolder lab04.  After unzipping, you should have the following files:

Under the ics202 package:

• Stack.java

• Queue.java

• QueueAsLinkedList.java

• StackAsLinkedList.java

Under the ics202.lab04 package:

• PriorityQueueAsLinkedList.java

2.  Task 1:

Open each of the above files and study it carefully to make sure you understand what it is doing.

3.  Task 2:

        Write a java program which uses the class StackAsLinkedList.java to check whether a given valid infix expression is correctly parathensesized

        or not.

        Sample input/output:       

(5*3)+(4/(6-2))	correct
(3-4/(4+4)	not correct
))((	not correct

4.  Task 3:

      Assuming that a postfix expression consists of operands of single digits (0,1, .., 9), the binary operators *, /, %, +, and -,  and possibly white-space characters.   An algorithm to evaluate the postfix expression is given below:

Create an empty stack

Read postfix expression as a string ;

while(there are more tokens in the string){

     if(current token is an operand)

        push token in the stack;

     else if(current token is an operator oprt ){

         operand1 = pop stack;

         operand2 = pop stack;

         result = operand2 oprt operand1;

         push result in the stack;

      }

  }

 pop result from the stack and print it;

      Write a Java program that prompts for, and reads a postfix expression.  It then uses the above algorithm and an instance of StackAsLinkedList to evaluate and print the value of the postfix expression. You may assume that the postfix expression consists of single-digit operands (i.e., 0, 1, 2, . . ., 9), the binary operators *, /, %, +, and -, and possibly white-space characters

        Sample input/ output:       

5.  Task 4:

A normal queue is a FIFO data structure; elements are dequeued from the front of the queue and enqueued at the end of the queue. A priority queue is a queue in which elements are also dequeued from the front of the queue; but they are enqueued according to their associated priorities. A higher priority item is always enqueued before a lower priority element. An element that has the same priority as one or more elements in the queue is enqueued after all the elements with that priority.

(a)     Complete the implementation of the PriorityQueueAsLinkedList class in the ics202.lab04 package by overriding the enqueue method.

(b)  What is the big-O complexity of the enqueue method ?

(c)   Patients in a hospital are assigned priorities to see a doctor. Write a test program, TestPriorityQueue in the ics202.lab04 package so that:

1.       For each patient: It prompts for and reads the patient ID and the priority of the patient (an integer between 1 and 5) to see a doctor.

2.       Initializes a priority queue with the data that is read. Each patient object is an Association object that contains the priority as the key, and the ID as the associated value.

3.       Displays the contents of the priority queue using the PrintingVisitor package.