Trouble with Linked List Stacks

[ChristianTool]

I've created a program where I read in a certain amount of data from an input file, place it in a queue, and then I'm supposed to split the information between 4 different stacks. I've been provided with some stack/queue code for Enqueuing, Dequeueing, etc. but I don't see how I can declare 4 stacks in the same program. Any suggestions?

[Kip Neuhart]

T stack1[SIZE];
T stack2[SIZE];
T stack3[SIZE];
T stack4[SIZE];

Any questions?

A well designed stack will allow for multiple simultaneous instances within the program. For example.

#include <stdio.h>
#include <stdlib.h>

typedef struct stack xstack;

struct stack {
  int *base;
  int  size;
  int  top;
};

xstack *make_xstack(int size);
void destroy_xstack(xstack *stack);
int empty_xstack(xstack *stack);
int top_xstack(xstack *stack);
void push_xstack(xstack *stack, int item);
void pop_xstack(xstack *stack);

int main(void)
{
  xstack *stack1;
  xstack *stack2;
  int i;

  stack1 = make_xstack(10);
  stack2 = make_xstack(10);
  for (i = 0; i < 10; i++) {
    push_xstack(stack1, i);
    push_xstack(stack2, i * i);
  }
  while (!empty_xstack(stack1)) {
    printf("%d : %d\n", top_xstack(stack1), top_xstack(stack2));
    pop_xstack(stack1);
    pop_xstack(stack2);
  }
  destroy_xstack(stack1);
  destroy_xstack(stack2);

  return 0;
}

Because each function works on a pointer to xstack passed as an argument, you don't need to use any global or stack data and multiple stacks can be maintained at any given time.

[ChristianTool]

That's some seriously confusing code.

In your declaration, you wrote T stack1[SIZE]; T stack2[SIZE]; etc.
Wouldn't that be declaring it as a stack with array implementation? Because I can't use it. My professor insists we use only linked list implementation.

[Kip Neuhart]

>That's some seriously confusing code.
I'm sorry.

>Wouldn't that be declaring it as a stack with array implementation?
Yes, it would. But the nice thing about stacks is that if you do it right, the implementation doesn't matter. It will be hidden behind the interface functions. For a linked implementation, you only need to maintain two separate lists and you'll have two stacks provided you only add and remove at one end.

int main(void)
{
  struct list *head1 = NULL; /* First stack */
  struct list *head2 = NULL; /* Second stack */

  [...]
}

[quzah]

Linked lists are amazingly simple, especially double linked lists. However, for a stack, FILO, single work just fine.

struct stack
{
    struct node *head;
};

int getsize( struct stack *s ); /* count the list elements */
struct node *pop( struct stack *s ); /* pop one */
int push( struct stack *s, struct node *n ); /* push one */
struct node *newnode( type data );

All of these functions take maybe five lines tops. You would of course need to create your linked list structure for node, which will hold whatever data you actually plan on using.

But then, whenever you feel like making as many lists as you want, you simply:

struct stack s1, s2;
struct node *n = NULL;

n = newnode( somevalue );
push( &s1, n );
n = newnode( someothervalue );
push( &s2, n );

I'll leave the miscellaneous house keeping functions for you to figure out. But the point is, it's quite simple. Post your attempt, specific problems and errors, etc, if you're stuck.

Quzah.

[ChristianTool]

I'm having a problem with the following code:

NODEPTR curr, temp;
curr = (*headPtr);

while ( curr != NULL )
   {
      curr -> data = Dequeue ( headPtr, tailPtr );
      temp = CreateNode();
      SetData ( temp, curr -> data );
      Push ( &top1, temp );
      PrintStack ( top1 );
      curr = curr -> next;
   }

This code sets curr to the value of head, or the beginning of the queue. Dequeue sets the value of the info dequeued into curr -> data. temp is then set to the new node. SetData takes the new node and the enters the data into the node. Then, Push enters that data into the stack. curr = curr-> next is supposed to enable the loop to traverse the queue until it's finished.

The problem is, I'm getting a segfault when I use the SetData function. The code for it is below:

void SetData (NODEPTR temp, CAR value)
{
   temp -> data = value;
}

When I Dequeue into a temporary CAR, and just do SetData(temp, tempCar), it works fine, but won't traverse the queue. I've put probes everywhere to determine the Seg Fault is coming from that function. Any ideas?

[penney]

Prior to using a pointer you should make sure that it is pointing to something and therefore is not NULL. Therefore, in your SetData routine place the following check:

if( temp ) /* It's pointing to something */
temp->data=value; /* assuming value and data are ints. If data is a string then use strcpy */

Also, how is NODEPTR defined?