http://www.oocities.org/SiliconValley/Peaks/8778/TAU_advprog.html

4 Stack and Queue

4.1 Stack

4.1.1 Set of operations

Stack is a list data model but instead of various operation of insertion and deletion there are 2 operations only:
That is an element pushed to the stack last will be popped first. This approach has its own name "Last In First Out" or LIFO.

4.1.2 Implementation with linked list.

Well, let's implement these 2 operations assuming that we have a linked list implementation of the "Stack" data model for integer numbers.

NODE* push( NODE* stack, int v)
{
	NODE* new_node;

	new_node = (NODE*)malloc( sizeof(NODE));
	new_node->val = v;
	new_node->next = stack;
	return( new_node);
}

NODE* pop( NODE* stack, int* v)
{
	NODE* tmp;

	if( stack == NULL)
		return( NULL);
	*v = stack->val;
	tmp = stack->next;
	free( stack);
	return( tmp);
}
So the use of the functions may be:

main()
{
	NODE* stack = NULL;
	int v;

	while( something)
	{
		v = some value;
		stack = push( stack, v);
	}
	... some work more...
	while( stack != NULL)
	{
		stack = pop( stack, &v);
		printf( "%d", v);
	}
}

4.2 Queue

4.2.1 Operations on queue

Queue is a list data model but instead of various operation of insertion and deletion there are 2 operations only:
That is an element inserted to the queue first will be got from it first also. This approach has its own name "First In First Out" or FIFO.

4.2.2 Implementation with double-linked list

Unlike all previous examples we will use a new data structure for implementation of a queue. It is called "double linked list" and differs from the regular "single linked list" by second pointer to the previous node in addition to the pointer to the next node. So our "basic" structure will look now:

typedef struct _dlist_node_
{
	int val;
	struct _dlist_node_* next;
	struct _dlist_node_* prev;
} NODE;

Let's write the above mentioned operations for queue using this struct:

NODE* insert( NODE* queue, int v)
{
	NODE* new_node;

	new_node = (NODE*)malloc( sizeof( NODE));
	new_node->val = v;
	new_node->prev = NULL;
	if( queue != NULL)
	queue->prev = new_node;
	new_node->next = queue;
	return( new_node);
}

NODE* get( NODE* queue, int* v)
{
	NODE* n;

	if( queue == NULL)
		return( NULL);
	/* let's find the last element, i.e. the first inserted */
	for( n = queue; n->next != NULL; n = n->next)
		;
	*v = n->val;

	/* if this is the only element */
	if( n->prev == NULL)
	{
		free( n);
		return( NULL);
	}

	n->prev->next = NULL;
	free( n);
	return( queue);
}
It is clear that this implementation is not the best (like some other examples discussed before: they are made simple in educational purposes rather than effective). The trivial improvement is to store both starting end ending elements of queue, so there will be no need to pass over all the queue for getting element. This may be implemented, for example, using another structure like:

typedef _queue _
{
	NODE* start;
	NODE* end;
} QUEUE;
Now our operations insert and get may look so:

void insert( QUEUE* queue, int v)
{
	NODE* new_node;

	new_node = (NODE*)malloc( sizeof( NODE));
	new_node->val = v;
	new_node->next = queue->start;
	if( queue->start != NULL)
		queue->start->prev = new_node;
	new_node->prev = NULL;
	queue->start = new_node;
	if( queue->end == NULL)
		queue->end = new_node;
}

void get( QUEUE* queue, int* v)
{
	NODE* tmp;

	if( queue->end == NULL)
		return;
	*v = queue->end->val;

	if( queue->end->prev != NULL)
		queue->end->prev->next = NULL;
	tmp = queue->end;
	queue->end = queue->end->prev;
	free( tmp);
	if( queue->end == NULL)
		queue->start = NULL;
}
And the use of the functions will be such:

main()
{
	int v;
	QUEUE q;
	q.start = q.end = NULL;

	...
	while( something)
		insert( &q, some integer);

	...
	while( q.start != NULL)
	{
		get( &q, &v);
		...
	}
}

4.3 FIFO and LIFO approaches. Their importance.

An important application of stacks (LIFO) is normally hidden from view but a stack is a way how computer handles function calls: each time a function is called the current "status" of the program is stored in (pushed into) a stack; each time the function finishes to work and returns to its caller the last status is recalled (popped) from the stack.

An importance of queues is more clear: there are many situations when we use queues in our life and any model of such a situation will use some kind of queue. Also queue may be useful for solving some additional tasks (one of such tasks is our exercise).

4.4 Exercise 4