A study guide for the Data Structures midterm.

4 minute read

Created

CSC251 Study Guide

Midterm Melodrama

Index

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 [code language=โ€javaโ€]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)
  • defintion
    • 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
      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.

Tips or Tricks?

Contact me @fvcproductions

Tags

, , , , , , , , , , , ,

Leave a comment

Read More