A project for Data Structures by Dave Schoeffler during the Fall 2011 semester.

This project was begun on October 10th and was completed on November 7th.

The purpose of this project is to explore the nature of stacks through their use in various functions. This project will also require an understanding of malloc(), structs, pointers. and passing them to functions. The understanding of the preceding will allow me to successfully create a stack data structure.

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

• understand functions
• understand pointers
• understand structs
• understand malloc()
• ability to create a linked data structure
• ability to create a stack data structure

The point of this project is to implement a stack that will store characters.

A stack is a data structure that is made up of a group of “nodes” that store data. Here is what a stack is http://lab46.corning-cc.edu/opus/fall2011/dschoeff/start#stacks. A stack is very similar to a linked list in that it is composed of nodes(structs) that contain data and a pointer to the next node. The difference in stacks is that the only way to add or remove data is from the top. This is known as a LIFO data structurehttp://lab46.corning-cc.edu/opus/fall2011/dschoeff/start#lifo.

This project will implement a stack the stores character data. It will give the user functionality to manipulate the stack by adding nodes to the top of the stack and removing nodes from the top of the stack. There will also be a function that will allow the user to view the value on the top of the stack without changing any of the nodes.

To better utilize the functionality of the stacks we've been studying in class, a personal implementation for use as a library will be undertaken for use in other projects and activities this semester.

Working from the class example, a library implementation will be created which has the following functions:

• pop: remove a node from the top of the stack
• push: add a value to the top of the stack
• peek: return the value on the top of the stack without changing the data structure

• pointers: pointers are at the heart of dynamic structures.
• malloc/new: dynamic memory allocation.
• linked lists: this code is going to implement linked lists.
• doubly linked lists: not only is the code implementing a linked list, it is implementing doubly linked lists.
• libraries: this code will be part of a library that can be reused in other projects
• stacks: this code will implement the use of stacks

/****************************************************************                         
* Header file. This includes the node structure for the stack   *
* data structure. This also inlcludes the function protypes for *
* the stack manipulation functions.                             *
****************************************************************/
#ifndef _STACK_H
#define _STACK_H
#include "linkedlist.h"
struct stack {
   int count;
   struct node *top;
   struct node *data;
   struct node *tmp;
};
typedef struct stack Stack;
Stack *push(Stack* start, char value);
char pop(Stack* );
void displayStack(Stack* start);
char peek(Stack* start );
#endif

/***********************************************************                              
* Function push() will create a stack if no stack currently*
* exists. If a stack does exist, push() will add a node to *
* the top of the stack. It will then return the updated    *
* stack.                                                   *
* Compile with: gcc -c push.c                              *
*                                                          *
***********************************************************/
#include "stack.h"
#include<stdio.h>
#include<stdlib.h>
Stack *push(Stack *start, char input)
{
   Node *tmp;
   if(start == NULL)
   {   
      start = (Stack *) malloc (sizeof(Stack));
      start -> data = malloc(sizeof(Node));
      start -> top = malloc(sizeof(Node));
      start -> tmp = malloc(sizeof(Node));
      start -> top -> value = input;
      start -> top -> next = NULL;
      start -> data = start -> top;
   }   
   else
   {   
      tmp = (Node *) malloc (sizeof(Node));
      tmp -> value = input;
      tmp -> next = start -> top;
      start -> top = tmp;
   }   
   return (start);
}

/******************************************************************                       
* Function pop() accepts as an argument a stack. It will then pop *
* the node that is currently on the top and make the node under   * 
* that the new top. It will then return the value that from the   *
* popped node as a character. If the stack that is passed is NULL *
* (meaning it does not exist), the function cannot pop a node that*
* doesn't exist. Therefore, the function will return the null     *
* terminating character.                                          *
*                                                                 *
* Compile with: gcc -c pop.c                                      * 
*                                                                 * 
**************************************************************** */
#include "stack.h"
#include <stdlib.h>
char pop(Stack *start)
{
  char chartmp;
  start -> tmp = start -> top;
  if(start -> tmp != start -> data)
  {
     start -> top = start -> top -> next;
     start -> tmp -> next = NULL;
     chartmp = start -> tmp -> value;
  }
  else if(start -> data == NULL)
  {
     chartmp = '\n';
  }
  else
  {
     chartmp = start -> top -> value;
     start -> top = start -> tmp = start -> data = NULL;
  }
 
  return(chartmp);
}

