Stack functions as arrays instead of node pointers

Here's my first attempt to change from node pointers to arrays in linked list of stack.

Please be kind when criticizing and giving help.
I just don't have any examples in texts or lecture notes to know how to do this.

Code:

/*****************/
/*  stack.c      */
/****************/

#include <stdlib.h>
#include "stack.h"

struct node {

   int data;
   struct node * next;   /*  int str[MAX_SIZE];  */
};

struct node *first;       /*  struct node first[];  */
int count;

void make_empty()
{
   first = NULL;               /* first[0]=NULL;   */ 
   count = 0;
}

int is_empty(void)
{
   return count == 0;
}

int is_full(void)
{
   return 0;
}

void push(int insert_value)
{
   int i = 0;
   struct node *new_node;              /* struct node new[]; */ 

   new_node=malloc(sizeof(struct node));   /* new[0]=malloc(sizeof(struct node));   */ 
   if (new_node == NULL)  {         /* if (new[i] = NULL) {
      printf("Error in push:  stack is full.\n");
      exit (EXIT_FAILURE);
   }
   new_node->data = insert_value;  /* new[i]->data=insert_value; */ 
   new_node->next = first;   /* new[i]++=first[i];  */
   first = new_node;              /* first[i] = new[i];  */ 
   count++;
}

int pop(void)
{
  struct node * top_node;       /*  struct node top[MAX_SIZE];  */ 
  int i;

  if (is_empty())  {
     printf("Error in pop: stack is empty.\n");
     exit (EXIT_FAILURE);
  }

  top_node=first;        /* top[0] = first [i];  */
  i = first->data;          /* i = first[i];  */
  first = first->next;    /*  first[i++];  */ 
  free(top_node);       /*  free(top);  */ 
  count--;
  return i;
}

void print_list()
{
  struct node *ptr;     / * struct node list;  */ 
  if (first == NULL) {   /* if (first[0]=NULL) {  */
    printf("List is empty.\n\n");
  }

  else  {
       printf("\n\nHere is your list:  \n");
       for (ptr=first;ptr;ptr=ptr->next) /* for (list=first;list[i]<MAX_SIZE;list[i]++) */ 
           printf("%d\n",ptr->data);  /* printf("%d\n",list[i]); */ 
       return;
  }
}

This isn't the kind of thing where you can adjust the code really. These two implementations for a stack are so very different, it'd prolly be easiest to just rewrite your functions. The trick is to make it so that any program using those functions will not have to rewrite anthing...

An array is probably a better model for a stack than a linked list because in memory, the stack is arranged in the same way as a stack in real life.

I have a small stack of coins in front of me. I may only add or remove one coin at a time, and I may only place or remove the coin at the top of this stack. Clearly, the only coin which I can remove is the currently top coin (a quarter). If I were to add a penny to the stack, I would not be able to reach the quarter without taking off the penny, because the penny is in the way. This stack of coins clearly fulfills the programming definition of a stack.

Now, let's organize these coins as an array...

Code:

COIN array[100];
array[0] = DIME;
array[1] = NICKEL;
array[2] = QUARTER;

Okay now... let's say I want to add a penny...
addThisCoin (PENNY);
I would have to make
array[3] = PENNY
How would the computer know to put penny in array[3]? I mean, it does technically have 100 different values to choose from here. Well, I can only put the penny on top of the last element in the stack.
How does the computer know where the last element in the stack is? It doesn't, so we have to tell it.

Since we use this variable to keep track of the top of the stack, let's call it top...

Code:

int top;
top = 2;

Exellent. Now if I wanted to add a penny to the stack, it knows where to put it. However, by adding the penny to the stack, the quarter is no longer the top coin on the stack, the penny is, in array[3], so we need to update top so it becomes 3. It should be clear that every time we add a coin to the stack, the variable top is going to go up by one.

Now let's say I wanted to remove the top coin in the stack. Let's go back to the DIME, NICKEL, QUARTER stack. In that stack, how did I know that array[3] wasn't in the stack? There's 2 ways to do this, either array[3..99] could have been some invalid value, to show that they do not represent coins... or, since we already have it, we can just use the variable top to say that all the coins above it don't really exist...
If that is true, then to remove a top coin, all we really have to do is wink it out of existance by lowering top by one... Clearly we'd have had to decrease top every time I removed a coin anyhow since top HAS to refer to the top coin's position.

So, here's some more complete pseudocode...

Code:

int top = 2;
COIN array [100];

array[0] = DIME;
array[1] = NICKEL;
array[2] = QUARTER;

void addCoin (COIN c)
{
 // Be careful.  array[top] is the top coin in the stack, so we have 
 //  to increase top before doing array[top] = c, or else we'll end up 
 //  overwriting the top coin in the stack.
 top ++;
 array[top] = c;
}

void removeCoin (COIN c)
{
 // We could give array[top] some value here, but we don't have to
 //  since we're just gonna pretend it doesn't exist as long as top is
 //  below it.  The only way to make top above it is to add enough
 //  coins... but the addCoin operation would overwrite array[top] in
 //  doing so, so there isn't any problem with doing it this way.
 top --;
}

// This function is just here to show that it's quite easy to treat the
//  stack such that the coins above top don't exist.
void printCoins ()
{
 int i;
 // We can either start at the bottom or the top of the stack.  I
 //  choose to start at the bottom, but doing it from the top is similar.
 for (i = 0; i <= top; i++) // 0 is bottom of stack, top is top.
 {
  // type coin is undefined, so I can't supply a type specifier here
  printf (???, array[i]);
 }
}

I may have gone a bit far with the coin allegory, I didn't intend to just write all that which I did. Still, the code is written with the idea in mind that instead of coin, you could use any data type. If there is anything that this code should show, it is that the array implementation of a stack is much much simpler than the linked list implementation.

And my code is not quite complete....
1) What if I remover from an empty stack?
2) Since I am using an array to implement the stack, there will neccisarily be a maximum number of elements that I can put on the stack. In my example, this was 100. How should I handle a user trying to add a 101th element?

Ok, I am trying this with your help QuestionC.
I am getting a problem though.

this is my input and output after compilation as it is now:

22 /accounts/student2/srbkpk/STACK/PR5 a.out
Please enter a line of text to be printed in reverse:How are you doing?
??????????????????

here's the source file

Code:

/******************/
/*  stacka.c      */
/******************/

#include <stdlib.h>         
#include "stack.h" 
                               
int top;
int str[MAX_SIZE];
int count;

void make_empty()            
{                                        
   str[0] = NULL;                  
   count = 0;                          
}                                           

int is_empty(void)            
{                                      
   return count == 0;         
}                             

int is_full(void)             
 {
        return 0; 
}

void push(int insert_value)   
{                             
   top++;
   str[top]=insert_value;
   count++;
}

int pop(void)
{
  int i;

  if (is_empty())  {
     printf("Error in pop: stack is empty.\n");
     exit (EXIT_FAILURE);
  }

  i = str[top];
  count--;
  return i;
}

void print_list()
{
  int i;
  if (str[i] == NULL) {
    printf("List is empty.\n\n");
  }

  else  {
       printf("\n\nHere is your list:  \n");
       for (i=0;i<=top;i++)
           printf("%c\n",str[i]);
       return;
  }
}

Okay, let's clear some confusion.

In the first place, real stackframes are managed via arrays, not linked lists, anyway.

For example, your program stack is simply consecutive RAM. In other words-- an array.

To handle a stack frame effeciently, just like your processor does, using an array in stead of any structures or nodes, or linked lists, simply allocate a RAM block that is 32K in size. If you need larger, fine, if not fine. 32K is a relatively adequate size for your needs.

Next, created a stack pointer. This is simply a pointer that points to the address of your RAM block.

As you "push" stuff onto the stack, increment your stack pointer the correct amount. As you "pull" (aka "pop") stuff off the stack, decrement your stack pointer appropriately.

If your stackpointer is ever greater than your RAM block's initial address + 32K, then you halt and generate an error message stating "stack overflow".

If your stackpointer is even less than your RAM block's initial address, then you halt and generate an error message stating "stack underflow".

See... it really isn't very hard. Just do it the way your system already does it. This is why I'm always preaching for developers to learn how their O/S and CPU actually works...

enjoy.

1) Since this is an array, and not a linked list, it is actually possible to run out of memory, so you have to give a meaningful return from is_full()

2) Your stack will not know it is empty unless you tell it that it doesn't have any elements... ie, top = 0. Adjust your make_empty function accordingly.

3) When you remove an item from the stack, the top moves down by one, so your pop() function needs to include top--.

