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;
}
C Programming with Al Jensen 