Sunday, October 4, 2009

Implementing basic stacks and queues in C

So, you're a C programmer, the type of programmer who hates C++ coz it's bloated and now you're working on a simple program.

You suddenly realize that part of your program needs to use a queue or stack data structure and you absolutely don't want to use STL coz you just don't like it(actually, you hate it)

So what do you do?!

A simple solution for a stack is to define an array with predefined maximum size and then use a stack pointer pointing to next empty place on stack:

//Basic stack structure
#define STACKMAX 10000 //maximum size of stack
int stack[STACKMAX]; //stack array
int stackptr=0;//next empty place on stack


void push(int value){
stack[stackptr]=value;
stackptr++;
}

int pop()
{
if(stackptr
>0){
stackptr--;

return stack[stackptr];
}
else
return -1; //assuming -1 is not a possible value
}

It's almost the same for a queue with the exception that 2 indices are used. 1 which points to the head of the queue and one for the tail.

//Basic queue structure
#define QUEUEMAX 10000 //maximum size of queue
int queue[QUEUEMAX]; //queue array
int head=0;int tail=0;


void push(int value){
queue[tail]=value;
tail++;
}

int pop()
{
if(head
<tail){
head++;
return queue[head-1];
}
else
return -1; //assuming -1 is not a possible value
}

The only problem here is that you have to estimate the maximum size of the queue or stack, and more memory will be used than is actually needed, but this is just for a simple program. Of course you have to include error checking to see that the indices aren't exceeding the array size and then report "queue/stack is full".

3 comments:

  1. Basic of Stack and Queue is like the first in first out and last in first out method. It is really very good concepts.

    ReplyDelete
  2. sorry #include sys/queue.h

    ReplyDelete