Trouble with Linked List Stacks

This is a discussion on Trouble with Linked List Stacks within the C Programming forums, part of the General Programming Boards category; I've created a program where I read in a certain amount of data from an input file, place it in ...

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    38

    Trouble with Linked List Stacks

    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?

  2. #2
    Registered User
    Join Date
    May 2004
    Posts
    127
    Code:
    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.
    Code:
    #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.

  3. #3
    Registered User
    Join Date
    Apr 2004
    Posts
    38
    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.

  4. #4
    Registered User
    Join Date
    May 2004
    Posts
    127
    >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.
    Code:
    int main(void)
    {
      struct list *head1 = NULL; /* First stack */
      struct list *head2 = NULL; /* Second stack */
    
      [...]
    }

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Linked lists are amazingly simple, especially double linked lists. However, for a stack, FILO, single work just fine.
    Code:
    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:
    Code:
    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.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Apr 2004
    Posts
    38
    I'm having a problem with the following code:
    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:

    Code:
    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?

  7. #7
    Registered User penney's Avatar
    Join Date
    Jan 2003
    Posts
    47
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 01:48 PM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21