Skip to content

Latest commit

 

History

History
194 lines (124 loc) · 5.26 KB

4.2.1.4 Abstract data types-data structures.md

File metadata and controls

194 lines (124 loc) · 5.26 KB
Raw

Abstract Data Types / Data Structures

Be familiar with the concept and uses of a:

  • queue
  • stack
  • graph
  • tree
  • hash table
  • dictionary
  • vector

Queue

A queue is a data structure that operates either on the first-in first-out (FIFO) out the last-in last-out (LILO) principle.

Items can be added to the rear of the queue and removed from the front.

Implementation:

Can be implemeneted as an Array or linked list

type queue = {
  array[CAPACITY] : VALUE,
  front : Int,
  size : Int
}

Uses

To be used when you want things to happen in the order they were called.

  • Keyboard Buffer
  • Printer Queue

Circular Queues

Queues can be created using an array; however, when an item is removed it leaves a space that cannot be reused.

Circular queues solve this problem by wrapping around to the beginning of the array.

Linear Queues

Queues can also be created using linked lists in the form of a linear queue.

Items are added to the rear of the queue and removed from the front.

Advantages:

  • Fast to implement but uses up large amounts of memory

Disadvantages:

  • Moving the items takes a lot of processing time and would not be an efficient way of managing a busy queue

Priority Queues

Each item in a priority queue is given a priority; the item with the highest priority will always be at the front of the queue. Think of this as queue jumping.

Stack

A stack is a data type that operates on either a last-in first-out (LIFO) or first-in first-out (FIFO) principle.

Items can either be added to or removed from the top of the stack.

A pointer indicates the top of the stack.

Uses of a stack

  • Calling procedures in programs
  • Recursive calculations
  • Reversing array items
  • Performing reverse polish calculations
  • Holding return addresses and system states for recursive function calls

When a routine is called, the computer allocates memory in the stack.

Each time a procedure is called by another procedure, it is pushed onto the stack.

When a function is used, the returned value is allocated to a variable; the variable’s memory location is stored to the stack frame.

At the end of a routine, the value is stored to the return address, control is passed back to the main function and stack frame is removed from the stack.

Graph

Tree

Hash Table

Dictionary

Vector

Static vs Dynamic Structures

Be able to distinguish between static and dynamic structures and compare their uses, as well as explaining the advantages and disadvantages of each.

Static Structures

Static structures are data structures which have a fixed size. They are good for storing a well-defined number of elements.

Uses of static structures

A static structure may be used:

  • To store a list of the top 5 most retweeted tweets
  • To store the 10 last commands in order to implement an undo function

Advantages and Disadvantages

Advantages Disadvantages
Fixed memory use Cannot add more elements if structure is full
No problems in adding or removing data items if structure not full Can be ineffienct as memory for the structure has to be set aside regardless of whether or not it is needed during program execution
Easier to program as there is no need to check data structure size at any point

Dynamic Structures

A dynamic data structure is one in which the number of elements to be stored is unknown. The data structure will grow and shrink as demand arises.

Dynamic structures use locations allocated from the heap.

When implementing a dynamic structure, the programmer should set a max size to avoid memory collisions.

Uses of dynamic structures

A dynamic structure may be used:

  • To keep a record of print jobs for a printer spooler as the number of jobs will not be known beforehand
  • To store a list of all tweets from your account on twitter

Advantages and Disadvantages

Advantages Disadvantages
Memory efficient as the structure only uses memory which is required and has no excess Harder to program as the structure must keep track of its size and location of its elements at any given time
Due to the data allocation being dynamic, the structure could overflow its allowed limit (require more memory than is available)

Creating and maintaining data

Describe the creation and maintenance of data within:

  • queues (linear, circular, priority)
  • stacks
  • hash tables

Queues

  1. Check whether the queue is empty
  2. Return the value of the front element
  3. Return the value of the first element and remove it
  4. Place new element onto the rear of the queue

Linear Queue

Circular Queue

Priority Queue

Stack

  1. Check whether the stack is empty (NULL) or not
  2. Check whether the stack is full or not
  3. Look at the top value and remove it (pop)
  4. Put a new value on top of existing stack (push)

Hash Tables

Overflow and Underflow

When a stack or queue is full, attempting to add a new element will create an overflow error.

When a stack or queue is empty, attempting to remove an element creates an underflow error.