Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

queue
linked list
data structures

How to implement a queue using a linked list

Educative Answers Team

A queue is a first-in-first-out (FIFO) data structure. It can be implemented using a linked list.

The following are the three main operations that can be performed on a queue:

  • enqueue: adding an element to the end of the list.

  • dequeue: popping an item from the head of the list.

  • peeking: displaying the element at the tail of the list.

svg viewer
A queue implemented using a linked list.

Implementation

#include <iostream>
#include <list>
using namespace std;
// Add an element to the tail of the linked list
void enqueue(int elem, list <int> &Queue){
   Queue.push_back(elem);
}
// Remove an element from the head of the linked list
int dequeue(list <int> &Queue){
  if(!Queue.empty()){
    int temp = Queue.front();
    Queue.pop_front();
    return temp;
  }
}
// Display the element from the tail of the linked list
int peek(list <int> &Queue){
  if(!Queue.empty()){
    return Queue.back();
  }
}
int main() {
  // Declaring a list to be used as a Queue
  list <int> Queue;
  // Enqueue 3
  enqueue(3, Queue);
  // Display element at the tail of the linked list
  cout<<"Element at tail: "<<peek(Queue)<<endl;
  // Enqueue 4
  enqueue(4, Queue);
  // Display element at the tail of the linked list
  cout<<"Element at tail: "<<peek(Queue)<<endl;
  // Enqueue 5
  enqueue(5, Queue);
  // Display element at the tail of the linked list
  cout<<"Element at tail: "<<peek(Queue)<<endl;
  // Dequeue elements
  cout<<"Element dequeued: "<<dequeue(Queue)<<endl;
  cout<<"Element dequeued: "<<dequeue(Queue)<<endl;
  cout<<"Element dequeued: "<<dequeue(Queue)<<endl;
  return 0;
}

RELATED TAGS

queue
linked list
data structures
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring