ICOM 4035 – Data Structures

Fall 2007

 

Laboratory 5: Stacks, Queues and Priority Queues

 

1.    Objectives

 

  1. Understand the usage of Queues.
  2. Understand the usage of Stacks.
  3. Compare them to the LinkedList.
  4. Implement algorithms using Stacks and Queues.
  5. Understand the structure of a priority queue.
  6. Compare priority queues to studied data structures.
  7. Use priority queues in some applications.

 

2.    Overview

 

Just like LinkedList there are some other data structures to store objects in an Object Oriented programming language such as Java. In this laboratory you will focus on two well known data structures: the queue and the stack. These two have a similar behavior since one can only access the data at one of the ends of them.

 

In the case of the Stack which uses a LIFO (last in first out) the data is stored at one end of the structure and when data is to be drawn the one chosen is the last one stored. That is, if one implements the stack as a list of single nodes then the data would be inserted at the beginning of the list and extracted from the first node at the list. This implementation makes the Stack have the following method execution times:

 

Method Name

Description

Execution Time

size

Returns the number of elements in a Stack.

O(1)

isEmpty

Returns true if there are no elements in the Stack.

O(1)

top

Returns the element at the top of the Stack.

O(1)

push

Inserts a new element in the Stack.

O(1)

pop

Removes the top element from the Stack and returns it.

O(1)

 

On the other hand the Queue uses a FIFO (first in first out) policy. This data structure compares to a line at store where the first person to be in the line is the first one to be serviced and any other people arriving have to stay at the end of the line. Thus when implementing a Queue, it is convenient to have knowledge of who are the first element and the last element in it. If these two references are used then the Queue has the following method execution times:

 

Method Name

Description

Execution Time

size

Returns the number of elements in a Queue.

O(1)

isEmpty

Returns true if there are no elements in the Queue.

O(1)

front

Returns the first element in the Queue.

O(1)

enqueue

Inserts a new element at the end of the Queue.

O(1)

dequeue

Removes the first element from the Queue and returns it.

O(1)

 

Although these two data structures can’t access elements in the middle of it as LinkedLists can, they are very useful in many applications that observe their behavior since as you can see all of their methods are O(1), making the code much more faster and efficient.

 

Now we consider a special structure that can be seen as a Queue implemented with a SortedList. This structure is known as the PriorityQueue. It stores the data sorted according to a value known as the key of the entry. This key doesn’t have to be unique to the entry but it does give the entry the position where it will be inserted inside of the queue.

 

When we want to extract one element from the queue we always get the one with the highest priority (typically lowest key value) first. The structure however may also have the potential to change the key value to prevent the application from reaching a lock state.

 

Elements inside of this queue must be comparable in order for the queue to be able to manage them using the compareTo method. In contrast to a normal Queue the PriorityQueue has the following execution times:

 

Method Name

Description

Execution Time

size

Returns the number of elements in a Queue.

O(1)

isEmpty

Returns true if there are no elements in the Queue.

O(1)

front

Returns the first element in the Queue.

O(1)

enqueue

Inserts a new element at the end of the Queue.

O(n)

dequeue

Removes the first element from the Queue and returns it.

O(1)

 

 

 

3.    Practice

 

For this laboratory you will need to download the file hierarchy by clicking here. When you download these files you must work on the file named lab5.java inside of the package testers. Work on the two empty methods after main following these specifications.

 

 

 

public static int[] convertToBinary(int number):

converts a positive integer into binary number where int[0] is most significant bit and int[length-1] is least significant bit. You must use an array of integers and a stack in this method.

 

public static <E> E MostRecent(Queue<E> queue)

this method returns the last element entered into a queue. You may only use the queue passed as parameter and the stack provided to you to find these element. Remember that the queue must be kept the same at the end of the execution.