Data Structures: Question Set – 05
When and how does one use a queue?
The FIFO (First-In, First-Out) principle is at the heart of queues and other similar data structures. Enqueue (to add an item to the end of the queue) and dequeue (to remove an item from the end of the queue) are its two primary operations (to remove the first element from the queue).
Why do we use binary search trees, and how do they function?
Each node in a binary search tree only ever has two offspring, with the left child being smaller than the parent and the right child being greater. This facilitates rapid searching because 50% of the remaining elements can be eliminated after each screening.
Hash tables: what are they and how do they function?
Hash tables are a type of associative array data structure in which each data item is given a distinct index value determined by its key. The data elements can be conveniently accessed using this index value. The key is mapped to a certain index in the table through a hash function.
How much time does it take to add a node to a binary search tree?
Adding a new node to a binary search tree takes O(log n) time, where n is the total number of nodes.
How long does it take to look up an item in a hash table?
If there are no collisions in a hash table, then the time complexity of searching for an element in the table is on average O(1).
Differentiate between a stack and a queue
Although a queue operates on the FIFO (First-In, First-Out) basis, a stack operates on the LIFO (Last-In, First-Out) philosophy.
What is a stack?
A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. It is a collection of elements with two primary operations: push (to add an element to the top of the stack) and pop (to remove the top element from the stack).
What are the two primary operations performed on a stack?
The two primary operations performed on a stack are push (to add an element to the top of the stack) and pop (to remove the top element from the stack).
How is a stack implemented?
A stack can be implemented using an array or a linked list. In an array implementation, the elements are stored in a contiguous block of memory, while in a linked list implementation, each element contains a reference to the next element in the list.
What is the time complexity of push and pop operations in a stack?
The time complexity of push and pop operations in a stack is O(1), which means that these operations can be performed in constant time.