### 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 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

- First In, First Out (FIFO)
*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

- 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 NOTEAlthough 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