Queue

Question: Given the root pointer to a binary tree, find if an element is present in it. Input: Sample Tree (Pointer to node 1 is given), Search – 3 Output: Present We discussed how to find if an element exists in the binary tree in this post. Find if an element is present in a binary tree That involved recursion. If recursion seems difficult to you, we can even solve this problem with the help of level order traversal of binary tree. The property of level order traversal is that…

Question: Given the root pointer to a binary tree, find the maximum element present in it. Input: Sample Tree (Pointer to node 1 is given) Output: Maximum = 9 We discussed how to find the maximum element in a binary tree using recursion in this post. Find maximum element in a binary tree That involved recursion. If recursion seems difficult to you, we can even solve this problem with the help of level order traversal of binary tree. The property of level order traversal is that it passes through each…

We discussed the basic tree traversals in this post – Basic tree traversals We learned about the pre-order traversal, in-order traversal and post-order traversal. These are standard traversals that are related with root, left sub-tree and the right sub-tree. Level order traversal follows an entirely different approach and is not related with the left sub-tree and the right sub-tree. It does not hold the same property for all the nodes and hence recursive technique cannot be applied to level order traversal. Let us try to understand with the help of…

In some situations we might need to find the minimum/maximum element among a collection of elements. Priority Queue ADT is the one which supports these kind of operations. A priority queue ADT is a data structure that supports the operations Insert and DeleteMin (which returns and removes the minimum element) or DeleteMax (which returns and removes the maximum element). These operations are equivalent to EnQueue and DeQueue operations of a queue. The difference is that, in priority queues, the order in which the elements enter the queue may not be…

Question: Give an algorithm to reverse a queue. You can only use generic functions of the Queue ADT. Input: 4, 8, 15, 16, 23, 42 Output: 42,23,16,15,8,4 To solve this question will take the help of an auxiliary stack. The steps involved will be:- Create an auxiliary stack S. Until the queue Q is not empty, push the elements of the queue, in the stack S. Now we have a stack in which the last element of the Queue is at the TOP. Until the stack is empty POP(S) and…

Before implementing a queue, we must know the basic operations that should be available for a queue. Main Queue Operations:- enQueue(int data) :- Inserts an element at the end of the queue. int deQueue():- Removes and returns the element at the front of the queue. Auxiliary Queue Operations:- int front():- Returns the first element at the queue, without removing it. int queueSize():- Returns the size of the queue. int isEmptyQueue():- Indicates whether no elements are present. We can implement a queue using an ADT (Abstract Data Type). To implement a…

A queue is a linear data structure that stores data (similar to Linked Lists and Stacks). In a queue, the order in which the data arrives is important. Definition: A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element that you insert, is the first one that is removed. This makes it a First In First Out (FIFO) or Last In Last Out (LILO) list. Basic Operations: The basic operations on this data structure…