10. Data Types and Structures
1a. Linear Queues
Arrays:
● Ordered, static set of elements
● When an array is created it will first need to know how many elements there are in the array (i.e.
how many different values it can hold) - size is fixed (static data structure)
● Once the array is created, this cannot be adjusted when the program is running, so there could be
empty elements in the array, wasting space in the computer’s memory
● Data is stored contiguously in memory (items are next to each other)
● All values in an array must be of the same data type
● The position of each element in an array is identified using the array's index
● The array's first element is the lower bound (LB) - typically 0 or 1 depending on language used
● The array's last element is the upper bound (UB)
● An array can be one-dimensional or multi-dimensional
Lists (Python only has lists built-in, not arrays):
● When a list is created, doesn’t need to know how many elements it will have - starts at 0
● Items then added one at a time and the list is free to grow (as much as memory allows)
● The actual values could be stored in various locations in memory and they do not have to be
stored next to each other in memory
A bubble sort is a very efficient algorithm for sorting an array of data:
● It works by cycling through each item of data, and comparing it with the next item of data
● If the next item is smaller, it swaps the two items around, which eventually by the end of the
pass, brings the highest value to the end (like a bubble floating to the top)
● This process then repeats, each time making swaps as it goes along
● Program ends once the it completes a pass where it has to make no swaps, or aftern-1passes
oundary ← LENGTH(Array) - 1
B
REPEAT
NoSwaps ← TRUE
FOR i ← 1 TO Boundary
IF Array[i] > Array[i + 1] THEN
Temp ← Array[i]
Array[i] ← Array[i + 1]
Array[i + 1] ← Temp
NoSwaps ← FALSE
ENDIF
NEXT i
Boundary ← Boundary - 1
UNTIL NoSwaps = TRUE
Abstract Data Types (ADT):
● An abstract data type (ADT) is a logical description of how we view the data and possible
operations e.g. a queue of print jobs, a stack of books, to-do list
● We are concerned only with what the data is representing and not how it is constructed
● We are creating an encapsulation around the data - encapsulation is a type of information hiding
, Queues:
● A queue is a FIRST IN, FIRST OUT (FIFO) data structure
○ New values may only be added to the end of a queue,
○ Values may only be retrieved from the front of the queue
Linear Queue:
● Linear queues have four distinct operations
○ Add item to the rear of the queue
■ enQueue(item):
■ Check that the queue is not already full
■ (If it isn’t) then add 1 to the value of the rear pointer (the rear pointer is the index
number of the last item in the queue)
■ Then add the new item to the position indicated by the rear pointer
○ Remove item from the front of the queue
■ deQueue():
■ Check the queue is not already empty
■ Return value at the front of the queue and delete (or pop)
■ Move remaining items up the queue one by one
■ Decrement the rear pointer
○ Check if the queue is empty
■ isEmpty():
○ Check if the queue is full
■ isFull():
● Checking if the queue is full/empty is needed to prevent any errors occuring
● Disadvantage of linear queues: if the queue is very long, deQueue will take a very long time as
every item must be moved one space
1b. Circular Queues
A circular queue overcomes the dequeuing issue of linear queues
Circular queues have a front pointer and size attribute
hen an item is dequeued, it does not actually get removed
W
Instead, the front pointer is increased by one and the size decreases by 1
When a new item is enqueued, it overrides items that have been dequeued,
and the size (and rear pointer) are increased by 1
he front pointer and rear pointer wrap around to the beginning when the
T
index goes beyond the last element in the data structure.
● The new index can be calculated using (current index+ 1) MODsize
1a. Linear Queues
Arrays:
● Ordered, static set of elements
● When an array is created it will first need to know how many elements there are in the array (i.e.
how many different values it can hold) - size is fixed (static data structure)
● Once the array is created, this cannot be adjusted when the program is running, so there could be
empty elements in the array, wasting space in the computer’s memory
● Data is stored contiguously in memory (items are next to each other)
● All values in an array must be of the same data type
● The position of each element in an array is identified using the array's index
● The array's first element is the lower bound (LB) - typically 0 or 1 depending on language used
● The array's last element is the upper bound (UB)
● An array can be one-dimensional or multi-dimensional
Lists (Python only has lists built-in, not arrays):
● When a list is created, doesn’t need to know how many elements it will have - starts at 0
● Items then added one at a time and the list is free to grow (as much as memory allows)
● The actual values could be stored in various locations in memory and they do not have to be
stored next to each other in memory
A bubble sort is a very efficient algorithm for sorting an array of data:
● It works by cycling through each item of data, and comparing it with the next item of data
● If the next item is smaller, it swaps the two items around, which eventually by the end of the
pass, brings the highest value to the end (like a bubble floating to the top)
● This process then repeats, each time making swaps as it goes along
● Program ends once the it completes a pass where it has to make no swaps, or aftern-1passes
oundary ← LENGTH(Array) - 1
B
REPEAT
NoSwaps ← TRUE
FOR i ← 1 TO Boundary
IF Array[i] > Array[i + 1] THEN
Temp ← Array[i]
Array[i] ← Array[i + 1]
Array[i + 1] ← Temp
NoSwaps ← FALSE
ENDIF
NEXT i
Boundary ← Boundary - 1
UNTIL NoSwaps = TRUE
Abstract Data Types (ADT):
● An abstract data type (ADT) is a logical description of how we view the data and possible
operations e.g. a queue of print jobs, a stack of books, to-do list
● We are concerned only with what the data is representing and not how it is constructed
● We are creating an encapsulation around the data - encapsulation is a type of information hiding
, Queues:
● A queue is a FIRST IN, FIRST OUT (FIFO) data structure
○ New values may only be added to the end of a queue,
○ Values may only be retrieved from the front of the queue
Linear Queue:
● Linear queues have four distinct operations
○ Add item to the rear of the queue
■ enQueue(item):
■ Check that the queue is not already full
■ (If it isn’t) then add 1 to the value of the rear pointer (the rear pointer is the index
number of the last item in the queue)
■ Then add the new item to the position indicated by the rear pointer
○ Remove item from the front of the queue
■ deQueue():
■ Check the queue is not already empty
■ Return value at the front of the queue and delete (or pop)
■ Move remaining items up the queue one by one
■ Decrement the rear pointer
○ Check if the queue is empty
■ isEmpty():
○ Check if the queue is full
■ isFull():
● Checking if the queue is full/empty is needed to prevent any errors occuring
● Disadvantage of linear queues: if the queue is very long, deQueue will take a very long time as
every item must be moved one space
1b. Circular Queues
A circular queue overcomes the dequeuing issue of linear queues
Circular queues have a front pointer and size attribute
hen an item is dequeued, it does not actually get removed
W
Instead, the front pointer is increased by one and the size decreases by 1
When a new item is enqueued, it overrides items that have been dequeued,
and the size (and rear pointer) are increased by 1
he front pointer and rear pointer wrap around to the beginning when the
T
index goes beyond the last element in the data structure.
● The new index can be calculated using (current index+ 1) MODsize
