Queue | Linked List | Data Structure

Introduction

In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. It is also known as a FIFO (first in, first out) data structure. In this challenge, we will implement a queue using a linked list.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/AdvancedTopicsGroup(["`Advanced Topics`"]) python(("`Python`")) -.-> python/PythonStandardLibraryGroup(["`Python Standard Library`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/stacks_queues("`Stacks Queues`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/AdvancedTopicsGroup -.-> python/iterators("`Iterators`") python/PythonStandardLibraryGroup -.-> python/data_collections("`Data Collections`") subgraph Lab Skills python/comments -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} algorithm/stacks_queues -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/variables_data_types -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/conditional_statements -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/tuples -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/function_definition -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/classes_objects -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/constructor -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/polymorphism -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/encapsulation -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/iterators -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} python/data_collections -.-> lab-268885{{"`Implementing Queue Using Linked List`"}} end

Queue List

Problem

Implement a queue with enqueue and dequeue methods using a linked list. The enqueue method should add an element to the end of the queue, and the dequeue method should remove an element from the front of the queue. If the queue is empty, dequeue should return None.

Requirements

To implement the queue, we need to follow the following requirements:

If there is one item in the list, the first and last pointers should both point to it.
If there are no items on the list, the first and last pointers should be None.
If you dequeue on an empty queue, it should return None.
We can assume that this fits memory.

Example Usage

Enqueue

Enqueue to an empty queue: If the queue is empty, the enqueue method should add the element as the first and last element of the queue.
Enqueue to a non-empty queue: If the queue is not empty, the enqueue method should add the element to the end of the queue.

Dequeue

Dequeue an empty queue -> None: If the queue is empty, the dequeue method should return None.
Dequeue a queue with one element: If the queue has only one element, the dequeue method should remove the element and set the first and last pointers to None.
Dequeue a queue with more than one element: If the queue has more than one element, the dequeue method should remove the first element and set the first pointer to the next element.

Summary

In this challenge, we learned how to implement a queue using a linked list. We also learned about the requirements for implementing a queue and the different scenarios that can occur while enqueuing and dequeuing elements from the queue.

Implementing Queue Using Linked List