Midterm Melodrama

A study guide for the Data Structures midterm.

CSC251 Study Guide

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.