Accessing Data       

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. 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 a file 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") then 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:

   int count = 0;
   do
   {  String data = input("Data:");
      list[count] = data;
      count = count + 1;
   } while (!name.equals("xxx"));

Now the words can be retrieved (used) in any order, because arrays are Random Access.

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 - LIFO and FIFO

• 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, if 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.
    
• Polling - In some systems, the CPU doesn't wait for an interrupt.  Instead, it checks periodically (e.g. every second) whether the peripheral device needs attention.  It's called polling because it is similar to asking people on the street what they think.  Polling is more common in small, simple systems like dedicated devices checking sensors (medical monitors, air-conditioning, traffic sensors, etc).  This makes the sensors simpler and cheaper.

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. 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 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)