Home Previous Next

CSC205::Lecture Note::Week 09
Assignments | Code | Handouts | Resources | Email Thurman { Compufoo::Twitter | Facebook | YouTube}
GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates

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

Code [stack] NumberSystemStack.java | Stack.java | ParenChecker.java | Stack2.java
[queue] Queue.java | FootNotes.java (footnotes.in.txt) | Q.java
[linked-list] SinglyLinkedList.java | TestLinkList.java [new version] SinglyLinkedList.java | DoublyLinkedList.java


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} {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:

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}


Linked Lists

A linked list is a low-level structure upon which high-level data structures can be built (e.g. stacks and queues can be implemented using a linked-list).

To date, we have grouped program data using the following ADTs (Abstract Data Types, or User Defined Types): array, class), Vector, set, list, stack, and queue (and priority queue).

Sometimes the only ADT available for organizing data is the built-in array; however, this can be problem if the the elements of the array need to be stored in some sort of order and elements are going to be inserted and deleted from the array. In these cases a linked-list may be the solution.

A linked-list is a collection of records, called nodes, each containing at least one field (member) that gives the location of the next node in the list. In the simplest case, each node contains two members: a data member (the data value of the list item) and a link member (a value locating the next node).

If each node contains only one link member, then we have a singly linked list.

Unlike an array, the nodes of a linked-list do not necessarily occupy consecutive memory locations. [C/C++ comment]

The implementation of a linked-list relies heavily on dynamic memory allocation. [Every node is dynamically allocated. When a linked-list is created, its length (i.e. # of nodes) is unknown.] [C/C++ comment]

Although arrays support "simple" list storage applications, they cannot efficiently handle dynamic changes such as inserting and deleting from the middle of a list. As we have seen, these operations require shifting elements either to the right or the left. With large volumes of data, these copy operations can be expensive.

Terminology

A linked list consists of a set of nodes. Each node contains data and link members. The first element is called the front and is pointed to by head. The end-of-list (EOL) is called the rear its link data member has the value NULL (i.e. 0). In some implementations the rear is pointed to by tail. List applications traverse the linked list using a cursor as a reference (or pointer) to the current element.

Description of a Node

A node can be described as follows:

Data
Operations
Bjarne Stroustrup: Why you should avoid Linked Lists
CS 61B at UCBerkeley

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


Home Previous Next