circular array implementation

circular array in c
circular array c++
circular array deque
circular queue tutorialspoint
circular array python
circular queue c++
circular array c#
circular array loop

This is my implementation of a circular array so far. It is supposed to store the last 5 commands entered, by entering the 6th command in the place of the 5th and discarding the 1st. What I have managed to do so far is, to able to store the 5 commands and print them out. On the 6th command, I noticed that it goes in the 2nd position (k=1) of the historyArray, but when debugging, k was equal to 0 which would at least push the last command at the top. If you can put me in the right track again, I would appreciate it. Here is part of the code.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main (int argc, char *argv[])
{
    int i=0; 
    int j=0; 
    int k=0;
    int tempIndex = 0;
    int elementCounter = 0;

    char inputString[100];
    char *result=NULL;
    char delims[] = " ";
    char historyArray[5][20] = {0};
    char tokenArray[20][20] ;
    char hCommand[1][20];

    do
    {
         j = 0;

         printf("hshell>");
         gets(inputString);

         //skip writing "history" in historyArray
         if (strcmp(inputString,"history")!= 0)
         {
             strcpy (historyArray[k], inputString);
         }

         k = (k+1) % 5;
         if (elementCounter <= 5)
             elementCounter++;

         // Break the string into parts
         result = strtok(inputString, delims);

         while (result!=NULL)
         {
             strcpy(tokenArray[j], result);
             j++;
             result= strtok(NULL, delims);                  
         }

         if (strcmp(tokenArray[0], "exit") == 0)
             return 0;

         if (strcmp(tokenArray[0], "history") ==  0)
         {
             if (j>1)
             {
                 tempIndex = atoi(tokenArray[j]);
                 puts(tempIndex);
             }
             else
             {
                 for (i=0; i<elementCounter-1;i++)
                     printf("%i. %s\n", i+1, historyArray[i]);
             }
         }
         else
         {
             printf("Command not found\n");
         }
    } while (1);
}

After suggestions (still incomplete):

         j = 0;
         //elementCounter = 0;
         printf("327>");
         gets(inputString);

         strcpy (historyArray[k], inputString);
         k = (k+1) % 5;

        if (elementCounter <= 5)
         {         
          elementCounter++;                
         }

The bug you describe is occurring because of the lines:

k = (k + 1) % 5;
elementCounter++;

What I see happening:

k initial | calculation | k result  | elementCounter
0           (0 + 1) % 5   1 % 5 = 1   1
1           (1 + 1) % 5   2 % 5 = 2   2
...
4           (4 + 1) % 5   5 % 5 = 0   5
0           (0 + 1) % 5   1 % 5 = 1   5

k is behaving as it's supposed to, as far as I can see. However, when elementCounter is 5, k = 1.

EDIT: The problem that I see is that the latest command is being added at position k, not position 0, which based on your implementation is the most recent command entered (based on the various if clauses, like the one that processes the "exit" and "history" commands). Try this set of commands, using your current algorithm. I expect that the contents of the [Command List] column are what you'll see...

Command # | Command Text | [Command List]
0           (null)         []
1           Login          [Login]
2           History        [Login,History]
3           Skynet         [Login,History,Skynet]
4           ps -al         [Login,History,Skynet,ps -al]
5           Skynet         [Login,History,Skynet,ps -al,Skynet]
6           Exit           [Exit,History,Skynet,ps -al,Skynet]

What you would want to do, is copy elements 0-3, and move them to elements 1-4. Then, insert the new command at position 0 in the historyArray. Thus, your history should look like this after adjusting your algorithm appropriately:

Command # | Command Text | [Command List]
0           (null)         []
1           Login          [Login]
2           History        [History,Login]
3           Skynet         [Skynet,History,Login]
4           ps -al         [ps -al,Skynet,History,Login]
5           Skynet         [Skynet,ps -al,Skynet,History,Login]
6           Exit           [Exit,Skynet,ps -al,Skynet,History]

Circular Queue, This approach takes of O(n) time but takes extra space of order O(n) Circular Queue | Set 1 (Introduction and Array Implementation) Prerequisite – Queues Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.

This is I tried and it seems to be working as expected:

             j = 0;
             //elementCounter = 0;
             printf("hshell>");
             gets(inputString);

             strcpy (historyArray[k], inputString);
             k = (k+1) % 5;

            if (elementCounter <= 5)
             {         
              elementCounter++;                
             }

             if (elementCounter ==6)
             {
                k = 5;
                for (i=0; i<5; i++)
                {
                    strcpy(historyArray[i], historyArray[i+1]);
                }
                 strcpy (historyArray[4], inputString);                 
             }