4)

Code:

if (str[i] == NULL) {
    printf("List is empty.\n\n");
  }

Tisk tisk. Use the function is_empty () instead of str[i] == NULL.

Really, doing this will be a lot easier if you realise that count and top are closely related. I mean, if you have 5 elements in your stack, then the top element will be str[4], so top = 4. It is easy to show that for any count, top = count - 1.

Knowing that, why use top at all? All you'll have to change is where you increment and decrement. For example, str[top] is the top element in the stack, so str[top + 1] = str[count] is the next available slot in the stack, so if you add an element using the count, you add the element to str[count], and then advance count.

QuestionC:

still getting problems. I assume from my make_empty function
I just don't know what to code it as. I am not following what you are saying and darn this stuff, I'd rather learn HTML I think.

Do I have to put in a for loop or something to make str[] == NULL in the make_empty function??? Buggers, this really gripes me that I don't get it!!!

My output is garbley gookey stuff and blank spaces and then it just stops and I guess that is like looking at the innards of memory space or something. So I cannot exactly printout my output for you.

Oh, the global variable called count has to be there. Don't ask me but it is supposed to be in the original stack.c file and this one. And then the source code file that has the main and both of these stack files include the same stack header file. That is why I have to use the exact same function prototypes/definitions. The darn instructor has been smoking something funny lately and really I think needs to go back to his day job. he he he

Anyways here's what I got thus far:

Code:

/******************/
/*  stacka.c                */
/******************/

#include <stdlib.h>
#include "stack.h"


int top;
int str[MAX_SIZE];
int count;

void make_empty()
{
   str[top] = NULL;
   count = 0;
}

int is_empty(void)
{
   return count == 0;
}


int is_full(void)
{
   return str[top]==MAX_SIZE;
}

void push(int insert_value)
{
   top++;
   str[top]=insert_value;
   count++;
}

int pop(void)
{
  int i;

  if (is_empty())  {
     printf("Error in pop: stack is empty.\n");
     exit (EXIT_FAILURE);
  }

  i = str[top];
  top--;
  return i;
}

void print_list()
{
  int i;
  if (is_empty) {
    printf("List is empty.\n\n");
  }

  else  {
       printf("\n\nHere is your list:  \n");
       for (i=0;i<=top;i++)
           printf("%c\n",str[i]);
       return;
  }
}

Hey I am getting close here on this stack with arrays


please tell me what is wrong. It is printing just the last 6 in reverse? I need it to print the 1st 6 or the whole string in reverse. My stack.c file is printing whole string in reverse, even with the stack limitation by the macro MAX_SIZE = 6.

Code:

     
/******************/
/*  stacka.c      */
/******************/

#include <stdlib.h>
#include "stack.h"


int top;
int str[MAX_SIZE];
int count;

void make_empty()
{
   str[MAX_SIZE] == NULL;
   count = 0;
}

int is_empty(void)
{
   return count == 0;
}


int is_full(void)
{
   return str[top]==MAX_SIZE;
}

void push(int insert_value)
{
   top++;
   str[top]=insert_value;
   count++;
}

int pop(void)
{
  int i;

  if (is_empty())  {
     printf("Error in pop: stack is empty.\n");
     exit (EXIT_FAILURE);
  }

  i = str[top];
  top--;
  count--;
  return i;
}

void print_list()
{
  int i;
  if (is_empty) {
    printf("List is empty.\n\n");
  }

  else  {
       printf("\n\nHere is your list:  \n");
       for (i=0;i<=top;i++)
           printf("%c\n",str[i]);
       return;
  }
}

I got this to work FINALLY>

Thanks QuestionC most especially for your help.

Stacks are very simple. Here's some pseudo code.

char stack[32767]; /* stack space */
char *stackPtr;

stackPtr = &stack[0]; /* init stack pointer */


/* push */

/* use memcpy() to copy object onto stack at location stackPtr */
stackPtr += sizeof(object_copied);

/* pull */

stackPtr -= sizeof(object_copied);
/*use memcpy() to copy object off stack at location stackPtr */


/* range checking */

if(stackPtr < &stack[0])
bail_out_with_error(STACK_UNDERFLOW);

if(stackPtr > (&stack[0] + 32768))
bail_out_with_error(STACK_OVERFLOW);


enjoy.