Stack implementation using only one queue in C

Question

We start with an empty queue. For the push operation we simply insert the value to be pushed into the queue.

The pop operation needs some manipulation. When we need to pop from the stack (simulated with a queue), first we get the number of elements in the queue, say n, and remove (n-1) elements from the queue and keep on inserting in the queue one by one. That is, we remove the front element from the queue, and immediately insert into the queue in the rear, then we remove the front element from the queue and then immediately insert into the rear, thus we continue upto (n-1) elements.

Then we will perform a remove operation, which will actually remove the nth element of the original state of the queue, and return. Note that the nth element in the queue is the one which was inserted last, and we are returning it first, therefore it works like a pop operation (Last in First Out).

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

/* Queue structure */

#define QUEUE_EMPTY_MAGIC 0xdeadbeef
typedef struct _queue_t
{
  int *arr;
  int rear, front, count, max;
} queue_t;

/* Queue operation function prototypes */
queue_t *queue_allocate (int n);
void queue_insert (queue_t * q, int v);
int queue_remove (queue_t * q);
int queue_count (queue_t * q);
int queue_is_empty (queue_t * q);

/* NOTE: Here is the stuff we are interested in */
/* Simulated stack operations START */

/* NOTE: passing the queue object, on which we will only operate the
 * queue operations.
 */
void
stack_push (queue_t * q, int v)
{
  queue_insert (q, v);
}

int
stack_pop (queue_t * q)
{
  int i, n = queue_count (q);
  int removed_element;

  for (i = 0; i < (n - 1); i++)
    {
      removed_element = queue_remove (q);
      queue_insert (q, removed_element);
      /* same as below */
      //queue_insert (q, queue_remove (q))
    }
  removed_element = queue_remove (q);

  return removed_element;
}

int
stack_is_empty (queue_t * q)
{
  return queue_is_empty (q);
}

int
stack_count (queue_t * q)
{
  return queue_count (q);
}

/* Simulated stack operations END */


/* Queue operations START */

int
queue_count (queue_t * q)
{
  return q->count;
}

queue_t *
queue_allocate (int n)
{
  queue_t *queue;

  queue = malloc (sizeof (queue_t));
  if (queue == NULL)
    return NULL;
  queue->max = n;

  queue->arr = malloc (sizeof (int) * n);
  queue->rear = n - 1;
  queue->front = n - 1;

  return queue;
}

void
queue_insert (queue_t * q, int v)
{
  if (q->count == q->max)
    return;

  q->rear = (q->rear + 1) % q->max;
  q->arr[q->rear] = v;
  q->count++;
}

int
queue_remove (queue_t * q)
{
  int retval;

  /* magic number if queue is empty */
  if (q->count == 0)
    return QUEUE_EMPTY_MAGIC;

  q->front = (q->front + 1) % q->max;
  retval = q->arr[q->front];
  q->count--;

  return retval;
}

int
queue_is_empty (queue_t * q)
{
  return (q->count == 0);
}

/* Queue operations END */



/* For demo */
void
queue_display (queue_t * q)
{
  int i = (q->front + 1) % q->max, elements = queue_count (q);


  while (elements--)
    {
      printf ("[%d], ", q->arr[i]);
      i = (i >= q->max) ? 0 : (i + 1);
    }
}

#define MAX 128
int
main (void)
{
  queue_t *q;
  int x, select;
  /* Static allocation */
  q = queue_allocate (MAX);


  do
    {
      printf ("\n[1] Push\n[2] Pop\n[0] Exit");
      printf ("\nChoice: ");
      scanf (" %d", &select);

      switch (select)
        {
        case 1:
          printf ("\nEnter value to Push:");
          scanf (" %d", &x);
          /* Pushing */
          stack_push (q, x);

          printf ("\n\n__________________________\nCurrent Queue:\n");

          queue_display (q);
          printf ("\n\nPushed Value: %d", x);

          printf ("\n__________________________\n");
          break;

        case 2:
          /* Popping */
          x = stack_pop (q);

          printf ("\n\n\n\n__________________________\nCurrent Queue:\n");

          queue_display (q);
          if (x == QUEUE_EMPTY_MAGIC)
            printf ("\n\nNo values removed");
          else
            printf ("\n\nPopped Value: %d", x);

          printf ("\n__________________________\n");
          break;

        case 0:
          printf ("\nQutting.\n");
          return 0;

        default:
          printf ("\nQutting.\n");
          return 0;
        }
    }
  while (1);

  return 0;
}

What optimizations can be made in order to reduce code length and time?

Answer 1

• Since the _t suffix is already reserved by POSIX, you should rename stack_t and queue_t. Using reserved names in your own implementation can cause name-clashing issues. More info about this can be found here.

