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 🔍 zoom
• 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 🔍 zoom
• 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;

}

• check if stack is not full
• set top position of array to element being added to stack
• 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--];

}

• check if stack is not empty
• decrement top
• 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.