Implementation of circular queues, Data Structure & Algorithms

Assignment Help:

One of the main problems with the linear queue is the lack of appropriate utilization of space. Assume that the queue can store 100 elements & the complete queue is full. Thus, it means that the queue is holding 100 elements. In case, some elements at the front are deleted, at the last position the element in the queue continues to be at the similar position and there is no competent way to determine that the queue is not full. In this way, space utilization in the case of linear queues is not competent. This problem is arising because of the representation of the queue.

The substitute representation is to illustrate the queue as circular. In case, we are representing the queue by using arrays, then, a queue along n elements begin from index 0 and ends at n-1.So, obviously , the first element in the queue will be at index 0 and the last element will be at n-1 while all the positions among index 0 & n-1(both inclusive) are filled. Under such situation, front will point to 0 and rear will point to n-1. Though, while a new element is to be inserted and if the rear is pointing to n-1, then, it has to be checked if the position at index 0 is free. If yes, then the element can be inserted to that position & rear can be adjusted accordingly. In this way, the utilization of space is enhanced in the case of a circular queue.

In a circular queue, front will point to one position less to the first element anti-clock wise. Thus, if in the array the first element is at position 4, then the front will point to position 3. While the circular queue is created, then both front & rear point to index 1. Also, we can conclude that the circular queue is empty in case front & rear both point to the same index. Figure  illustrates a circular queue.


Related Discussions:- Implementation of circular queues

Tree structure, We would like to implement a 2-4Tree containing distinct in...

We would like to implement a 2-4Tree containing distinct integer keys. This 2-4Tree is defined by the ArrayList Nodes of all the 2-4Nodes in the tree and the special 2-4Node Root w

Explain the halting problem, Explain the halting problem Given a comput...

Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

Define a procedure called make-avl-tree, This question deals with AVL trees...

This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o

Preorder - postorder and inorder, 1) preorder, postorder and inorder 2) ...

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

Define chaining process of hashing, Chaining In this method, instead of...

Chaining In this method, instead of hashing function value as location we use it as an index into an array of pointers. Every pointer access a chain that holds the element havi

Consistent heuristic function - graph search, Consistent Heuristic Function...

Consistent Heuristic Function - Graph Search Recall the notions of consistency and admissibility for an A* search heuristic. a. Consider a graph with four nodes S, A, B, C,

Function performs multiplication of two numbers, You need to write a functi...

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

Internal sorting, In internal sorting, all of the data to be sorted is obta...

In internal sorting, all of the data to be sorted is obtainable in the high speed main memory of the computer. We will learn the methods of internal sorting which are following:

Explain space complexity, Explain Space Complexity Space Complexity :...

Explain Space Complexity Space Complexity :- The space complexity of an algorithm is the amount of memory it requires to run to completion. Some of the reasons to study space

Explain the prim''s minimum spanning tree algorithm, Question 1. Explai...

Question 1. Explain the different types of traversal on binary tree 2. Explain the Prim's minimum spanning tree algorithm 3. Differentiate fixed and variable storage allo

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd