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:



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

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)

Queue (FIFO)

Deque (pronounced "Deck")
-
implements all the operations from both a queue and stack, where we recognize that Pop and Dequeue are actually the same




ADT - Abstract data Structure

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 Stacks

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

Programming Queues

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:

  



Handling Overflow and Underflow Errors

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:

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.




This program demonstrates the basic functions of a Queue.




Get a copy of the QueueTest program.

  1. 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?

  2.  

    Add the underflow prevention code mentioned above, and make it work correclty.
    This means that an underflow does not cause any problems.

  3.  

    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.

  4.  

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

  5.  

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

  6.  

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

  7.  

    Finish all these tasks, and prepare for a QUIZ in the next HL meeting. There will be
    questions about this set of notes.