A project for Data Structures by Tyler Galpin during the Fall 2011.

This project took about one day to complete and was completed on November 16th, 2011.

The point of this project is to make a usable Stack library that can be used not only in a test implementation, but can be applied to any program that may make use of a stack comprised of a linked list. Through this, a greater understanding of what a stack is should be attained.

In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

• Understanding of linked list
• Understanding of doubly linked list
• Basic understanding of what a stack is
• Understanding of pointers

As previously stated, a working Stack library is the goal. It should be able to manipulate the data in the stack however we need it to. As is such,the following functions must be in it:

• Push–Add a node, FILO style
• Pop– Remove a node, FILO style
• Display– Display stack, make note of where top and bottom is

The implementation is relatively straightforward. I just need it to demonstrate that the logic of a stack is present. For this, a menu is included in the main part of the program to let you choose which function you'd like to test.

• linked list: The stack is based off of a linked list
• doubly linked list: The stack uses a doubly linked list.
• pointers: make up the backbone of the data structure
• malloc: needed in the creation of new stacks/nodes
• stack: …Hey, this is a stack, isn't it?
• library: That is what is being made/used!
• File I/O: Used in main.c for test implementation

/*
 * Stack implementation -- header file
 *
 * Fall2011 Data Structures
 */
 
#ifndef _STACKLIB_H
#define _STACKLIB_H
 
// Include files
#include <stdio.h>
#include <stdlib.h>
 
// Create our node structure
struct node {
	int value;
	struct node *next;
	struct node *prev;
};
typedef struct node Node;
 
Node *stack, *top, *tmp;
 
void push(int);
void pop();
void displayStack();
//int isEmpty(); (Figure this out later)
 
#endif

/*
 * Stack implimentation -- main
 *
 * Fall2011 Data Structures
 */
 
#include "stacklib.h"
 
int main()
{
	int i, input, choice;
	puts("Please enter a value (-1 to stop:): ");
	scanf("%d", &input);
	while(input != -1)
	{
		push(input);
		puts("Please enter a value (-1 to stop:): ");
		scanf("%d", &input);
	}
	puts("Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]");
	scanf("%d", &choice);
	while (choice != 0)
	{
		if (choice == 1)
		{
			input=0;			
			puts("Please enter a value (-1 to stop:): ");
			scanf("%d", &input);
			while(input != -1)
			{
				push(input);
				puts("Please enter a value (-1 to stop:): ");
				scanf("%d", &input);
			}
			input=0;
		}
		else if (choice == 2)
		{
			pop();
		}
		else if (choice == 3)
		{
			displayStack();
		}	
		puts("Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]");
		scanf("%d", &choice);
	}
/*
	while((tmp=pop())!=NULL)
	{
		printf("value: %d\n", tmp->value);
		free(tmp);
	}
*/
	return(0);
}

#include "stacklib.h"
 
void push(int value)
{
	if (stack==NULL)
	{
		stack = (Node *) malloc(sizeof(Node));
		top=stack;
		stack->next=NULL;
		stack->prev=NULL;
		tmp=stack;
		stack->value=value;
	}
	else if (stack == top)
	{
		tmp= (Node *) malloc(sizeof(Node));
		top->next=tmp;
		tmp->prev=top;
		top=top->next;
		top->value=value;
		top->next=NULL;
	}
	else
	{
		tmp=stack;
		int i=0;
	       	while(tmp != NULL)
	        {   
        	        i++;
                	tmp=tmp->next;
       		}   
        	tmp = (Node *) malloc (sizeof(Node));
        	top -> next = tmp;
        	tmp -> prev = top;
        	top = top -> next;
        	top -> value = value;
        	top -> next = NULL;
	}
}

#include"stacklib.h"
 
void pop()
{
	tmp=top;
	tmp->prev->next=NULL;
	top=top->prev;
	tmp->prev=NULL;
	free(tmp);
}

#include"stacklib.h"
 
void displayStack()
{
	int n=0;
	tmp=top;
	printf("\n[Top of Stack]\n");
	while(tmp != NULL)
	{
		printf("[%d]: %d\n", n+1,tmp->value);
		n++;
		tmp=tmp->prev;
	}
	printf("[Bottom of Stack]\n");
}

This is how to compile and execute:

lab46:~/src/data/stack$ ar rcs libdll.a *.o
lab46:~/src/data/stack$ gcc -o testimple main.c -L. -ldll
lab46:~/src/data/stack$ ./testimple

I was able to complete this project with relative ease. It was an interesting project to work on, and I learned a good bit about stacks from it. It's a short jump from the stack project to a queue, and all it takes is some manipulation of the functions from here to do that.

In performing this project, the following resources were referenced:

• Matt Haas + Class lecture
• Fellow classmates (simple discussion about the aspects of our personal implementations)
• C Programming Language O'Reilly Pocket Reference