Data Structures A level Computer Science
AQA exam 2024
What is a queue? - A First In First Out Data Structure.
What is a stack? - A LIFO, last-in first-out data structure.
Define Abstract data type - An abstract data type is a logical description of how the data is viewed and
the operations that can be performed on it, but this is not necessarily known to the user.
What are queue's used in? - Characters typed in a keyboard are held in a queue in a keyboard buffer.
Queues are useful in simulation programs simulates customers.
Output waiting to be printed.
What is abstraction? - The removal of unnecessary details from a program making it easier to solve.
What are the following operations needed for a queue? - Enqueue(item): Adds a new item to the rear of
the queue.
deQueue(): Removes the front item from the queue and returns it.
IsEmpty(): Test to see whether the queue is empty.
,Data Structures A level Computer Science
AQA exam 2024
IsFull(): Test to see whether the queue is full.
What is dynamic data structure? - A dynamic data structure refers to the collection of data in memory
that has the ability to grow or shrink in size, it does this with the aid of the heap which is a portion of
memory from which space is automatically allocated or de-allocated as required.
Very useful for implementing data structures like queues. Example is a lists.
What is static data structure - A static data structure such as static array is fixed in size, and cannot
increase in size or free up memory whilst the program is running.
How do you implement a linear queue? - There are 2 ways to to implement a linear queue in an array or
list:
As the items leave the queue all of the item move up one space. So that the front of the queue is always
the first element of the structure. With a long queue, this may require significant processing time.
A linear queue can be implemented with pointers the front and rear of the queue. An integer holding the
size of the array and a variable giving the number of items in currently in the queue are needed.
Disadvantage for the implementation of a linear queue? - If items are added to and deleted from the
queue space is created at the front of the queue which cannot be filled.
, Data Structures A level Computer Science
AQA exam 2024
What is a circular queue? - One way of overcoming the limitations of implementing a queue as linear
queue is to use a circular queue instead so when the array fills up the rear pointer points to the last
element of the array, it will be made to point to the first element.
Disadvantage for the implementation of a circular queue? - This solution requires some extra effort on
the part of the programmer and is less flexible than a dynamic data structure if the maximum number of
items is not known in advance.
What is the Pseudocode to initialise the queue? - SUB Initialise
Front = 0
Rear = -1
Size = 0
maxSize = size of array
ENDSUB
What is the Pseudocode to test for an empty queue? - SUB IsEmpty
IF Size == 0 then
return True
ELSE
return False
ENDIF
ENDSUB
AQA exam 2024
What is a queue? - A First In First Out Data Structure.
What is a stack? - A LIFO, last-in first-out data structure.
Define Abstract data type - An abstract data type is a logical description of how the data is viewed and
the operations that can be performed on it, but this is not necessarily known to the user.
What are queue's used in? - Characters typed in a keyboard are held in a queue in a keyboard buffer.
Queues are useful in simulation programs simulates customers.
Output waiting to be printed.
What is abstraction? - The removal of unnecessary details from a program making it easier to solve.
What are the following operations needed for a queue? - Enqueue(item): Adds a new item to the rear of
the queue.
deQueue(): Removes the front item from the queue and returns it.
IsEmpty(): Test to see whether the queue is empty.
,Data Structures A level Computer Science
AQA exam 2024
IsFull(): Test to see whether the queue is full.
What is dynamic data structure? - A dynamic data structure refers to the collection of data in memory
that has the ability to grow or shrink in size, it does this with the aid of the heap which is a portion of
memory from which space is automatically allocated or de-allocated as required.
Very useful for implementing data structures like queues. Example is a lists.
What is static data structure - A static data structure such as static array is fixed in size, and cannot
increase in size or free up memory whilst the program is running.
How do you implement a linear queue? - There are 2 ways to to implement a linear queue in an array or
list:
As the items leave the queue all of the item move up one space. So that the front of the queue is always
the first element of the structure. With a long queue, this may require significant processing time.
A linear queue can be implemented with pointers the front and rear of the queue. An integer holding the
size of the array and a variable giving the number of items in currently in the queue are needed.
Disadvantage for the implementation of a linear queue? - If items are added to and deleted from the
queue space is created at the front of the queue which cannot be filled.
, Data Structures A level Computer Science
AQA exam 2024
What is a circular queue? - One way of overcoming the limitations of implementing a queue as linear
queue is to use a circular queue instead so when the array fills up the rear pointer points to the last
element of the array, it will be made to point to the first element.
Disadvantage for the implementation of a circular queue? - This solution requires some extra effort on
the part of the programmer and is less flexible than a dynamic data structure if the maximum number of
items is not known in advance.
What is the Pseudocode to initialise the queue? - SUB Initialise
Front = 0
Rear = -1
Size = 0
maxSize = size of array
ENDSUB
What is the Pseudocode to test for an empty queue? - SUB IsEmpty
IF Size == 0 then
return True
ELSE
return False
ENDIF
ENDSUB
