Class 42: Introduction to Linear Structures

Held Monday, November 13, 2000

Summary

Today we move on to a new class of abstract data types, the so-called linear structures. In some sense, linear structures are simplified lists.

Notes

• Are there any questions on homework 4?
  • Yes, your add methods can be O(n) when you expand the array.
• How are the readings in Bailey going?
• When do you want to have the next take-home exam due? (I'll distribute it before Thanksgiving, but it may cover stuff we do after Thanksgiving.)
  • I'll be gone Nov. 30 through December 3, so I'd prefer to have it due on Nov. 29th (on the off chance that I can grade on the plane).
  • Short calendar:

    Su Mo Tu We Th Fr Sa 
    12 13 14 15 16 17 18   November
    19 20 21 22 23 24 25   Turkey week
    26 27 28 29 30  1  2   December
     3  4  5  6  7  8  9   Last week of classes
    10 11 12 13 14 15 16   Finals week
    

• We'll be having our first set of candidates visit in the next few weeks (the two weeks after Thanksgiving). These are folks who managed to get all the materials in by the early deadline and who sounded pretty good on the phone.
  • Yes, we're very excited about some of them.
  • Yes, there's a chance that we'll also see some very good people in our future rounds.

Overview

• About linear structures.
• Common linear structures:
  • Stack
  • Queue
  • Priority queue
  • Dequeue

Linear Structures

• Believe it or not, a problem with some kinds of lists is that they provide just too many options.
  • In ordered lists, you might put at and retrieve elements from the front, back, or even middle of the list.
  • Should you use simple lists, sequenced lists, sorted lists, indexed lists, vectors, or what?
• This multiplicity leads to some difficulties.
  • Implementation can be more difficult, as we've already seen.
  • Clients may find it difficult to use lists, as they must consider the interrelationship of the different functions.
• Many uses of lists can be simplified to three or four basic operations:
  • add an element
  • get an element, removing it from the structure
  • check if the structure is empty
  • check if the structure is full (for array-based implementations)
• Some also add a peek method which looks at the next element to be removed.
• Structures that support these three or four operations are often called linear structures.
• We can think of this in terms of a typical collection of tasks. You add tasks as they come up. Whenever you have free time, you pick another task to do.
• A policy determines the relationship between objects being added and objects being removed.
• A first-in, first-out (FIFO) policy says that objects are removed in the order that they're put in. Linear structures with a FIFO policy are typically called queues.
• A last-in, first-out (LIFO) policy says that objects are removed in the opposite order that they're put in (so the object most recently added is the next one to be removed). Linear structures with a LIFO policy are typically called stacks
• A prioritized policy says that are objects are removed in a highest-priority-first order. Linear structures that remove based on priority are called priority queues.
• Other policies are also possible.

Detour: Naming Methods

• We call our basic methods add and get.
• Good design would suggest that every linear structure use the same names for these basic operations.
• Unfortunately, when these structures were first designed, no one had thought about the commonality. Hence, the ``standard'' names for operations in linear structures differ from structure to structure.

Stacks

• Stacks are linear structures that use the LIFO policy.
• They are similar to the stacks of dishes that you may see in cafeterias. As each dish is cleaned, it is added to the top of the stack. As customers need dishes, they remove them from the top of the stack.
• They are also similar to the stacks used to implement function calls in typical languages.
• The standard names for stack operations are
  • push(Object o) -- add an element to the top of the stack
  • Object pop() -- remove an element from the top of the stack
  • Object peek() -- look at the element on the top of the stack
  • boolean isEmpty() -- check if the stack is empty
• There are many uses for stacks, and we'll keep coming back to them as the term progresses. These uses include:
  • Providing support for recursive procedure calls
  • Searching structures
  • Computation
• One interesting aspect of stacks is that push and pop are clear inverses. If you push an element and then pop, the stack ends up the same. In other policies, this may not be the case.
• There are, of course, many ways to implement stacks. We can use arrays, lists, nodes, ....

Queues

• Often, linear structures are used to organize tasks to be done (e.g., places in a maze to look at, potential solutions to a programming problem, ...).
• One problem with stacks is that the first things that are added to the stack are the last removed, so if we keep finding new things to try, we'll never try the first ones.
• To provide a sense of fairness, we might instead require that the earlier tasks are done first.
• Queues are first-in first-out (FIFO) linear structures. They are similar to lines at a bank teller or elsewhere.
• The main methods in queues are
  • enqueue(Object o) -- add an object to the back of the queue
  • Object dequeue() -- remove an object from the front of the queue
  • Object front() -- determine what's at the front of the queue, but don't remove it.
  • boolean empty() -- are there any elements in the queue?
• Like stacks, queues are used for a variety of purposes.
• Like stacks, queues can be implemented in multiple ways.

Priority Queues

• We might further refine our sense of ``queue'' by adding a priority to the elements of the queue. Rather than using FIFO, we'll now use ``lowest/highest priority first''.
  • Linear structures that use priority in choosing the next element are priority queues.
• Are priority queues queues?
  • No, in the sense that many elements do not follow a FIFO ordering.
  • Yes, in the sense that all elements of equal priority are expected to be returned in a FIFO ordering.
  • It is likely the second observation that led to the naming.

Doubly-Ended Queues

• In some odd cases, it may make sense to add elements to or remove elements from both the front and back of the queue.
• Queues that support this extension are called doubly-ended queues or simply dequeues (isn't that a wonderful name conflict with the operation?)
• In effect, these are a kind of ordered list, but without cursors.
• Note that we cannot have dequeues match the three/four basic operations of linear structures.
• Note also that dequeues almost nearly match our basic list model (except that you cannot iterate them).