Representing Stacks in C

A stack is an ordered collection of objects in memory. C already has a data type that is an ordered collection – the array. We can therefore use the array to represent a stack; however, a drawback to this approach is that the number of items in an array is fixed at declaration. A stack, on the other hand, is a dynamically sized collection that grows and shrinks as items are pushed onto the stack and popped off of the stack.

There is more than one way to represent a stack in C. We can use the array to store a stack, as long as we declare the array to be large enough to store the maximum number of items we think will be placed on the stack. The start of the array functions as the bottom of the stack, and the last element in the array that holds data will be the top the stack that shifts as data is popped off the stack and pushed on the stack.

We can therefore declare a stack to be a structure containing an array as well an integer value indicating the top of the stack. If we declare the array as itself being of the struct type, we can declare a stack that contains different value types.

const int stack_array_size = 100;

enum StackArrayNodeType {integer, floatingpoint, character};

struct StackArrayNode {
	enum StackArrayNodeType;

	union {
		int iValue;
		double dValue;
		char cValue;
	};
};

struct StackArray {
	int top;
	struct StackArrayNode items[stack_array_size];
}; 

The top field in the StackArray structure is declared as an int, since it always represents an index or offset. We represent an empty stack by setting the top field to -1 or some other negative value. We can even set up a simply function to check if the stack is empty or not.

We need to declare a set of auxiliary functions for handling the nodes that make up item in the stack; remember here that each node is itself a stack consisting of an enumerated type identifier as well as a union allowing for different types of actual data stored.

//copy node after it has been popped off the stack
struct StackArrayNode *CopyNode(struct StackArrayNode source) {
	struct StackArrayNode *ReturnNode = (StackArrayNode*)malloc(sizeof(StackArrayNode));
	ReturnNode->type = source.type;
	switch (source.type) {
	case integer:
		ReturnNode->iValue = source.iValue;
		break;
	case floatingpoint:
		ReturnNode->dValue = source.dValue;
		break;
	case character:
		ReturnNode->cValue = source.cValue;
		break;
	}
	return ReturnNode;
}

//returns true only if able to identify type and print value to the screen
bool StackArrayNodePrint(const struct StackArrayNode *theNode) {
	bool returnValue = false;
	//check for NULL node
	if (theNode != NULL) {
		//print node according to its type
		switch (theNode->type) {
		case integer:
			printf("Type: Int \t Value: %d\n", theNode->iValue);
			returnValue = true;
			break;
		case floatingpoint:
			printf("Type: Double \t Value: %f\n", theNode->dValue);
			returnValue = true;
			break;
		case character:
			printf("Type: Char \t Value: %c\n", theNode->cValue);
			returnValue = true;
			break;
		}
	}
	return returnValue;
}

bool StackArrayNodeSetInt(struct StackArrayNode *theNode, int value) {
	bool returnValue = false;
	if (theNode->type == integer) {
		theNode->iValue = value;
		returnValue = true;
	}
	return returnValue;
}

bool StackArrayNodeSetChar(struct StackArrayNode *theNode, char value) {
	bool returnValue = false;
	if (theNode->type == character) {
		theNode->cValue = value;
		returnValue = true;
	}
	return returnValue;
}

bool StackArrayNodeSetFloatingPoint(struct StackArrayNode *theNode, double value) {
	bool returnValue = false;
	if (theNode->type == floatingpoint) {
		theNode->dValue = value;
		returnValue = true;
	}
	return returnValue;
}

We have three functions, each for setting a different value type for the node. We also have a function that prints the node depending on its type. This is necessary since the printf() function requires different conversion characters in the string literal.

bool StackArrayIsEmpty(const struct StackArray theStack) {
	if (theStack->top < 0) {
		return true;
	}
	else {
		return false;
	}
}

Using simple functions like this may impose a minuscule performance penalty as function stacks are added, but it adds immeasurably to the readability of programs. Let’s also add a function to clear the stack. We do this by simply setting the stack’s top value to -1.

void ClearStack(struct StackArray *theStack) {
	theStack->top = -1;
}

Next, let’s implement the pop function. The possibility of underflow should be addressed when implementing the pop functionality for a stack. In this context, we should make sure that the stack is not empty before popping off a value. This function will return a pointer to a dynamically allocated stack object that stores the copied data from the original item on the stack.

struct StackArrayNode *StackArrayPop(struct StackArray *theStack) {

	struct StackArrayNode *returnValue = NULL;

	if (StackArrayIsEmpty(theStack) == false) {
		//note that the decremement of the top index should occur after popping the value
		//because after push operation the index is set to the last element added
		returnValue = CopyNode(theStack->items[theStack->top--]);
	}

	return returnValue;
}

For implementing the push() operation, let’s first add a helper function to check if the stack is already full.

bool StackArrayIsFull(const struct StackArray *theStack) {
	if (theStack->top >= stack_array_size) {
		return true;
	}
	else {
		return false;
	}
}

The push() operation must increment the top of the stack by one. In our case, the stack will increment the top of the stack before actually adding the value, using the prefix increment operator. We do this since whenever the the stack is cleared or initialized, the top value is set to -1, indicating an empty stack. Since we cannot have an array with a negative index value, we must increment it first so that the value to be used as the index is at least 0.

Since we have three different value types, we will have three different push() functions – one for the int type, one for the double type, and one for the char type.

bool StackArrayPushInt(struct StackArray *theStack, int value) {
	//check if stack is full
	bool returnValue = StackArrayIsFull(theStack);
	//if stack isn't full, push value onto stack
	if (returnValue == false) {
		//guard against a negative value other than -1
		if (theStack->top < -1) { 			
                     theStack->top = -1;
		}
		//increment top index before adding value 
		++theStack->top;
		theStack->items[theStack->top].type = integer;
		returnValue = StackArrayNodeSetInt(&theStack->items[theStack->top], value);
	}
	return returnValue;
}

bool StackArrayPushDouble(struct StackArray *theStack, double value) {
	//check if stack is full
	bool returnValue = StackArrayIsFull(theStack);
	//if stack isn't full, push value onto stack
	if (returnValue == false) {
		//guard against a negative value other than -1
		if (theStack->top < -1) { 			
                    theStack->top = -1;
		}
		++theStack->top;
		theStack->items[theStack->top].type = floatingpoint;
		returnValue = StackArrayNodeSetFloatingPoint(&theStack->items[theStack->top], value);
	}
	return returnValue;
}

bool StackArrayPushChar(struct StackArray *theStack, char value) {
	//check if stack is full
	bool returnValue = StackArrayIsFull(theStack);
	//if stack isn't full, push value onto stack
	if (returnValue == false) {
		//guard against a negative value other than -1
		if (theStack->top < -1) { 			
                      theStack->top = -1;
		}
		//increment top index before adding value 
		++theStack->top;
		theStack->items[theStack->top].type = character;
		returnValue = StackArrayNodeSetChar(&theStack->items[theStack->top], value);
	}
	return returnValue;
}

Finally, we can bring it all together in the main() function, were we utilize everything we have written.

int main()
{
	struct StackArray theStack; 
	struct StackArrayNode *tempNode = NULL;

	ClearStack(&theStack);

	StackArrayPushInt(&theStack, 42);
	StackArrayPushChar(&theStack, 'X');
	StackArrayPushDouble(&theStack, 1.61803);
	StackArrayPushInt(&theStack, 8088);
	StackArrayPushChar(&theStack, 'H');
	StackArrayPushDouble(&theStack, 3.14159);
	StackArrayPushInt(&theStack, 1138);
	StackArrayPushChar(&theStack, 'T');
	StackArrayPushInt(&theStack, 6174);

	do {
		tempNode = StackArrayPop(&theStack);
		StackArrayNodePrint(tempNode);
		free(tempNode);
	} while (tempNode != NULL);

    return 0;
}

 

A Simple Stack in C Using an Array

A stack is like a stack of plates – the last plate put on the stack is the first one taken off. This behavior is known as LIFO – last in, first out. Computers in general are stack oriented machines.

The simplest implementation of a stack is as an array. Since the array’s name devolves to a pointer to the first element in the array, we always have a readily available base pointer. It is also possible to implement a stack using linked lists.

The stack can be managed with only two functions: the push() function to write data to the top of the stack, and the pop() function to read data from the top of the stack. As a side effect, the push() function increments the top pointer or array subscript. As a side effect, the pop() function in turn decrements the pointer or array subscript.

#include <stdio.h>
#include <stdlib.h>


//add an int to the
//stack
int push(int *stack, int *top);
//return an int
int pop(int *stack, int *top);
//return an int value from stdin
int getInt();

const int stack_size = 10;

int main(void){


    char c, ch;
    int x;

    int stack[stack_size];

    int top = -1;

    while(1){
        printf("Enter command (R)ead, (W)rite, or (Q)uit: ");
        ch = getchar();
        //clear buffer
        while((c = getchar())!='\n');

        switch(ch){
            //assign old value to y
            //newly popped value to x
            case 'r':
            case 'R':
                x = pop(stack, &top);
                printf("Value popped of stack: %d\n", x);
                break;
            case 'w':
            case 'W':
                if((push(stack, &top))<0){
                    printf("Stack is full!\n");
                } else {
                    printf("Value added to stack: %d\n", stack[top]);
                }
                break;
            case 'q':
            case 'Q':
                printf("Exiting...");
                exit(EXIT_SUCCESS);
        }//end switch
            
    }//end while

    return 0;

}

int pop(int *stack, int *top){
    if(*top >= 0){
        int returnInt = *(stack + *top);
//decremement index value to
//top of the stack by one
        (*top)--;
        return returnInt;
    } else {
        return 0;
    }
} //end pop

//note that array name devolves
//to point to base address of the array
int push(int *stack, int *top){
//increment value pointed to by one
    (*top)++;    
//if we are still within the bounds
//of the array, add a value at the next index
    if(*top < stack_size){
        *(stack+(*top)) = getInt();
        return 0;
    } else {
        return -1;
    }
} // end push

int getInt(){
    printf("Please enter the int value: ");
    char input[12];
    fgets(input, sizeof(input), stdin);
    return atoi(input);    
}

The getInt() function reads up to 12 characters from stdin and places it in a buffer called input. The function then converts the char string contained in input to an integer using the atoi() function and returns it to the calling function.

The pop() function accepts two arguments, one being the base address of the int array, which stores the stack values, and the second being a pointer to the integer value that represents the offset needed to retrieve the value at the top of the stack. We pass the second argument as a pointer because we want to manipulate the integer value it points to directly within the function.

The push() function accepts two arguments, one being the base address of the int array, and the second being an integer value passed “by reference” as a pointer. If the value pointed to by the second parameter is less than the bounds of the int array, we can add a value to the top of the stack.  To access the value pointed to by the second parameter, we must use the dereference operator. It is important to remember to use the dereference operator when using the second parameter as an offset to the base address of the int array.

Note that the push() function returns negative one if there is no more room on the stack.