Thursday, 5 May 2011

Stack using two queues

Implement a stack using two queues. The operations need not be neccesarily O(1).





#include stdio.h
#include "queueimplll.h"

typedef struct queue QUEUE;
typedef struct queue_node QUEUE_NODE;

int queuepush( QUEUE *q1, QUEUE *q2, int val)
{

/* If first queue is empty, enqueue val straight away*/
if (q1->first == 0 &&
q1->last == 0)
{
enqueue( q1, val);
return 0;
}

/* Enqueue val into second queue*/
if (enqueue(q2, val))
{
printf("ERROR: enqueue q2\n");
}

/* Move (deQ, enQ) from q1 to q2 */
int first_value;
while (!queue_empty_p(q1))
{
dequeue(q1, &first_value);
enqueue(q2, first_value);
}

/* Move (deQ, enQ) from q2 to q1*/
while (!queue_empty_p(q2))
{
dequeue(q2, &first_value);
enqueue(q1, first_value);
}
/* q1 is ready to be poped up*/

queue_empty_p(q2);
return 0;
}

/* Driver program */
int main()
{
QUEUE queue1, queue2;
int index;

init_queue(&queue1);
init_queue(&queue2);

/* Push into queue1 */
srand(time(NULL));
for (index = 0; index <= 100; index++)
{
queuepush( &queue1, &queue2, (rand() % 100) + 1);
}

/* Pop from queue1*/
int value = 0;
index = 0;
while (!queue_empty_p(&queue1))
{
dequeue( &queue1, &value);
printf("%d : %d\n", index++, value);
}
}



No comments:

Post a Comment