Stack

A Stack is a last-in-first-out data structure. It’s implemented in all computer hardware, and is used by C (and other programming languages) to implement local variables, functions (return addresses), and parameter passing.

The basic functions of the stack are push and pop. Push places an item onto the stack, and pop will remove it. The stack must maintain the following information: Where it has stored the data it is given, where the last item placed into storage was put, and how much space is left in the stack. Stacks can be implemented in C using the following ‘controlling structure’ :

	typedef struct _tagSTACK {
		int *Body;	/* Where data is stored, note 
				we use ints only for example. */
		int Size;	/* How large the body is */
		int Index;	/* Where we currently are within the body */
	} STACK;

The Body data member is a pointer to an array of integers (integers, for demo purposes). When a value is 'Pushed' onto the stack, it will be stored in this array.

The Size data member is an indicator of the maximum size of the stack, and used to make sure we don't corrupt memory.

The Index data member is used to store and retrieve data to and from the stack. Index is changed anytime data is stored or retrieved. When the stack is empty, then Index is zero. When Index == Size, then the stack is full. The Index defines the location of where the next push operation is to take place.

Note that in this description, there are two pieces of data: The STACK structure, and the array that Body points to. Also, trying to place data on a full stack is called a 'stack overflow', trying to remove data from an empty stack is called a 'stack underflow'.

Stack Functions

STACK * StackConstruct( int nSize );
This function creates a new stack. Dynamically allocates a new STACK structure, and allocates it's Body to be nSize elements large. Size is set to nSize and Index is set to zero.

int StackPush( STACK* Stack, int Value );
Places Value on the Stack. Stack indicates what stack to put it on. If the stack is full, this function returns -1, otherwise it returns zero. The value is stored at the current index, and the index is incremented.

int StackPop( STACK* Stack, int *Dest );
Removes a value from the stack. If the stack is empty, this function returns -1. If it's not empty, index is decremented, and the value at [Index] is stored at Dest, and 0 is returned.

void StackDestruct( STACK* Stack );
Removes the body, and stack structure from memory. This items were made in StackConstruct.

int StackIsFull( STACK* Stack );
returns 1 if stack is full, zero if not.

int StackIsEmpty( STACK* Stack );
returns 1 if stack is empty, zero if not.

Testing program for a Stack

#include <stdio.h>
#include <stdlib.h>
#include <mystack.h>
void main( void )
{
	int i;
	STACK *Stack;
	Stack = StackConstruct( 3 );
	if( Stack==NULL )
	{
		printf("Error constructing stack\n");
		exit(1);
	}
	printf("Putting 1 on stack gave %d\n", StackPush( Stack, 1 ) );
	printf("Putting 2 on stack gave %d\n", StackPush( Stack, 2 ) );
	printf("Putting 3 on stack gave %d\n", StackPush( Stack, 3 ) );
	printf("Putting 4 on stack gave %d\n", StackPush( Stack, 4 ) );
	
	if( StackPop(Stack, &i ) == 0 ) printf("pop got %d\n", i );
	else printf("pop failed!\n");
	if( StackPop(Stack, &i ) == 0 ) printf("pop got %d\n", i );
	else printf("pop failed!\n");
	if( StackPop(Stack, &i ) == 0 ) printf("pop got %d\n", i );
	else printf("pop failed!\n");
	if( StackPop(Stack, &i ) == 0 ) printf("pop got %d\n", i );
	else printf("pop failed!\n");
	StackDestruct( Stack );
	exit(0);
}