Write short notes on any two of the following: i) Queue using linked list ii) Hashing iii) Post fix expression evaluation iv) Different types of searching techniques

i) Queue using Linked List:

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. In a linked list implementation of a queue, we use two pointers: front and rear. The front pointer points to the front of the queue, and the rear pointer points to the rear of the queue.

To enqueue (insert) an element into the queue, we create a new node with the given data and add it to the end of the linked list. We update the rear pointer to point to the newly added node.

To dequeue (delete) an element from the queue, we remove the node at the front of the linked list. We update the front pointer to point to the next node in the linked list.

The advantage of using a linked list to implement a queue is that it allows for dynamic resizing. As elements are added to the queue, the linked list can grow to accommodate them.

ii) Hashing:

Hashing is a technique used to store data in a way that allows for fast retrieval. A hash function is used to map a key to a hash value. The hash value is used as the index of an array, called a hash table, where the data is stored.

When a key is used to search for data in a hash table, the hash function is used to compute the hash value. The hash value is then used to access the corresponding element in the hash table.

Hashing is a very efficient way to search for data, especially when the data is large and the key is known. However, hashing can also lead to collisions, which occur when two different keys map to the same hash value. Collision resolution techniques are used to handle collisions.

iii) Postfix Expression Evaluation:

Postfix expression evaluation is a method of evaluating mathematical expressions written in postfix notation, also known as Reverse Polish Notation (RPN). In postfix notation, the operands are written first, followed by the operator.

To evaluate a postfix expression, we use a stack. We push the operands onto the stack. When we encounter an operator, we pop the top two operands from the stack, perform the operation, and push the result back onto the stack.

This process continues until all the tokens in the postfix expression have been processed. The final result is the top element on the stack.

Postfix expression evaluation is often used in compilers and calculators. It is also used in some programming languages, such as Forth and PostScript.

iv) Different Types of Searching Techniques:

There are many different types of searching techniques, each with its own advantages and disadvantages. Some of the most common searching techniques include:

• Linear Search: Linear search is the simplest searching technique. It involves searching through a list of elements one by one until the desired element is found. Linear search is easy to implement, but it is also the least efficient searching technique, especially for large lists.
• Binary Search: Binary search is a more efficient searching technique that can be used on sorted lists. Binary search works by repeatedly dividing the list in half until the desired element is found. Binary search is much more efficient than linear search, but it requires that the list be sorted.
• Interpolation Search: Interpolation search is a variant of binary search that is used on uniformly distributed data. Interpolation search is even more efficient than binary search, but it requires that the data be uniformly distributed.
• Hashing: Hashing is a very efficient searching technique that can be used to search for data in a hash table. Hashing works by mapping a key to a hash value. The hash value is then used to access the corresponding element in the hash table. Hashing is very efficient, but it can also lead to collisions.