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

head++;

}

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".

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#include

ReplyDeletesorry #include sys/queue.h

ReplyDelete