How to implement a queue using linked list – Java & C++

Hello Coders! Welcome to codingbroz and our Data Structures and algorithm interview series.

Today, we are going to see an interesting problem commonly asked in coding interviews is How to implement a queue using linked list? We will also implement the code in Java as well as C++ programming language.

Also Read : How to implement a stack using linked list – Java & C++

Problem

The problem statement says that you have to implement a queue using linked list.

You have to implement the FIFO property of the queue data structure using the linked list data structure.

You have to implement the following functions using a linked list which follows the FIFO property of queue :

• enqueue() / add() : This function should accept data in FIFO manner.
• dequeue() / remove() : This function should return and remove data in FIFO manner.
• peek() : This function should return the data in FIFO manner.

Solution – How to implement a queue using linked list

Java

import java.io.*;
import java.util.*;

public class Main {

  public static class LLToQueueAdapter {
    LinkedList<Integer> list;

    public LLToQueueAdapter() {
      list = new LinkedList<>();
    }

    int size() {
      return list.size();
    }

    void add(int val) {
      list.addLast(val);
    }

    int remove() {
      if(size()==0){
          System.out.println("Queue underflow");
          return -1;
      }
      else{
          return list.removeFirst();
      }
    }

    int peek() {
        if(size()==0){
          System.out.println("Queue underflow");
          return -1;
      }
      else{
          return list.getFirst();
      }
    }
  }

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    LLToQueueAdapter qu = new LLToQueueAdapter();

    String str = br.readLine();
    while (str.equals("quit") == false) {
      if (str.startsWith("add")) {
        int val = Integer.parseInt(str.split(" ")[1]);
        qu.add(val);
      } else if (str.startsWith("remove")) {
        int val = qu.remove();
        if (val != -1) {
          System.out.println(val);
        }
      } else if (str.startsWith("peek")) {
        int val = qu.peek();
        if (val != -1) {
          System.out.println(val);
        }
      } else if (str.startsWith("size")) {
        System.out.println(qu.size());
      }
      str = br.readLine();
    }
  }
}

C++

#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;
}

To Practice more Interview Questions, Checkout other articles too on CodingBroz 🙂