• If you're just printing unformatted text, use puts() instead of printf().

• This is redundant:

  case 0:
    printf ("\nQutting.\n");
    return 0;
  
  default:
    printf ("\nQutting.\n");
    return 0;
  

  Just combine them into one if they're supposed to do the same thing. I'd also use 3 instead of 0 to keep the case numbers in order.

  case 3: default:
    printf ("\nQutting.\n");
    return 0;
  

Answer 2

Assertions in every function that takes a queue_t * q to avoid a NULL would be a good practice. E.g.:

#include <assert.h>
...
int queue_count (queue_t * q)
{
    assert(q != NULL);
    return q->count;
}

At least typedef queue_t into stack_t or similar for the stack functions. It is very weird passing a queue object to a function prefixed with stack_.

typedef queue_t stack_t;
...
int stack_is_empty (stack_t * s);

Consider allowing the user to provide a custom allocator for queue_allocate. Most application will rather prefer using a custom allocator instead of malloc, to allow things like memory accounting and leak tracing. You can let the user provide two pointers to custom allocation functions that have the same interface of malloc and free:

queue_t *queue_allocate (int n, void*(*allocator)(size_t), void (*deallocator)(void*));

So the user can decide between malloc/free or custom functions:

queue_t * my_queue = queue_allocate(10, &malloc, &free);

Or

queue_t * my_queue = queue_allocate(10, &my_alloc, &my_free);

Answer 3

• An underlying queue structure should not be visible to the client, so stack interface needs creation and destruction routines expressed in terms of stack.

• stack_push should return at least bool, to let the user know if it succeeded or failed.

• stack_pop behaves in an unpleasant way if applied to an empty stack. You may want to test for n > 0 before the loop, or at least to document such behaviour.

• QUEUE_EMPTY_MAGIC is a valid integer that can be legitimately inserted in the queue, so the return value of queue_remove is misleading. Consider changing the interface to bool queue_remove(queue_t *, int *).

• Assuming a honest-to-goodness FIFO queue, I don't see how the performance can be improved.

Answer 4

Seems awfully convoluted to me. Is there a particular reason you're implementing your stack as a queue? A stack can be as simple as this:

typedef struct _stack_t
{
    int *  top;  /* Top Of Stack (TOS) pointer                 */
    size_t used; /* number of items on stack                   */
    size_t size; /* maximum number of items that can be stored */
} stack_t;

int stack_init (stack_t * stack, size_t n)
{
    /* sanity check */
    assert((n > 0) && "Attempting to allocate a zero-sized stack!");

    /* safety check */
    if (stack->top != NULL)
    {
        stack_destroy(stack);
    }

    /* allocate memory */
    int * ptr = malloc(n * sizeof(*ptr));

    if (ptr != NULL) /* malloc succeeded */
    {
        stack->top = ptr + n; /* point to end of memory   */
        stack->used = 0;      /* new stack is empty       */
        stack->size = n;      /* store maximum size       */
        return 1;             /* indicate success somehow */
    }
    else /* malloc failed, so we set the stack to a known invalid state */
    {
        stack->top = NULL; /* invalid stack has NULL TOS pointer        */
        stack->used = 0;   /* invalid stack is empty by definition      */
        stack->size = 0;   /* invalid stack has zero size by definition */
        return 0;          /* indicate failure somehow                  */
    }
}

void stack_destroy (stack_t * stack)
{
    /* safety check */
    if (stack->top != NULL)
    {
        /* get pointer to start of memory */
        int * bottom = stack->top - stack->size + stack->used;

        /* release memory */
        free(bottom);

        stack->top = NULL;
        stack->used = 0;
        stack->size = 0;
    }
}

int stack_is_empty (stack_t * stack)
{
    /* an invalid stack cannot return true, or somebody might try to push onto it */
    return ((stack->used == 0) && (stack->size > 0)) ? 1 : 0;
}

int stack_is_full (stack_t * stack)
{
    return (stack->used == stack->size) ? 1 : 0;
}

void stack_push (stack_t * stack, int i)
{
    /* sanity check */
    assert((stack->used < stack->size) && "Attempting to push onto a full stack!");

    --(stack->top);    /* decrement TOS pointer */
    *(stack->top) = i; /* store value           */
    ++(stack->used);   /* increment used count  */
}

int stack_pop (stack_t * stack)
{
    /* sanity check */
    assert((stack->used > 0) && "Attempting to pop from an empty stack!");

    int i = *(stack->top); /* get value from top of stack */
    ++(stack->top);        /* increment TOS pointer       */
    --(stack->used);       /* decrement used count        */
    return i;
}

P.S. I haven't had time to check this, just bashed it out.