This, basically, checks if the elementCounter becomes 6 (meaning that a 6th command has been entered). If so, it sets k=5 so that the command will be entered at the last position of the array, and then shift the first 4 values up one position leaving index 4 blank. The final step fills the position with the command. It is not the most elegant piece of code but seems to do the trick.

Implementation of Deque using circular array, Circular Queue | Set 1 (Introduction and Array Implementation). Prerequisite – Queues. Circular Queue is a linear data structure in which the operations are  This is my implementation of a circular array so far. It is supposed to store the last 5 commands entered, by entering the 6th command in the place of the 5th and discarding the 1st. What I have managed to do so far is, to able to store the 5 commands and print them out.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    long n; 
    long k; 
    long q; 
    scanf("%ld %ld %ld",&n,&k,&q);
    long *a = malloc(sizeof(long) * n);
    long *b = malloc(sizeof(long) * n);
    for(long a_i = 0; a_i < n; a_i++)
    {
       scanf("%ld",&a[a_i]);
    }
    for(long i = 0; i < k; i++)
    {
        b[0] = a[n-1];
        for(long a_i = 1; a_i < n; a_i++)
        {
        b[a_i] = a[a_i-1];
        }
        for(long a_i = 0; a_i < n; a_i++) 
             a[a_i] = b[a_i];
    }
    for(long a0 = 0; a0 < q; a0++) 
   {
    long m; 
    scanf("%ld",&m);
    printf("%ld\n", b[m]);
    }
    return 0;
}

Circular array, Circular array implementation deque. For implementing deque, we need to keep track of two indices, front and rear. We enqueue(push) an item at the rear or the  This a simple implementation of Queue Abstract Data Type uses an Array. In the array, we add elements circularly and use two variables to keep track of the start element and end element. Generally, a front is used to indicate the start element and rear is used to indicate the end element in the queue.

What is a circular array and how does it work?, Implementing a Queue using a circular array. Just like the Stack, we can implement a Queue using different data structures. You just saw the implementation of  In this tutorial we will go over details on how to implement Circular ArrayList. There are numerous examples we have on Crunchify about ArrayList and this one will be with Integer Array. Let’s get started: Create class CrunchifyCircularArrayList.java; Create constructor with only one parameter arraySize which is 10 in our case

Queue using Circular Array - C++ (Circular Queue), Some DSPs implement circular buffers (arrays) in hardware: you load 2 special registers with a start and end address and then sequential access is automatically  In this Java tutorial, we are going to discuss the circular queue and its array implementation in java. Circular Queue is a linear data structure in which operations are performed on FIFO ( First In First Out ) basis . Element at last position is connected to front element in circular queue . In linear queue we can insert elements till the size

Using an Array to represent a Circular Queue, The most common queue implementation is using arrays, but it can also be implemented using lists. Python. Java. C. C+. # Circular Queue implementation in​  Implementing a Queue using a circular array Just like the Stack, we can implement a Queue using different data structures. You just saw the implementation of the queue using a list

Comments
  • This may or may not be related, but are you confident that your buffers are big enough for any string you'll encounter? If not, then gets and strcpy will lead to overflows. You should investigate fgets and strncpy as "safe" alternatives.
  • Also, I'm sceptical about the if (elementCounter <= 5); why do you need that?
  • @OliCharlesworth You are right. I plan on fixing those later on. The if (elementCounter <= 5) is used to count the elements in the array and I used it in the array printing further down the code. It is there so that it does not print more than 5 values.
  • But what happens when elementCounter reaches 6? Then k will never be updated ever again.
  • Seems to me that if you were to remove the conditional and do the modular arithmetic when doing the copy, things would be a bit simpler. I.e., you always write to historyArray[k % 5] (incrementing k each time around), k + 1 is always the total number of "commands" entered, and MIN(k + 1, 5) is the number of jobs currently in the array.
  • I have posted the full code so you can get a better view at what's happening.
  • Thank you, that helps a lot!
  • I'm on it. I'll be back.
  • I removed the if clauses and it works as shown in your first table. The thing that strikes me though, is the copying. You say "copy elements 0-3, and move them to elements 1-4", but from what I understand, this should be the opposite, as in, copy the values from index 1-4 in index 0-3 and insert the new command in index 4 (position 5). Which is what you showed in your last table, correct?
  • If position 4 is going to be the most recent element in the history queue, yes. It will resemble my second table, just the order would be inverted, as new members would always be added to the final position. Of course, that will also complicate your implementation when your array has fewer than five members.