Implement Queue using fixed size array

implement queue with limited size of arrays airbnb
implement queue using array
implement queue using array leetcode
implementation of queue using array java
generic queue implementation in java using array
insertion and deletion in queue in data structure
stack and queue using array
array to queue java

I came across below interview question and I am working on it:

Build a queue class with the enqueue and dequeue methods. The queue can store an UNLIMITED number of elements but you are limited to using arrays that can store up to 5 elements max..

Here is what I was able to come up with. Is this the right way to do it in the interview or is there any better way we should implement in the interview?

class Solution {  
  private final List<List<Integer>> array;

  public Solution() {
    this.array = new ArrayList<>();
  }

  public void enqueue(int value) {
    if(array.isEmpty()) {
      List<Integer> arr = new ArrayList<>();
      arr.add(value);
      array.add(arr);
      return;
    }
    if(array.get(array.size() - 1).size() != 5) {
      array.get(array.size() - 1).add(value);   
      return;
    }
    List<Integer> arr = new ArrayList<>();
    arr.add(value);
    array.add(arr);
    return;
  }

  public int dequeue() {
    if(array.isEmpty()) {
      return -1; 
    }
    for(List<Integer> l : array) {
      for(int i=0; i<l.size(); i++) {
        return l.remove(i); 
      }
    }
    return -1;
  }
}

As I mentioned in comments, your solution doesn't really solve the problem because the outer array of 5-element arrays can have more than 5 elements.

Instead, you can implement the queue as a linked list of 4-integer nodes, using the 5th element for a reference to the next array. But there's no reason to assume the elements are integers. This turns out to be pretty simple.

public class SillyQueue<T> {
  private static final int MAX = 5;
  private Object [] head = new Object[MAX], tail = head;
  private int headPtr = 0, tailPtr = 0;

  void enqueue(T x) {
    if (tailPtr == MAX - 1) {
      Object [] a = new Object[MAX];
      tail[MAX - 1] = a;
      tail = a;
      tailPtr = 0;
    }
    tail[tailPtr++] = x;
  }

  T dequeue() {
    if (headPtr == MAX - 1) {
      head = (Object[]) head[MAX - 1];
      headPtr = 0;
    }
    return (T) head[headPtr++];
  }
}

Airbnb, Assume in your programming language you only have a fixed size array of length 5. Implement a queue datastructure that can get unlimitted number of elements� Implement Queue using fixed size array. Build a queue class with the enqueue and dequeue methods. The queue can store an UNLIMITED number of elements but you are limited to using arrays that can store up to 5 elements max.. Here is what I was able to come up with.

Your answer uses ArrayList instead of true arrays, and worse, uses an unlimited arraylist to put those arrays in. I think that the interviewers expected you to implement a singly-linked list of 5-element arrays:

/**
 * A singly-linked list node with an array; supports popping its 1st elements, 
 * and adding elements at the end, possibly by creating a new node
 */
public class ListNode {
    final int MAX = 5;
    private int contents[] = new int[MAX];
    private int size = 0; // valid elements

    private ListNode next = null;
    private ListNode(ListNode next) {
        this.next = next;
    }

    public boolean isEmpty() { return size == 0; }

    public ListNode addLast(int value) {
        ListNode next = this;
        if (size == MAX) {
            next = new ListNode(this);
        }
        next.contents[next.size ++] = value;
        return next;
    }

    public int removeFirst() {
        if (size == 0) {
            throw new NoSuchElementException("empty queue");
        }
        int value = contents[0];
        size --;
        for (int i=1; i<size; i++) contents[i-1] = contents[i];
        return value;
    }
}

/**
 * A simple queue on top of nodes that keep arrays of elements
 */
public class ListArrayQueue {
    ListNode first = new ListNode();
    ListNode last = first;
    public void enqueue(int value) {
        last = last.addLast(value);
    }
    public int dequeue() {
        if (first.isEmpty() && first != last) {
            first = first.next;
        }
        return first.removeFirst();
    }
}

Performance-wise, this can be improved: you can avoid keeping the size in each ListNode, since only the 1st and last nodes can be non-full. You can also avoid the loop in removeFirst, but that would entail replacing size by firstIndex and lastIndex; which could again be moved into the ListArrayQueue to save space in each node.

If they has asked you to build an unlimited array out of 5-element array pieces, you would have had to implement something similar to a b-tree. Which, without handy references, would be quite hard to pull off during an interview.

Array implementation of queue (Simple), To implement a queue using array, create an array arr of size n and take two variables front and rear both of which will be initialized to 0 which means the queue is currently empty. Element rear is the index upto which the elements are stored in the array and front is the index of the first element of the array. return; queue->rear = (queue->rear + 1) % queue->capacity; queue->array [queue->rear] = item; queue->size = queue->size + 1; cout << item << " enqueued to queue "; } // Function to remove an item from queue. // It changes front and size.

You can use a 1-D array and use Wrap-around indexing to implement the queue with the limitation that queue can contain maximum 5 elements.

For checking the condition of empty queue, maintain a variable that counts the number of elements present in the queue.

Implement Queue using fixed size array, Interview questions are almost always meant to evaluate you by the clarifying questions you ask. In this case, what data structures were you� Implement Queue using fixed size array. Ask Question Asked 1 year, 2 months ago. Active 1 year, 2 months ago. Viewed 638 times 2 \$\begingroup\$ I came across below

Is this the right way to do it in the interview…? Presenting uncommented code is never right, let alone in an interview. In an interactive interview, it would be your task to find out whether you can/should use an unlimited number of arrays. If not, you have to negotiate a way to handle an enqueue() to a queue filled to capacity in addition to a dequeue() to an empty one. Fix the type of items the queue can hold. Agree upon the parameters of the enqueue and dequeue methods.

The task is to Build a queue class, Solution is a bad choice for a name - array for something to access the items is no better. In a language providing arrays, I'd take limited to using arrays literally - if using something more, why not an implementation of java.util.Queue? The empty queue handling is entirely redundant: in enqueue(), you could have used if (!array.isEmpty() && array.get(array.size() - 1).size() < 5); in dequeue() you can just drop it. Instantiating List<Integer>s, you know there won't be more than five items at a time: tell the constructor. dequeue() leaves empty List<Integer>s in arrays, giving rise to the current nested loop that desperately needs a comment.

(For the second part of the question, I second Rajkamal Tomar.)

Implement Queue with Limited Size of Array , Assume in your programming language you only have a fixed size array of length 5. Implement a queue datastructure that can get unlimitted� The queue implemented using array stores only fixed number of data values. The implementation of queue data structure using array is very simple. Just define a one dimensional array of specific size and insert or delete the values into that array by using FIFO (First In First Out) principle with the help of variables 'front' and ' rear '.

Implement a Queue using an Array in Java, import java.lang.reflect.Array; import java.util.Arrays; public class Queue<E> { E[] arr; int head = -1; int tail = -1; int size; public Queue(Class<E> c, int size) { E[]� We can implement a queue by using an array. import java.lang.reflect.Array; import java.util.Arrays; public class Queue < E > { E [] arr; int head = -1; int tail = -1; int size; public Queue ( Class < E > c, int size) { E [] newInstance = ( E []) Array. newInstance( c, size); this. arr = newInstance; this. size = 0; } boolean push ( E e) { if ( size == arr. length) return false; head = ( head + 1) % arr. length; arr [ head] = e; size ++; if( tail == -1){ tail = head; } return true; } boolean

Queue - Array Implementation, Here's a queue of characters with 3 elements: queue Let's simplify our array implementation of a queue by using an array of a fixed size, MAX_QUEUE_SIZE . Implementing a queue with an array: Since a queue usually holds a bunch of items with the same type, we could implement a queue with an array. Let's simplify our array implementation of a queue by using an array of a fixed size, MAX_QUEUE_SIZE. What other pieces of data would you need (besides an array) to implement a queue in this way?

src/main/java/implement_queue_with_fixed_size_of_arrays , Code and explanation of a queue and all its functions using an array in C. can't change the size of an array, so we will make an array of fixed length We will use three pointers to implement the queue using an array, 'size',� A queue is an abstract data structure that contains a collection of elements. Queue implements the FIFO mechanism i.e. the element that is inserted first is also deleted first. In other words, the least recently added element is removed first in a queue. A program that implements the queue using an array is given as follows − Example

Making a queue using an array in C, However, if using dynamic memory allocation is not an option, then there is no other buffer with maximum length known at compile time over C array or std:: array. Here is the implementation of StaticQueue functionality from embxx library. Queue using Array 1.Insertion 2.Deletion 3.Display 4.Exit Enter the Choice:1 Enter no 1:10 Enter the Choice:1 Enter no 2:54 Enter the Choice:1 Enter no 3:98 Enter the Choice:1 Enter no 4:234 Enter the Choice:3 Queue Elements are: 10 54 98 234 Enter the Choice:2 Deleted Element is 10 Enter the Choice:3 Queue Elements are: 54 98 234 Enter the

Comments
  • Make it circular, by using a pointer to current head, also record the actual size, when overflow, replace & discard the oldest element.
  • I'm confused. If you can use an array of size only 5, you can't possibly store an unlimited number items, right? Or can you get rid of the older elements like @EricWang suggests?
  • Your solution uses an array of arbitrary length to hold arrays of length 5, so it doesn't solve the problem. To get arbitrary size, you need to implement something like a 5-ary tree where the leaves are the integers. Of course no computer can hold any data structure of UNLIMITED size because real computers can only address a finite amount of memory. In an interview you'd do well to explain that.
  • Or a linked list of 4-element nodes.
  • This solution right now doesn't take care of memory after deque that won't be used ever again. A separate program to free up those memory areas would be needed to keep memory leak in check (just for the sake in an interview). Correct me if I missed something.
  • @UtkarshGupta No that's not a problem. Nodes bypassed by head no longer have any references, so the JVM's garbage collector will get them. Same as popping the head not from a linked list.
  • Yes, you're right in the case of Java. But still, it needs to be handled for languages that don't come with the GC and expects the programmer to free the memory, i.e. c, c++, etc.