/***********************************************                                          
* Function peek() simply returns the value that*
* is held on the top node.                     *
*                                              *
* Compile with: gcc -c peek.c                  *
***********************************************/
#include "stack.h"
#include <stdlib.h>
char peek(Stack *start)
{
   char tmp;
   if(start -> top == NULL)
   {   
      tmp = '\n';
   }   
   else
   {   
      tmp = start -> top -> value;
   }   
   return (tmp);
}

/********************************************************************                     
*  A Project for Data Structures                                    *
*  Author: Dave Schoeffler                                          *
*  Purpose: This program implements the "stack.h" header file which *
*         for the creation and manipulation of a stack. The program *
*         will allow the user to choose from a menu what operation  *
*         they would like to perform. Those operations include pop  *
*         , push and peek.                                          *
*                                                                   *
*  Compile with: gcc -o stack stack.c -L. -lstack                   *
*                                                                   *
*  Execute with: ./stack                                            *
*                                                                   *
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
 
int main()
{
   char input, input2, junk, tmp;
   int i = 0;
   Stack *start;
 
   start = NULL;
 
   printf("Enter - 1 - to pop a Node off of the stack\n");
   printf("Enter - 2 - to push a Node on the stack\n");
   printf("Enter - 3 - to peek at the value on top of the stack\n");
   printf("Enter - q - to quit\n");
   scanf("%c",&input2);
   scanf("%c",&junk);
   while( input2 != 'q')
   {   
      switch(input2)
      {
         case '1':
            tmp = pop(start);
            printf("The value that was pooped is: %c\n", tmp);
            break;
         case '2':
            printf("Enter value for new node: ");
            scanf("%c",&input);
            scanf("%c",&junk);
            start = push(start, input);
            break;
         case '3':
            printf("The top node contains the value: %c\n", peek(start));
            break;
         case 'q':
            break;
      }
      printf("Enter - 1 - to pop a Node off of the stack\n");
      printf("Enter - 2 - to push a Node on the stack\n");
      printf("Enter - 3 - to peek at the value on top of the stack\n");
      printf("Enter - q - to quit\n");
      scanf("%c",&input2);
      scanf("%c",&junk);
   }
 
   return(0);
}         

I will load a stack with the string “qwerty” and then pop each of those values off.

lab46:~/stack$ ./stack
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: q
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: w
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: e
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: r
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: t
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: y
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: y
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: t
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: r
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: e
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: w
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: q
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
1
The value that was pooped is: 

Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
q
lab46:~/stack$

example of peek

lab46:~/stack$ ./stack
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
2
Enter value for new node: x
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
3
The top node contains the value: x
Enter - 1 - to pop a Node off of the stack
Enter - 2 - to push a Node on the stack
Enter - 3 - to peek at the value on top of the stack
Enter - q - to quit
q
lab46:~/stack$

So this project took a whole lot longer than I expected. I ran into a few problems that were based in how I constructed my doubly linked list library. I actually had to go back to my doubly linked library and change a few things before I could go forward. I eventually got all my problems figured out with that and was able to move on to the main meat of the project. I probably did everything you could possibly do wrong with stacks at first and this showed as my functions weren't working at all. I kept on getting the dreaded Segmentation Fault! After working through these problems I was able to get my functions working and get them working in an efficient matter. I feel like having done so many things wrong at first really helped me get a better understanding of how stacks work. I feel like moving on I will be able to implement stacks in many different situations.

• http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29
• C++ Programming D.S. Malik
• Matthew Haas
• a few other internet sources I do not remember :)