Stacks: functions, modules

A stack is an ADT used to push items on the stack and pop items off the stack. It as called first-in last-out as only the top item on the stack is available (through normal channels or calls).

Stacks are often used to remember where you were, start something new, then return and pick up where you left off.

The following are stack operations.

Init to initialize the stack to empty
Push to push an item onto the stack
Pop to pop an item off of the stack
Top to get the top item on the stack (without changing the stack)
Empty to determine if the stack is empty

In production programs, some form of error checking is often done.

This error checking can be for each and every stack access.

Or, it can be the responsibility of the calling program (for abstracted stack routines).

Or, a correctness proof make it impossible for an error to happen (e.g., for advanced programming language design concepts).

And so on.

A stack can be implemented as a list. The list can be implemented as an array.

Here is an implementation and test program for a stack for items of type integer. To keep the example simple, no error checking is done.

Here are the data structures for the stack.

const int STACKMAX = 32;
int stack1[STACKMAX+1];
int stackLen1;

The stack is initialized as follows.

// Initialize the stack
stackLen1 = 0;

The input uses a trailer loop to get values and push them on the stack.

scanf("%d",&value1);
while (value1 >= 0) {
	printf("\t%d\n",value1);
	// push the value
	stackLen1++;
	stack1[stackLen1] = value1;
	scanf("\t%d",&value1);
	}

The output pops values off of the stack and prints them, which means that they are printed in reverse order of how they were read from the input.

while (stackLen1 != 0) {
	// pop the value
	value1 = stack1[stackLen1];
	printf("\t%d\n",value1);
	stackLen1--;
	}

Here is the C code.

#include <stdio.h>

