Data Structures

What are four characteristics of arrays?

• Static

• Mutable

• Only store 1 data types

• Can have multiple dimensions

What are four characteristics of lists?

• Dynamic

• Mutable

• Can store multiple data types

• Can have multiple dimensions

What are two characteristics of records?

• Collection of related fields

• Can store multiple data types

• e.g Car record has make, model + price fields

What are three characteristics of tuples?

• Static

• Immutable

• Can store multiple data types

What is an abstract data type?

Made by the programmer rather than defined by the language (e.g queues, stacks, graphs)

What is a stack?

Last In, First Out (LIFO) data structure - items added to the top + removed from the top (like a stack of plates)

What are two applications of stacks?

• Hold addresses when subroutines called

• Back button on browsers

How to implement stacks?

• Use an array

• Two variables - one pointer to the top of the stack + other for max size of array

What five operations are needed for stacks?

• push(item) - add item to the top of the stack

• pop() - remove + return item on the top of the stack

• peek() - return item on the top of the stack

• isEmpty() - checks if stack is empty

• isFull() - checks if stack is full

What is a queue?

First In, First Out (FIFO) data structure - new items added to the end of the queue + items retrieved from the front (like a supermarket queue)

What are two applications of queues?

• Printer queue

• Character typed held in a queue in a keyboard buffer

How to implement queues?

• Use an array

• Two variables - front pointer + back pointer

What four operations are needed for queues?

• enQueue(item) - add an item to the back

• deQueue() - remove item from the front + return

• isEmpty()

• isFull()