INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM
ICS202 : DATA STRUCTURES
LAB #04 : Stacks and Queues
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.
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
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.
Sample input/ output:
postfix expression |
value |
5 9
+ 2 * 6 5
* + |
58 |
6 2 + 5
8 4 / - * |
24 |
6 2
+ 5 * 8 4
/ - |
38 |
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.