int main() {
	const int STACKMAX = 32;
	int stack1[STACKMAX+1];
	int stackLen1;
	int value1;
	// Initialize the stack
	stackLen1 = 0;
	// input
	printf("Input: (in order)\n");
	scanf("%d",&value1);
	while (value1 >= 0) {
		printf("\t%d\n",value1);
		// push the value
		stackLen1++;
		stack1[stackLen1] = value1;
		scanf("\t%d",&value1);
		}
	// process and output
	printf("Output: (reverse order)\n");
	while (stackLen1 != 0) {
		// pop the value
		value1 = stack1[stackLen1];
		printf("\t%d\n",value1);
		stackLen1--;
		}
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

For the above example input, here is the expected output.

Input: (in order)
	123
	234
	456
	567
Output: (reverse order)
	567
	456
	234
	123

The mental model of a stack as implemented above can be abstracted to use functions to more separate the mental model of a stack from the implementation of that model.

In doing the abstraction, the code in the local scope of main is moved to the global scope.

Here are the data structures.

#define STACKMAX1 32
int stack1[STACKMAX1+1];
int stackLen1;

Note: The const has been used at the local scope. Due to programming tradition, the define is usually used at the global scope.

Note: The STACKMAX name could be used at the local scope level using const.

But that name is used elsewhere in C, so, in this case, STACKMAX1 is used at the global scope level.

The stack is initialized by setting stackLen1 to 0 (zero).

void stackInit() {
	stackLen1 = 0;
	}

The function stackPush pushes the supplied value onto the stack.

void stackPush(int value1) {
	stackLen1++;
	stack1[stackLen1] = value1;
	}

The function stackPop pops the top of the stack off the stack and returns that value.

int stackPop() {
	int value1 = stack1[stackLen1];
	stackLen1--;
	return value1;
	}

The function stackEmpty returns 0 if the stack is empty. Otherwise, the length of the stack is returned, a feature of this routine.

int stackEmpty() {
	return stackLen1;
	}

The stackTop function returns the value at the top of the stack.

int stackTop() {
	return stack1[stackLen1];
	}

Here is the C code.

#include <stdio.h>

// begin stack implementation

// stack data structures

#define STACKMAX1 32
int stack1[STACKMAX1+1];
int stackLen1;

// stack routines

void stackInit() {
	stackLen1 = 0;
	}

void stackPush(int value1) {
	stackLen1++;
	stack1[stackLen1] = value1;
	}

int stackPop() {
	int value1 = stack1[stackLen1];
	stackLen1--;
	return value1;
	}

int stackEmpty() {
	return stackLen1;
	}

int stackTop() {
	return stack1[stackLen1];
	}

// end stack implementation

int main() {
	int value1;
	stackInit();
	// input
	printf("Input: (in order)\n");
	scanf("%d",&value1);
	while (value1 >= 0) {
		stackPush(value1);
		printf("\t%d\n",value1);
		scanf("\t%d",&value1);
		}
	// process and output
	printf("Output: (reverse order)\n");
	while (stackEmpty() != 0) {
		value1 = stackPop();
		printf("\t%d\n",value1);
		}
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

For the above example input, here is the expected output.

Input: (in order)
	123
	234
	456
	567
Output: (reverse order)
	567
	456
	234
	123

This code for implementing a stack might be useful in other programs so that the code can be reused.

There are many sophisticated ways to do this. A simple and common way to get started is now covered.

The first step is to separate the interface from the implementation.

The implementation contains the actual code that does the computations.

The interface is a controlled way in which to access the implementation.

Below is the above code separated into interface and implementation parts.

The interface consists of constants, variables, and functions. The interface for the stack implementation is as follows.

void stackInit();
void stackPush(int value1);
int stackPop();
int stackEmpty();
int stackTop();

Note the function headers following by a semicolon. These must match exactly the implementation which is moved below the main function.

A function header (without the implementation body) is sometimes called a prototype although this word can be confused with the object-oriented feature of a prototype.

The generic term for a function header is a signature though a signature can be a more general concept.

The formal parameter names of the interface do not need to match the formal parameter names of the implementation, though this is usually done. Here is the C code.

#include <stdio.h>

// begin stack interface
void stackInit();
void stackPush(int value1);
int stackPop();
int stackEmpty();
int stackTop();
// end stack interface

int main() {
	int value1;
	stackInit();
	// input
	printf("Input: (in order)\n");
	scanf("%d",&value1);
	while (value1 >= 0) {
		stackPush(value1);
		printf("\t%d\n",value1);
		scanf("\t%d",&value1);
		}
	// process and output
	printf("Output: (reverse order)\n");
	while (stackEmpty() != 0) {
		value1 = stackPop();
		printf("\t%d\n",value1);
		}
	return 0;
	}

// begin stack implementation

// stack data structures

#define STACKMAX1 32
int stack1[STACKMAX1+1];
int stackLen1;

// stack routines

void stackInit() {
	stackLen1 = 0;
	}

void stackPush(int value1) {
	stackLen1++;
	stack1[stackLen1] = value1;
	}

int stackPop() {
	int value1 = stack1[stackLen1];
	stackLen1--;
	return value1;
	}

int stackEmpty() {
	return stackLen1;
	}

int stackTop() {
	return stack1[stackLen1];
	}

// end stack implementation

Here are some examples of input and output for the above program code.

Here is an example input.

For the above example input, here is the expected output.

Input: (in order)
	123
	234
	456
	567
Output: (reverse order)
	567
	456
	234
	123

The implementation encapsulates the functionality.

The code in main can no longer access the internals of the stack.

The code in main must only access the stack through the interface.

This concept is called encapsulation.

The next step is to abstract the interface and implementation to a module.

A module is a collection of code that can be reused between programs.

In C, a module is created as follows. Other languages have other conventions for how this is done but follow the same general ideas.

0. Separate the interface and implementation parts, as in the above code. 1. A name for the module is decided, such as rsStack. The "rs" may be the programmer's initials. Or the company initials. Or some prefix that makes it unlikely that the same module would be named the same name by someone else. 2. The interface is put into file rsStack.h (The letter h is for "header").

3. The implementation is put into file rsStack.c (The letter c is for code in the C programming language). 4. The following directive is added to the top of the main program.

#include "rsStack.h"

Note that (user defined) non-standard modules use double quotes while standard modules use angle brackets such as the following.

#include <stdio.h>

This is just a convention as either will work for either purpose.

The following program now results. Note how much smaller it is since functionality has been moved to a module.

One disadvantage is that one must now know what that interface is, how to use it, and code is now separated between many files instead of in just one program file. Here is the C code.

#include <stdio.h>
#include "rsStack.h"

int main() {
	int value1;
	stackInit();
	// input
	printf("Input: (in order)\n");
	scanf("%d",&value1);
	while (value1 >= 0) {
		stackPush(value1);
		printf("\t%d\n",value1);
		scanf("\t%d",&value1);
		}
	// process and output
	printf("Output: (reverse order)\n");
	while (stackEmpty() != 0) {
		value1 = stackPop();
		printf("\t%d\n",value1);
		}
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

For the above example input, here is the expected output.

Input: (in order)
	123
	234
	456
	567
Output: (reverse order)
	567
	456
	234
	123

Here is the interface in the header file rsStack.h

void stackInit();
void stackPush(int value1);
int stackPop();
int stackEmpty();
int stackTop();

Here is the implementation in the code file rsStack.c

#define STACKMAX1 32
int stack1[STACKMAX1+1];
int stackLen1;

// stack routines

void stackInit() {
	stackLen1 = 0;
	}

void stackPush(int value1) {
	stackLen1++;
	stack1[stackLen1] = value1;
	}

int stackPop() {
	int value1 = stack1[stackLen1];
	stackLen1--;
	return value1;
	}

int stackEmpty() {
	return stackLen1;
	}

int stackTop() {
	return stack1[stackLen1];
	}

Function calls can be thought of as a message passing system.

The main routine passes values to the function
The function receives values, computes values, and returns a value.
The main routine receives the value from the function and uses it.

In case you wanted to know: This is (one way, simplified as to) how the main routines interacts with a function.

The main routine calculates values for all passed parameters. These parameters are pushed on the run-time variable stack.
The function retrieves the needed values off of the stack.
On return, the function pops the passed values off of the stack and then pushes the return value on the stack.
The main function pops the return value off of the stack.