Midterm Melodrama – Data Structures With Java

A study guide for the Data Structures midterm.

CSC251 Study Guide

Midterm Melodrama

Index

• Array Properties
  • overview
• Stack Properties
  • overview
  • definition
  • diagram
  • conceptual implementation
  • operations
• Queue Properties
  • overview
  • definition
  • diagram
  • conceptual implementation
  • operations
• Stack Code & Algorithms\
  

  uses arrays for implementation

  • is stack empty
  • is stack full
  • add to stack
  • delete from stack
  • print in order
  • find an element in stack
• Comparing Stacks & Queues
  • overview
  • advantages
  • disadvantages
  • examples of how they can be used
• Queue Algorithms
  

  uses arrays for implementation

  • shift queue
  • circular queues
• Basic Definitions & Phrases

Array Properties

• overview
  • fixed size
  • more efficient b/c it uses less memory
  • easier to manage
  • collection
  • linear
  • can add/remove at any position

Stack Properties

• overview
  • example of a collection SDT
  • since stacks are lists, any list implementation will do
  • Last In, First Out data structure
  • can be implemented as an array
  • can only access the top
  • harder to manage b/c only top can be accessed
• defintion
  • data structure of ordered items such that items can be inserted and removed only at 1 end called the top
• diagram

• conceptual implementation
  • First In, First Out (FIFO)
    • add to rear and remove from front
• operations
  • push – adds item to stack
  • pop – deletes item from stack
  • peek – looks at top item in stack
  • size – returns # of elements in stack by examining top
  • isEmpty – tests for emptiness in stack by examining top

Queue Properties

• overview
  • example of a collection SDT
  • operations: enqueue (add), dequeue (delete)
• definition
  • data structure of ordered items that can be inserted only at end (rear) and removed at other end (front)
• diagram

• conceptual implementation
  • First In, First Out (FIFO)
    • add to rear and remove from front
• operations
  • enqueue – adds item to queue
  • dequeue – removes item from queue
  • first – looks at top item in stack – so front
  • size – returns # of elements in queue by examining top
  • isEmpty – tests for emptiness by examining top

Stack Code & Algorithms

isEmpty

int top = -1; //or 0
public boolean isEmpty () {
    return (top == -1);
}

public boolean isFull() {
    return (top == size-1);
}

public void add (int element) {
    if (isFull() == true)
        System.out.println("Stack full, cannot add element.");
    else
        stack[++top] = element;
}

public int delete () {
    if (isEmpty() == true)
        System.out.println("Stack empty, cannot delete element.");
    else
        return stack[top--];
}

1. check if stack is not empty
2. decrement top
3. set return value to top position of array

print in order

public void printOrder() {
    while(!isEmpty()) {
        int value = remove();
        System.out.print(value + " ");
    }
}

find an element in stack

public boolean find(int element) {
    System.out.print("Please enter element to find: ");
    element = keyboard.nextInt();
    for (int i = 0; i < size; i++) {
        if (stack[i] == element)
            return true;
    }
    return false;
}

Comparing Stacks & Queues

• overview
  • stacks and queues are similar data structures
  • they’re different only by how an item is removed first
  • both can be implemented as arrays or linked lists
• advantages
  • implementing a stack as an array is easy, but implementing a queue as an array is more difficult because you have to dequeue from front and enqueue at end
  • TL; DR
    • when you want to be able to add or remove values from any position, arrays are the way to go because any value can be accessed through indexes
• disadvantages
  • main limitations of arrays is that they cannot be extended or shrunk so you want to use an array when you know your max upper limit
  • TL; DR
    • if you’re not sure how many values there will be in your data structure, then it’s better to not use an array and stick with a linked list (ergo, queues) because arrays always have a fixed size
• examples of stacks
  • CD storage case
  • cafeteria tray
  • batteries in a flashlight
  • cars in a single car garage
  • Towers of Hanoi
• examples of queues
  • waiting line for a roller coaster
  • hamburger processing line at Mickey D’s
  • vehicles on a toll bridge
  • luggage checking machine
  • phone answering system for most big tech companies

Queue Algorithms

• shift queues
  • enqueue operation
    1. save value at first index to item you want to enqueue
    2. increment size
    3. if array fills up, all n elements have to be copied to a new, larger array
  • dequeue operation
    1. save value at first index
    2. shift all elements left
    3. decrement size
• circular queues
  • advance queue indexes front (to delete an item) and back (to insert an item) by moving them both clockwise around array

Basic Definitions & Phrases

• abstract data type\
  

  taken straight from the textbook

  • a data structure is the underlying programming construct used to implement a collection
• abstractions
  • ignores or hides certain details at certain times, e.g. collection is abstraction where details of implementation are hidden
• “abstract” in abstract data type
  • means that there are many different ways of implementing data type
• algorithm
  • step by step instructions on how to execute a program or set of instructions
• data structure
  • memory structure with associated representation mapping, e.g. a collection is a type of data structure that acts as an object that gathers & organizes other objects
• a data type is specified by describing both
  • its set of values & operations used for implementation
• implementing an abstract data type proceeds in 2 stages
  • declaring necessary variables of data types
  • writing methods & procedures to implement operations of data for given data types

TO NOTE

Although stack and queues have been implemented using an array – these ADTs are not accessed as an array. No actual code for a queue on this test; but you should be able to write an algorithm to demonstrate the concept of a queue.