Vectors, Stacks & Queues

Question 1

What is a Vector in ADE?

Answer 1

An Abstract Data Type corresponding to generalising the notion of the ‘array’ CDT
Based off of the array CDT, and stores a sequence of arbitrary objects

Question 2

What is a common usage of Vector? How does this work briefly?

Answer 2

Using it as a stack
Add and remove elements at the end i.e. maximum rank values
push(o) = insert after all the existing ones
pop() = remove the element that is located after all the existing ones

Question 3

How does an array-based Vector work?

Answer 3

Use an array V of size N as the CDT
A variable n keeps track of the size of the vector (number of elements currently stored)
Operation elementAtRank(r) is O(1) time by returning V[r]

Question 4

What is the time complexity of an insertion into an array-based Vector and how does it work?

Answer 4

Worst time complexity - O(n)
Shifts all the elements after the specified point forward another space, so as to make room for the new element

Question 5

What is the time complexity of deletion in an array-based Vector and how does it work?

Answer 5

Worst case - O(n)
Shifts all the elements back a space that are after the specified point so as to ‘fill the hole’, thereby removing the redundant element

Question 6

What are the time complexities for the space used by the data structure, the methods size(), isEmpty(), insertAtRank and removeAtRank, as well as push and pop?

Answer 6

Data structure - O(n)
size, isEmpty - O(1)
insertAtRank, removeAtRank - O(n)
push and pop - O(1) (unless needing to resize the array with push, in which case, this will change to O(n))

Question 7

How would you go about increasing the size of an array-based Vector?

Answer 7

Incremental strategy - increase size by a constant c
Doubling strategy - double the size

Question 8

What is the difference between amortised analysis and average case analysis?

Answer 8

Amortised - real sequence of dependent operations
Average - set of possibly independent operations

Question 9

What is the amortised time of a push operation within an incremental strategy?

Answer 9

Amortised time of a push operation - O(n)

Question 10

How does the incremental strategy work?

Answer 10

Replace the array k = n/c times (c being the length added to the array, and n being the number of elements
T(n) is O(n + k^2) i.e. O(n^2)

Question 11

How does the doubling strategy work?

Answer 11

When the array needs to be extended, takes the current length of the array and then doubles it. Afterwards, transfers over all the old elements.

Question 12

What is the amortised cost of the doubling strategy?

Answer 12

Gives an average of O(1) per push operation, as the overall amount of pushes performed at O(1) vastly outweigh those of O(n)

Question 13

What is the stack ADT and how does it work?

Answer 13

Stores arbitrary references to objects
Insertions and deletions follow last-in-first-out (LIFO)
Main stack operations:
push(object) - inserts an element
pop(object) - removes and returns the last inserted element
Other elements are not accessible

Question 14

What is a common implementation of a stack CDT?

Answer 14

Using it within an array
Add elements from left to right, and a variable (t) keeps track of the index of the top element
If trying to push to an already full array, will throw an exception

Question 15

What is the performance of an array-based Stack and the limitations?

Answer 15

The space used is O(n)
Each operation runs in O(1)
Limitations:
Maximum size of the array-based Stack must be defined in advance and cannot be changed dynamically
Trying to push a new element into a full stack causes an implementation-specific exception

Question 16

What is the Queue ADT and how does it work?

Answer 16

Stores arbitrary objects
Insertions and deletions follow the first-in-first-out (FIFO) scheme
Insertions are at the rear (tail) of the queue, and removals are at the front (head) of the queue

Question 17

How does a queue work when using an array?

Answer 17

Use an array of size N in a circular ‘fashion’
Two variables keep track of the front and rear:
f - index of the front element
r - index immediately past the rear element
Array location r is kept empty

Question 18

What are the differences between ‘narrow’ and ‘wide’ ADTs?

Answer 18

Narrow:
Stack ADT is one of these
Less flexible to use, but more flexible to implement, hence maybe more efficient
Wide:
Java Stack
More flexible to use
Possibly more difficult to implement efficiently

Question 19

How does a stack with a singly linked list work?

Answer 19

Top element is stored at the first node of the list
The space used is O(n) and each operation of the stack ADT takes O(1) time

Question 20

How does a queue work as a singly linked list?

Answer 20

Needs to keep track of both the head and the tail
New arrivals for the queue are placed at the tail and deletions are made at the head
Complexities of operations are:
Inserting at the tail - O(1)
Removing at the head - O(n)

Question 21

What are the pros and cons for using linked list CDTs vs array-based CDTs?

Answer 21

Array:
Con - fixed size, might need a lot of unused space
Pro - contiguous in memory
Linked list:
pro - size grows and shrinks automatically
Cons - can be scattered around memory, and give poor usage of the cache, as well as storage of the ‘next’ reference doubles the space usage