1.4.2 Data structures definitions/info Flashcards
(b) (c)
What is a stack?
A data structure which follows a last in, first out (LIFO) structure
- holds an ordered, linear sequence of items
what is needed to keep track of a stack?
a pointer which points to the top of the stack
what is the operation to add an item to a stack?
push - adds an element to the top of a stack
what is the operation to remove an item from a stack?
pop - removes an element from the top of the stack
what is the peek operation?
returns a copy of the element on the top of the stack without removing it
what are the steps for the push operation?
- check if the stack is full
- add an item by incrementing the pointer by 1 and then inserting the item into the array at the pointer
what are the steps for the pop operation?
- checks if the stack is empty
- store the item at the top of the stack (at the index equal to the pointer)
- reduce the pointer by 1
- return the item
what are the steps for the peek operation?
- return the item at the top of the stack (at the index equal to the pointer)
what other functions can there be for a stack?
is_empty - checks if the stack is empty
is_full - checks if the stack is at maximum capacity when stored in a static structure
what is a static data structure?
a data structure of fixed size
what are the ways a stack can be implemented?
- using a static array
- using a dynamic linked list
what is a queue?
a data structure which follows first in, first out (FIFO) structure
- holds an ordered linear sequence of items
what is the operation to add an item to a queue?
enqueue - adds an element to the queue
what is the operation to remove an item from a queue?
dequeue - removes an element from the front of the queue
what is needed to keep track of a queue?
- a pointer at the front
- a pointer at the back/rear
what other operations can a queue have?
- is_empty - checks if the queue is empty
- is_full - checks if the queue is full
what are the steps for the enqueue operation? (for linear queues)
- check if the queue is full
- increment the back/rear pointer
- add the item to where the back/rear is pointing to
- check if this is the first item to be added to the queue (if the front pointer = -1) and if so, sets the front pointer to 0
what are the steps for the dequeue operation? (for linear queues)
- check if the queue is empty
- store the item at the front of the queue in a variable
- increment the front pointer
- return the item
what is a circular queue?
a queue which reuses the empty slots at the front of the queue when elements are dequeued
how does a circular queue work?
- as items are enqueued, and the rear pointer reaches the last position, it wraps around to point at the start of the array
- as items are dequeued, the front pointer will wrap around until it passes the rear pointer
how is the enqueue operation adjusted for circular queues?
- use an additional check to cycle back to the beginning if there is free space
how is the dequeue operation adjusted for circular queues?
- use an additional check to cycle to the beginning of the queue
what is a priority queue?
a queue where each element in the queue has a priority
when new elements are added into the queue, they are inserted ahead of those with a lower priority and behind those with equal priority.
what is a dynamic data structure?
a data structure where the size can change at any time
what is a graph?
an abstract data structure that can represent relationships between objects.
what does a graph consist of?
nodes (hold the data)
edges (represent the relationships)
what are neighbours in a graph?
when two nodes are connected by an edge
what is the degree of a node?
the number of other nodes that a node is connected to
what is a loop?
an edge that connects a node to itself
what is a path?
a sequence of nodes that are connected by edges
what is a cycle?
a closed path (starts and ends at the same node with no repeats)
what are some applications of graphs?
- social networking
- transport networks
- the internet
- the world wide web
what is an undirected graph?
a graph where you can traverse in either direction between nodes
what is a directed graph?
a graph where the edges have a direction
what is a weighted graph?
a graph that has values associated with the edges
what is a tree?
a graph that:
- has no cycles
- must be connected
what does a tree having no cycles mean?
there is only one possible path between any two nodes
what is the root of a tree?
the start node for traversals
rooted trees have roots
what is a branch?
a path from the root to an end point
what is a leaf?
an end point on a tree
- a leaf node has no other nodes attached to it except 1
what is the height of a tree?
equal to the number of edges that connect the root node to the leaf node furthest from it
what is a binary tree?
a tree which:
- has a root node
- every node must have at most two child nodes
what is a binary search tree?
a rooted tree where the nodes are ordered
how does the binary search tree algorithm work?
- set the current node to the root node
- use a while loop to check if we have reached a leaf node
- if the data in the current node is greater than the search item, we go to the left
- if the data in the current node is less than the search item, we go right
- if the data in the current node = the search item, return true
- if a leaf node is reached, return false
what is a breadth first traversal?
a traversal which goes along the horizontal layers of a graph/tree
how does a breadth first traversal work?
- visit the root node
- visit all nodes attached to the root node
- move to the first node attached to the starting node and repeat, visiting the nodes attached to this node
what does a breadth first traversal use to store nodes?
a queue stores visited nodes
what are the different types of depth first traversal?
pre-order
in-order
post-order
how does a pre-order traversal work?
visit, left, right
how does an in-order traversal work?
left, visit, right
how does a post-order traversal work?
left, right, visit
what is used to store previous nodes in a depth first traversal?
a stack
what is a linked list?
a dynamic data structure which has links to sort the data
how is an item added to an unordered linked list?
- insert data into the next available free node
how is an item added to an ordered linked list?
- create a new node
- traverse the list to find the correct position
- set the pointer of the new node to the pointer of the pointer of the current node
- set the pointer of the current node to the pointer of the new node
what is the free pointer used for?
it is used to point to the next available free location
what are the steps to search a linked list?
- set current to the head pointer
- use a while loop to continue code until the end of the linked list
- check if the current node = data
- return true if true
- increment current to the next pointer if not
- return false if the while loop breaks
