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
- data structure of ordered items such that items can be inserted and removed only at 1 end called the
- diagram
- conceptual implementation
- First In, First Out (FIFO)
- add to rear and remove from front
- First In, First Out (FIFO)
- operations
push
– adds item to stackpop
– deletes item from stackpeek
– looks at top item in stacksize
– returns # of elements in stack by examining topisEmpty
– 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
- First In, First Out (FIFO)
- operations
enqueue
– adds item to queuedequeue
– removes item from queuefirst
– looks at top item in stack – so frontsize
– returns # of elements in queue by examining topisEmpty
– 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
- enqueue operation
- 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.
11 views
Last updated on May 12th, 2020