Home Previous Next

CSC205::Lecture Note::Week 06
Assignments | Code | Handouts | Resources | Email Thurman | Tweets::@compufoo
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

Overview Assignment(s)[program] #WoodallNumbers [due 3/11/2017]

Code CloneableEG.java | Memory.java | MultiArrays.java | TwoDimensionalArrays.java | BYTES.java | ThreeDimensionalArray.java
[moved to next week] Main.java | Stack.java | ParenChecker.java | Stack2.java | Queue.java | FootNotes.java (footnotes.in.txt)
Q.java | TestQ.java | PriorityQueue.java


Lists

A  list  is a linear data structure whose components can only be accessed sequentially, one after another.

The first item is a list is called the  head  or  front  and the last item is called the  tail ,  back  or  end.

Lists have the following features:

List operations include:

GDT::Java::Code::GoofyIntList.java

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos}


Sets

A set is a basic building block of mathematics and is a collection of objects (e.g. integers, real numbers, boolean values, geometric points, strings, records, etc.).

The objects of a set are called elements (or members).

A set the following properties:

Example of sets:

The following operations are performed on a set:

An array (i.e. vector) can be used to store a set.

A class that is used to represent a set could have the following instance methods:

   Set();
   Set(int capacity);
   boolean isMember(Object element);
   boolean isEmpty();
   boolean isSubset(Set other);
   int size();
   Set union(Set other);
   Set intersection(Set other);
   Set difference(Set other);
   void add(Object element);
   void remove(Object element);
   void clear();

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos}


Stacks

A  stack  is a data structure in which all access is restricted to the most-recently-inserted elements (LIFO: Last-In-First-Out).

My favorite real world example of a stack is a salad bar. Typically, at the start of the salad bar line is a stack of plates and normally you take the top-most plate (unless it is dirty or has some type of foreign looking object on it, in which case you dig down and take a plate from somewhere lower in the stack [atypical stack behavior]). In actualality, a stack is the wrong way to store plates at a salad bar because of the following scenario: The dishwasher cleans the dirty plates, brings them out front to the salad bar, and  pushes  them on top of the stack -- now John Q. Customer comes up and is stuck using a hot plate.

A stack has three natural operations: insert, delete, and find; but in stack terminology these operations are called  push ,  pop  and  top .

Elements are inserted onto a stack by using a push operation.

Elements are deleted from a stack by using a pop operation.

The most-recently inserted element can be examined by using a top operation.

Stacks are heavily used in system software (e.g. compilers). A stack can be used to check for unbalanced symbols (e.g. (), {}, []). Example algorithm:

  1. create an empty stack
  2. read symbols until EOF
    1. if the symbol is an opening symbol, push it onto the stack
    2. if the symbol is a closing symbol and the stack is empty, then report an error
    3. otherwise, pop the stack (if symbol popped is not the corresponding opening symbol, then report an error)
  3. at EOF, if stack is *not* empty, then report an error

A stack is used to implement function (method) calls in most languages. For example in C++, when a function is called, memory for parameters and locally defined variables is allocated from the stack. When the function returns, the memory for the parameters and local variables is de-allocated from the stack. In addition, "jump" information and return value data is stored on the stack.

Stacks are also used in the evaluation of expressions (e.g. operator precedence parsing).

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos}


Queues

A  queue  is a data structure in which all access is restricted to the least-recently-inserted elements (FIFO: First-In-First-Out).

Operations are:

Examples of a queue: buffered input and a line printer spooler.

Another queue example: message queues.

{TopOfPage} {Oracle.com::API Specification | Tutorial} {Derek Banas Videos}


Home Previous Next