Data Structures

Stacks

A stack is a Last In First Out (LIFO) abstract data type, in which items are added to the top and removed from the top, like a stack of books or plates. It supports the following operations:

  • push – puts an item on top of the stack
  • pop – removes an item from the stack
  • peek – returns a copy of the item on top of the stack without removing it
  • isEmpty – returns true if the stack is empty
  • isFull – returns true if the stack is full

A simple static stack (i.e. fixed in size) could be implemented using an array in a high level language.

An index variable can be used as a pointer to the top of the stack.

Once a programmer has created the stack abstract data type, they can use it without worrying about how the stack has actually been implemented. Hence the name Abstract Data Type, because the details of the implementation have been abstracted away, and the stack can simply be used through use of the pop, push etc operations.

Activity 1

  • In a new BlueJ project, create a class called Stack
  • Create an array of strings called stack, with 5 elements
  • Create an int variable called stackPtr
  • Create a method called push that accepts a String argument and returns a boolean value which is true if the item was successfully added to the stack or false if it wasn’t
  • Create a method called pop which removes the item from the top of the stack and returns it, or returns null if the stack is empty.
  • Create methods for isFull and isEmpty.
  • Create a method for peek
  • Test all your code, including a test to see what happens if you try to push an item onto an already full stack

Queues

A queue is another ADT, similar to a stack but in which items are added to the rear and removed from the front, described as First In First Out (FIFO) .

It supports the following operations:

  • enqueue – puts an item into the queue
  • dequeue – removes an item from the queue
  • isEmpty – returns true if the queue is empty
  • isFull – returns true if the queue is full

A primitive queue can again be created using an array with a fixed number of elements. This time there will be two pointers needed:

  • frontPointer – showing where the front of the queue is, and therefore where items should be removed from
  • rearPointer – showing where the back of the queue is, and therefore where new items should be added.

Activity 2

  • In the same project as before, create another class this time called SimpleQueue.
  • Once again create a String array of 5 elements, but call it queue
  • Create int variables for front and rear pointers.
  • Create an enqueue method that accepts a String argument and adds it to the queue
  • Create a dequeue method that returns a String from the queue
  • Test all your code, including a test to see what happens if you try to queue an item in an already full queue, or dequeue an item from an empty queue

Circular queues

The simple queue used in the previous activity is not particularly useful as once five items have been added, no more items can be added even when items have been removed from the queue. A more useful queue would make use of the locations freed up once they have been removed from the queue, and would go back to the beginning of the array and carry on from there. As long as the front of the queue doesn’t overwrite the back of the queue this can work well.

In addition to the front and rear pointers, will will need to keep track of the number of items in the queue. This will allow us to know whether the queue is full or empty.

A useful trick is to use modulo arithmetic to make the pointers “wrap around” back to the beginning without using if statements.

// this code will output the values 0 to 3 forever
while (true){
  pointer = pointer + 1;
  pointer = pointer mod 4;
  System.out.println(pointer);
}

Activity 3

  • Create a new class called CircularQueue
  • Once again create a String array of 5 elements and call it queue
  • Create int variables for front and rear pointers
  • Create another in variable called size which is updated everytime an item is enqueued or dequeued
  • Create an enqueue method that accepts a String argument and adds it to a circular queue, updating pointers and the size variable as needed
  • Create a dequeue method that returns a String from the queue, updating pointers and the size variable as needed
  • Create methods for isEmpty and isFull
  • Test your code by adding 5 items, removing 3, and then adding another 3 and removing the remaining items from the queue.

Priority Queues

A priority queue works as a normal queue does, but items can be inserted into any position in the queue, not just at the back of the queue. In this way, higher priority items can be dealt with earlier than if they had just been added to the rear of the queue as normal.

Think of the triage process that takes places in hospital accident and emergency departments:

  • Life threatening injury – top priority so dealt with first
  • Patient in serious pain but not life threatening – medium priority so dealt with next
  • All other non life threatening injuries – dealt with last

Items will still be removed from the front of the queue, but because we could add items anywhere, it is tricky to implement this with an array. It is better to use a list abstract data type, to which items can be added, removed, and inserted at a particular position. This ADT is dynamic, i.e. it can grow or shrink in size.

In Java this can be done with ArrayLists.

import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    ArrayList<String> stuff = new ArrayList<String>();
    stuff.add("Stacks");
    stuff.add("Queues");
    stuff.add("Lists");
    
    System.out.println( stuff.get(0) );
    System.out.println( stuff.size() );
    System.out.println( stuff.remove(0) );
    System.out.println( stuff );

  }
}

Uses for Stacks and Queues

Both ADTs can be used for a variety of tasks:

  • Stacks: backtracking, undo, traversing trees, evaluating expressions in parse trees
  • Queues: scheduling, buffering, traversing trees

Activity 4

  • Create a new class called MusicPlayer
  • Allow the user to enter a song name at the keyboard, and add the song to a queue
  • If the user enters the string “PLAY”,
    • display a message saying “Playing …” and the name of the song that is first in the queue
    • remove the song from the queue
  • Keep looping around until the user enters “QUIT”
  • If the user attempts to play a song and the queue is empty, display the message “The queue is empty. Add some songs to play.”
  • Extension: Add a command called TOP which is followed by the name of a song. It should insert this song at the front of the queue
  • Extension: Add a “SHOW” command which shows all the songs currently in the queue, in the order that they will play

Knowledge Check

  • What is the difference between a stack and a queue?
  • What do we mean by a static data structure?
  • Describe the operation of a circular queue.
  • How are items inserted and removed from a priority queue?
  • What operations might a list data type have, and how does this differ from a standard array?
  • What uses might stacks and queues have in programs?