Queue

Introduction

Queue is a linear data structure used to store data. It follows the FIFO(First In First Out) principle.

It is an ordered list in which insertions are done at one end which is known as the rear and deletions are done from the other end known as the front.

Limited availability of resources results in queues.

Queuing theory examines every component of waiting in line, including the arrival process, service process, number of servers, number of system places, and the number of customers—which might be people, data packets, cars, or anything else.

Agner Krarup Erlang, a Danish Mathematician and Engineer introduced the Queuing theory in 1920's

Problem Statement

Given the number of requests who would be served first?

Telephone Exchanges Manual telephone switchboards required human operators to use electrical patch cord cables (aka ‘Switchers’) to route the calls. The caller telephoned the operator and asked to be connected to someone. The operator then plugged the caller’s patch cord cable jack into the call recipient’s socket.

By the start of the 1900s – the idea of picking up a telephone & instantly chatting with someone was becoming very popular – it was the Internet / Social Media of the day – and telephone exchanges – facilities that housed hundreds of switchboards (and hundreds of switchboard operators) – were sprouting up in cities around the world.

Copenhagen Telephone Exchange wanted to improve its company processes.

• How many circuits were needed to provide an acceptable level of telephone service, for people not to be “on hold” (or in a telephone queue) for too long.
• How many telephone operators were needed to process a given volume of calls.

Variety of Use Cases

• Managing requests on a single shared resource such as CPU scheduling and disk scheduling
• Handling hardware or real-time systems interrupts
• Handling website traffic
• Routers and switches in networking
• Maintaining the playlist in media players

Types

• Simple Queue
• Circular queue
• Doubly ended queue

Features and Properties

• Queue can handle multiple data.
• We can access both ends.
• They are fast and flexible.
• FIFO
• Insertion from one end and deletion from another end.

Constraints and Limitations

• Simple Queue

If we pop some item from the front and then rear reach to the capacity of the queue and although there are empty spaces before front means the stack is not full but as per the condition in isFull() function, it will show that the stack is full then.

• Circular Queue

In a circular queue, the number of elements you can store is only as much as the queue length, you have to know the maximum size beforehand.

Outcome