DEV Community

Mohamed Khaled Yousef
Mohamed Khaled Yousef

Posted on

1 3

Queue - Data structure

Queue is data structure like array and stack. But here the first element added to the queue, will be the first element removed from the queue. So queue called first in first out (FIFO) or first come first serve

Alt Stack

We can in queue:

Enqueue(Key): To add key to collection
Key Dequeue(): To remove and return least recently-added key
Boolean Empty(): means,, Are there any elements?

Queue implementation:

We can implement queue in several way (Linked list, Array, 2 Stack).

Queue implementation with linked list:

There two things we must to know:

The first : When we enqueue, we are going to push to the back of the linked list
The second : To make sure the the queue list is empty , we make sure if the head is null or not

Here the code using linked list:

Queue implementation with array:

It’s easy to implement queue using array but pay attention in this case.

When we want to enqueue(g) maybe causes error!! WHY??

This case occurred when we have array say with size (5) but this array have (4) occupied by values

Here example:
Alt Stack

if we did enqueue(g), The read and write would be both 2

  • And it would be hard to distinguish read and write index 2 because the queue is full
  • Or read and write index both 2 because the queue is empty
  • So we have a buffer of at least one that can’t be written to make sure read and write are separate and and distinct if the queue isn’t empty

Notice:
one distinction between the array and linked list implementation
is that in the array implementation we have a maximum size that the queue can grow to so it is bounded

Here the code using array:

Queue time complexity

Cost for doing a dequeue and enqueue , all are O(1). And there is no “worst case”

Finally … Here you can find how to implement queue using 2 stack and all source code in c++

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay