Design a circular buffer


  • 0
    Z

    implement push, pop, next, hasnext function


  • 0
    R

    circular queue maybe ok, using array implement


  • 2
    S

    The idea is to definitely build using arrays. Since Circular buffer are mostly fixed size, arrays will provide a better cache locality. Circular buffer means that Push() will write value to empty spot or if the CB is full it will overwrite the oldest written value. That's how Circular buffers function.

    Three tricky points to note:

    1. When overwriting a value, you must move the start pointer forward to read the oldest value during pop.
    2. When ever the end reaches for either start or end pointer, you must set to 0 and check for case mentioned above.
    3. Check for empty CB for pop operation.

    Below is a complete Java class using Generics.
    GitHub Link: https://github.com/shivam-maharshi/Algorithms/blob/master/src/microsoft/CircularBuffer.java

    /**

    • Design a Circular Buffer with push, pop, next, hasNext.

    • Link: https://leetcode.com/discuss/88912/design-a-circular-buffer

    • @author shivam.maharshi
      */
      public class CircularBuffer<T> {

      private T[] store;
      // Always designates the start of CB.
      private int start;
      // Always designates the end of CB.
      private int end;
      // 0 indicates empty, initialCapacity is full.
      private int size;

      public CircularBuffer(int initialCapacity) {
      this.store = (T[]) new Object[initialCapacity];
      }

      public void push(T... vals) {
      for(int i=0;i<vals.length;i++)
      push(vals[i]);
      }

      // Inserts an item at the end.
      public void push(T val) {
      if (end == store.length)
      end = 0;
      store[end] = val;
      if (size < store.length)
      size++; // When CB has free space.
      else {
      // Means the CB is full.
      start++; // Value of start was overwritten.
      if (start == store.length)
      start = 0;
      }
      end++;
      }

      // Removes an item from start.
      public T pop() {
      if (size == 0)
      throw new RuntimeException("CircularBuffer is empty.");
      size--;
      T val = store[start];
      store[start] = null;
      start++;
      if (start == store.length)
      start = 0;
      return val;
      }

      // Reads the next item.
      public T next() {
      if (size == 0)
      throw new RuntimeException("CircularBuffer is empty.");
      return store[start];
      }

      // Returns true if not empty.
      public boolean hasNext() {
      return size > 0;
      }

      public void print() {
      for (int n = 0; n < store.length - 1; n++)
      System.out.print(store[n] + "->");
      System.out.println(store[store.length - 1]);
      }

      public static void main(String[] args) {
      CircularBuffer<Integer> cb = new CircularBuffer<>(5);
      cb.push(1,2,3,4,5);
      cb.print();
      cb.push(6);
      cb.print();
      for(int i=0;i<5;i++)
      System.out.println(cb.pop());
      // Completely empty.
      cb.print();
      // Is empty now, will throw exception.
      System.out.println(cb.pop());
      }

    }


  • 0
    S

    Well with arrays you can do a mod operator on the index, if the index mod the size are the same it goes back to the start for example:

    const int arraySize = 10;
    int fooArray[arraySize];
    for(int i = 0; i < 100; ++i)
    {
    fooArray[i%arraySize] = i;
    }

    At the end fooArray has values 90 to 99


  • 2
    S

    Well with arrays you can do a mod operator on the index, if the index mod the size are the same it goes back to the start for example:

    const int arraySize = 10;
    int fooArray[arraySize];
    for(int i = 0; i < 100; ++i)
    {
        fooArray[i%arraySize] = i;
    }
    

    At the end fooArray has values 90 to 99


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.