What Are the Differences Between a Circular Queue & a Linear Queue?

by Frank Howard

While queues can relate to any fluid system, circular and linear queues are more often associated with computer software and computer systems. Between these two types of queues there are both structural and performance differences. For example, when designing a Web server farm, a network architect may need to decide whether access should be handled in a circular queue or a linear queue. This affects how access to the servers is routed, as well as how the servers should be connected structurally.

Real-Life Illustrations

To quickly understand the primary difference between a linear queue and a circular queue, consider a real-life example. If a group of people are waiting in line to be seated at a restaurant, when a table is ready, the people at the front of the line sit down and new arrivals take their place at the back of the line. A circular queue is more like a game of musical chairs. Newcomers can enter anywhere there is room, provided there is an empty chair.

Comparing Queue Structures

A linear queue is like a straight line in which all elements or instructions stand one behind the other. There is a definite beginning and a definite end of the queue. Tasks lined up in this queue format are executed in the order of their placement, on a FIFO (First In First Out) basis. A circular queue has a circular structure. The last element of this queue is connected with the first element, thus completing the circle. Tasks in this format are not essentially executed in the order in which they are sent.

Insertion and Deletion

In a linear queue, a new task is inserted at the end of the list, while a deletion is made at the front of the list. The front and rear ends are responsible for tracking the queue status. A queue can have a finite number of elements, which is predefined. Every new insertion must pass a "queue full" test, and likewise, prior to a deletion, a "queue empty" test must be passed. "Queue full" checks whether that there is space for the insertion, and "queue empty" makes sure there are elements waiting to be deleted and the queue is not already empty. In a circular queue, insertions and deletions can happen at any position in the queue and not necessarily in a sequential order.

Maintenance Cost and Time

In a linear queue, for a new insertion at the end, there must be an empty space at the front and all elements in between must move up one space to create vacancy a for the new insertion. Every time there is a new insertion, the steps have to be repeated. Insertion and deletion are thus two different steps. This approach is time-consuming and computationally expensive. On the other hand, in a circular queue, insertion and deletion can happen simultaneously.

About the Author

Frank Howard has been a professional writer for more than 20 years, working with Metro Publications and Penguin Group. He is now part of the Metro Publications creative team, where he creates fictional stories for kids. Howard has a master's degree in creative writing from City University London and bachelor's degree in journalism from the University of Leeds.

More Articles