Data Structures and Access Methods

Random Access

Random Access does not mean unpredictable or without order. Random Access means that the position of an item does not effect the speed of access. Hard-disk drives, CD-ROM drives, and RAM (Random Access Memory) or all random-access devices. On a hard-disk, a file might be stored near the center of the disk, or near the outside. But the read/write head moves very quickly to the correct track, so the position is not significant. In RAM, any storage location returns data in the same amount of time, regardless of its address.

Serial (Sequential) Access

Tape drives (e.g. cassettes) are NOT random-access devices. To access data at the end of the tape, either the tape drive must read through all the data, from beginning to end, or it must "fast forward" to the correct position. In either case, it takes a lot longer to read data at the end of the tape than reading data at the beginning.

Text-Files

A text file is a list of words or lines of text, usually stored on a disk-drive. Although the disk-drive is a random-access device, the words in the text-file must be accessed sequentially, for example:

search = input("What name do you want to find?");

open text-file ;

do
{
name = input();
if name.equals(search) { output("Found it"); }
} while (!name.equals("xxx") and !name.equals(search))

if ( name.equals("xxx") ) { output("Not found"); }

If the text-file contains a million names, in alphabetical order, then it takes a lot longer to find "Zeke" (at the end) than to find "Abraham" (at the beginning).
Printing the file in reverse order (from Z to A) would take a very long time, as it is not possible to read backward. Instead, every single item must be accessed by starting at the beginning again.

Arrays

Arrays are random-access structures. Arrays are stored in RAM, making it quick and easy to "access" any position in the array. There is no difference in access speed between the following two commands:

     names[1] = "Alex"

     names[1000000] = "Zeke"

Printing an array in reverse order is no problem, and runs just as fast as printing forward:

for(int x=1000000; x > 0; x=x-1) 
{ output(names[x]);}

Lists

An array can be used to store a list of words or commands. Normally the entries are copied sequentially into the array, like this:

   count = 0
   do
      data = input()
      list[count] = data
      count = count + 1
   while !name.equals("xxx")

Now the words can be retrieved (used) in any order.

FIFO

FIFO stands for First In, First Out. This means data is used in the same order that it was saved. This is like a queue in a cafeteria. In fact, the term queue is a technical computer science term for a list of data used in the same sequential order as it was received.

LIFO

LIFO stands for Last In, First Out. This means data is processed in reverse order - the last item received is the first to be processed. This is similar to a stack of work, where each new assignment is laid on top of the stack. Then the top item (received last) is taken off the top of the stack and processed first. Stack is the technical computer science term for LIFO type processing. This is useful for handling interrupts, where the most recent signal demands the immediate attention of the processor.

Examples

Cafeteria - In a narrow line in a cafeteria, customers enter at one end and stand in a queue. The are served when they get to the front of the queue, in FIFO order.

Bus Passengers - A bus has a single entrance at the front. Passengers enter and move to the back of the bus. When the exit, the passengers at the front must exit first, in LIFO order - Last In, First Out.

Restaurants - Customers enter a restaurant, sit at a table, and wait to be served. The position of the table doesn't affect the service. If all the waiters are efficient, the service should be basically FIFO (e.g. fair), but this isn't necessary, and doesn't always happen. Here the service is random-access - e.g. no particular order is required.

Print Queue - A network allows many PCs to use a single printer. Each print job (document) arrives at a server and is stored temporarily in a queue. When the printer finishes with one job, it removes another job from the queue. Using queue-oriented access (FIFO), the first print job entered in the queue is the first to be printed. People consider this "fair".

Interrupts - Computers use interrupt signals when a peripheral device (e.g. printer) needs attention from the CPU (PC). A PC might receive a request from a printer to send the next print job. Before it can start, it might receive another interrupt from the modem to receive some data from the interrupt. The PC normally stops working on the print request and services the modem request immediately - e.g. LIFO.

Priorities

Some jobs are more urgent or more important than others. In a hospital, the emergency room patients are more urgent than those who already have a bed. In computer systems, a request from a modem to receive data is more urgent than a request from a printer - the printer can wait, but the modem must keep pace with a web-server somewhere else. To ensure that an urgent job gets attention before a less urgent job, computer systems can assign priority codes to devices - e.g. 99 for a high priority, 0 for a low priority. Prioritized data storage can be implemented in a deque (pronounced “deck”). A deque (double ended queue) works like a queue at the back end, and like a stack at the front end. If a request arrives with a high priority (higher than the item at the front of the queue) it will be "pushed" onto the front, and processed next. This is like permitting a teacher to push in at the front of the cafeteria queue, ahead of the students.

Standard Structures and Operations

Stack (LIFO)

Initialize - start with the stack empty

Push - add a new item at the top of the stack

Pop - remove an item from the top of the stack (and process it)

Queue (FIFO)

Initialize - start with the queue empty

Enqueue - enter the queue (at the back)

Dequeue - leave the queue (at the front, after waiting)

Deque (pronounced "Deck")

implements all the operations from both a queue and stack, where we recognize that Pop and Dequeue are actually the same

Initialize - start with an empty list

Enqueue - join the back of the queue

Push - join at the front of the queue

Dequeue - remove and process the item from the front of the queue (same as Pop)

ADT - Abstract Data Structures

