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

• [Pi Day 1-Point Extra Credit] Write gotopi.cpp in Java.
• Notes (posted week #8)
• The set data structure.
• The stack data structure.
• The queue data structure. {priority queue}
• BigOCheatSheet.com::Know Thy Complexities!

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:

• all elements of a set belong to some universe
• any object of the universe is either in a set or it is not
• there is no particular ordering of elements within a set

Example of sets:

• a set of classes that a student it taking
• a set of email addresses in an adress book
• a set of prime numbers

The following operations are performed on a set:

• construct (i.e. define/create/instantiate) a set
• check to see if an object is a member of a set
• test if a set is empty
• get the cardinality (size of a set; number of elements/members)
• check if set A is included in set B (if so, then A is subset of B and B is superset of A)
• determine union of two sets (all elements appearing in A or B)
• determine intersection of two sets (all elements appearing in A and B)
• difference between to sets (all elements of set A not in set B -- notation: A - B)
• add an object to a set
• remove an object from a set
• clear all objects from 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} {Data Structure Visualizations}

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} {Data Structure Visualizations}

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:

• enqueue -- insert at the back of the line (append)
• dequeue -- remove from the front of the line
• front -- access item from front of the line

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} {Data Structure Visualizations}

Priority Queues

A  priority queue  allows the highest priority element to be removed from a queue even though it may not be the "oldest."

Real world example of a priority queue: You go to a restaurant with a friend that has a wait. There are a number of queues: a queue for two person table, a queue for a four person table, and a queue for large party table. You are placed on the queue for a two person table. There are three "elements" ahead of you. In comes a VIP with a friend. The next two person table that opens up is given to the VIP.

An operating system may use a priority queue when scheduling jobs. By default, each job is given the same priority. CPU access is granted using a queue (first come, first served). In certain cases, however, you may have a job that needs to get more CPU usage. In those cases, it will be given a priority higher than the default. The OS will use a scheduling algorithm to ensure the higher priority job gets the CPU with more frequency.

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

Home	Previous	Next