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);

}isFull

public boolean isFull() {

return (top == size-1);

}

add to stack

public void add (int element) {

if (isFull() == true)

System.out.println("Stack full, cannot add element.");

else

stack[++top] = element;

}

1. check if stack is not full
2. set top position of array to element being added to stack
3. increment values of top and count (if partially filled array)

delete from stack

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
• save value at first index to item you want to enqueue
• increment size
• if array fills up, all n elements have to be copied to a new, larger array
• dequeue operation
• save value at first index
• shift all elements left
• 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.