Stacks, Queues, and Deques are examples of Abstract Data Structures - they describe some general concepts which can be applied in a variety of situations. For example, it is possible to implement a queue by storing data in a text-file, or by storing it in an array. The file could be stored on a disk-drive, or a tape, or some other storage device. The data might be names, or dates, or e-mail addresses, or anything else. So the requirements for the ADT are abstract - that is, general rather than specific.

Programming ADTs

Stacks Operations

A stack can easily be stored in an array, with an integer variable TOP which tells where the stack ends. Like this:

int top = 0; 
String[] stack = new String[100];

public void initialize()}
{ top = 0; }

public void push(String newItem)
{ top = top + 1;
  stack[top] = newItem;
}

public String pop()
{ String item = stack[top];
  top = top - 1;
  return item;
}

Queue Operations

A queue is a bit more complicated to program than a stack. It needs to keep track of where the front of the queue is, as well as the back. Like this:

      int front = 0;

int back = 0;
String[] queue = new String[100];
public void initialize()
{ front = 0;
  back = 0;
}

public void enqueue(String newItem)
{ queue[back] = newItem;
  back = back + 1;
}

public String dequeue()
{ String item = queue[front];
  front = front + 1;
  return item;
}

Handling Errors - Overflow and Underflow

Usually printers are sitting around doing nothing. That means there is no data in the print-queue. After printing the last job in the queue, an attempt to dequeue the next job causes an underflow - that means there is no more data, so the dequeue operation fails. The command "front=front+1" doesn't cause an arithmetic error, but the data in position [front] is actually meaningless. So the dequeue method should not return anything, except possibly an error code. Study the following sequence of queue operations:

Task-> Cell #	#1 Init	#2 EnQ ("Al")	#3 EnQ ("Bob")	#4 DeQ	#5 EnQ ("Cho")	#6 DeQ	#7 DeQ	#8 DeQ
0	front, back	[Al] front	[Al] front
1		back	[Bob]	[Bob] front	[Bob] front
2			back	back	[Cho]	[Cho] front
3					back	back	front, back	back
4								front

After dequeue removes "Cho", front and back are both equal to 3. This means there is actually no data in the queue. Now a deQueue command will return the contents of queue[3], and increase front to 4. But this is nonsense.

This underflow situation must be prevented (handled), by adding an if... command to prevent the problem. Something like the following:

public String dequeue() 
{ if (front<back)
  { String item = queue[front];
    front = front + 1;
    return item;
  }
  else
  { return "***"; }         //  *** represents an error situation //
}

As the program continues running, handling more and more data, we notice that the variables front and back continue to increase. If queue is an array of 100 cells, front and back will eventually become larger than 100, causing an overflow error. This will actually cause the program to crash, so it must be prevented. It is not quite as simple as handling the underflow error. Once this happens, the program must either shut down, or front and back must be reset to start over at 0. But this won't be simple if back reaches 100 when there is still data in the queue.

Queue Program

This program demonstrates the basic functions of a Queue. It contains no error-handling, so it is just a prototype.

import java.awt.*;
import java.awt.event.*;

public class QueueTest extends EasyApp
{ public static void main(String[] args)
  { new QueueTest(); }

  //--- Global Variables for the Queue ---
  int front = 0;
  int back = 0;
  String[] queue = new String[100];

  //--- Controls - added to form ------
  Button bEnq = addButton("Enqueue",40,50,70,20,this);
  Button bDeq = addButton("Dequeue",40,80,70,20,this);
  Button bCheck = addButton("Check",40,110,70,20,this);
  Button bQuit = addButton("Quit",40,140,70,20,this);

  public QueueTest()
  //--- Constructor - Adjust controls at start ---
  { bQuit.setBackground(Color.red);
    setBounds(0,0,150,200);
    setVisible(true);
  }

  public void actions(Object source, String command)
  //--- Perform actions when buttons are clicked ---
  {
    if (source == bQuit)
    { System.exit(0);
    }
    else if (source == bEnq)
    { String name = input("Add a name:");
      enqueue(name);
    }
    else if (source == bDeq)
    { String name = dequeue();
      output(name);
    }
    else if (source == bCheck)
    { output("Current pointers :" +
             "\n front = " + front +
             "\n back = " + back);
    }
  }

  public void initialize()
  { front = 0;
    back = 0;
  }

  public void enqueue(String newItem)
  { queue[back] = newItem;
    back = back + 1;
  }

  public String dequeue()
  { String item = queue[front];
    front = front + 1;
    return item;
  }
}

Practice Programming

Get a copy of the QueueTest program.

Run the program, and try typing in the sequence of items shown in the table above.
What happens when the Queue "underflows"? Does the program crash?
Now try to Enqueue a new item AFTER the underflow occurs. What does the Dequeue do now?
Add the underflow prevention code mentioned above, and make it work correclty.
This means that an underflow does not cause any problems.
Change the entire program so that it implements a STACK instead of a QUEUE.
Use the same code shown above if you wish. Otherwise, write your own code.
Add error checking code to prevent and underflow in the STACK program.
This is simpler than a queue - here an underflow occurs if (TOP < 1).
Change the STACK program so that it only has 10 cells in the stack, instead of 100.
Add items until an OVERFLOW occurs (9 or 10 or 11 items).
Now add some code to prevent an overflow. This means that new items cannot be
pushed onto the stack when it already contains 10 items (or is it 9?).
Finish all these tasks, and prepare for a QUIZ in the next HL meeting. There will be
questions about this set of notes.