Thread: Queues

I get the feeling you didn't read very far into my explanation before responding. But that's okay, people tend to ignore me or think I don't know what I'm talking about.

I read your entire post. It's just that the only indication that you were talking about a circular queue was "The only real difference is that you also need to wrap around the pointers to fit within the boundaries of the array" and it's not really clear from just that what you were referring to.

In any event, I don't think that to make a fully functional queue that has no internal limitations (only dependant on available memory and OS) is that difficult.

Code:

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

typedef struct queue_node_s
{
  int num;
  struct queue_node_s *next;
} QUEUE_NODE;

typedef struct
{
  QUEUE_NODE *head;
  QUEUE_NODE *tail;
} QUEUE;

QUEUE *new_queue(void)
{
  QUEUE *q;

  if(!(q = malloc(sizeof(*q))))
    puts("Memory allocation error");
  else
    q->head = q->tail = NULL;

  return q;
}

void clear_queue(QUEUE *queue)
{
  QUEUE_NODE *q, *qnext;

  for(q = queue->head;q;q = qnext)
  {
    qnext = q->next;
    free(q);
  }

  queue->head = queue->tail = NULL;
}

QUEUE *destroy_queue(QUEUE *queue)
{
  clear_queue(queue);
  free(queue);

  return NULL;
}

void print_queue(QUEUE *queue)
{
  QUEUE_NODE *node;

  printf("Elements in queue: ");
  for(node = queue->head;node;node = node->next)
    printf("%d ", node->num);
  putchar('\n');
}

QUEUE_NODE *push(QUEUE *queue, int num)
{
  QUEUE_NODE *new;

  if(!(new = malloc(sizeof(*new))))
    puts("Memory allocation eror");
  else
  {
    new->num = num;
    new->next = NULL;

    if(!queue->head)
      queue->head = new;
    if(queue->tail)
      queue->tail->next = new;
    queue->tail = new;
  }

  return new;
}

QUEUE_NODE *pop(QUEUE *queue)
{
  QUEUE_NODE *q;

  if((q = queue->head))
    queue->head = q->next;

  return q;
}

int main(void)
{
  QUEUE *queue;
  QUEUE_NODE *node;
  char buf[BUFSIZ];
  char choice;

  if(!(queue = new_queue()))
    exit(EXIT_FAILURE);

  do
  {
    printf("1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: ");
    fflush(stdout);

    fgets(buf, sizeof(buf), stdin);
    choice = *buf;
    switch(choice)
    {
      case '1':
        printf("Number to push: ");
        fflush(stdout);

        fgets(buf, sizeof(buf), stdin);

        if(!(node = push(queue, atoi(buf))))
        {
          destroy_queue(queue);
          exit(EXIT_FAILURE);
        }
        printf("Pushed '%d'.\n", node->num);
        break;
      case '2':
        if(!(node = pop(queue)))
          puts("Queue is empty. Unable to pop.");
        else
        {
          printf("Popped '%d'.\n", node->num);
          free(node);
        }
        break;
      case '3':
        print_queue(queue);
        break;
      case '4':
        clear_queue(queue);
        puts("Queue cleared.");
        break;
      case '5':
        destroy_queue(queue);
        break;
      default:
        puts("Please choose 1, 2, 3, 4, or 5.");
    }
  } while(choice != '5');

  return 0;
}

My output:

Code:

1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 1
Number to push: 7
Pushed '7'.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 1
Number to push: 59
Pushed '59'.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 1
Number to push: 86
Pushed '86'.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 1
Number to push: 101
Pushed '101'.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 3
Elements in queue: 7 59 86 101
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 2
Popped '7'.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 3
Elements in queue: 59 86 101
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 1
Number to push: 18
Pushed '18'.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 3
Elements in queue: 59 86 101 18
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 4
Queue cleared.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 3
Elements in queue:
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 2
Queue is empty. Unable to pop.
1) Push, 2) Pop, 3) Print, 4) Clear, 5) Quit: 5

The meat of the queue is all above the main() function. The rest is jsut UI crap. It looks somewhat longer because of error checking and added functionality, but that's pretty much all you'll ever need from a queue. Changing the type of data you can store in the queue is also trivial. To me, this linked list queue is infinitely better than the array queue. There's no wasted memory (due to unused nodes/elements but there is overhead), the queue doesn't have an imposed upper limit, and it can easily store whatever kind of data you want.