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:
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:
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.
/* * 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: