Wrox Programmer Forums
| Search | Today's Posts | Mark Forums Read
C++ Programming General discussions for the C++ language. For questions specific to Microsoft's Visual C++ variant, see the Visual C++ forum instead.
Welcome to the p2p.wrox.com Forums.

You are currently viewing the C++ Programming section of the Wrox Programmer to Programmer discussions. This is a community of software programmers and website developers including Wrox book authors and readers. New member registration was closed in 2019. New posts were shut off and the site was archived into this static format as of October 1, 2020. If you require technical support for a Wrox book please contact http://hub.wiley.com
  #1 (permalink)  
Old April 27th, 2004, 09:37 PM
Registered User
 
Join Date: Mar 2004
Location: nogales, sonora, Mexico.
Posts: 9
Thanks: 0
Thanked 0 Times in 0 Posts
Default FIFO 2 LIFO

hey guy i'm having some dificulties in trying to convert this FIFO into a LIFO, what i've done so far is that the program tells me that the char that i have eliminated is the last one but then the whole stack is empty, so i would really apreciate some pointers :D
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct queueNode
{
char data;
struct queueNode *nextPtr;
};
typedef struct queueNode QueueNode;
typedef QueueNode *QueueNodePtr;
void printQueue( QueueNodePtr );
int isEmpty( QueueNodePtr );
char dequeue( QueueNodePtr *, QueueNodePtr * );
void enqueue( QueueNodePtr *, QueueNodePtr *, char );
void instructions( void );
int main()
{
QueueNodePtr headPtr = NULL, tailPtr = NULL;
int choice;
char item;
instructions();
printf( "? " );
scanf( "%d", &choice );
while ( choice != 3 )
{
switch( choice )
{
case 1:
printf( "Introduzca un Caracter: " );
scanf( "\n%c", &item );
enqueue( &headPtr, &tailPtr, item );
printQueue( headPtr );
break;
case 2:
if ( !isEmpty( headPtr ) )
{
item = dequeue( &headPtr, &tailPtr );
printf( "%c a Sido Eliminado.\n", item );
}
printQueue( headPtr );
break;
default:
printf( "Opcion Invalida.\n\n" );
instructions();
break;
}
printf( "? " );
scanf( "%d", &choice );
}
printf( "Fin de Corrida.\n" );
return 0;
}
void instructions( void )
{
printf ( "Introduzca su Opcion:\n"
" 1 Para Insertar un Elemento a la Cola\n"
" 2 Para Eliminar un Elemento de la Cola\n"
" 3 Para Salir\n" );
}
void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value )
{
QueueNodePtr newPtr;
newPtr = new QueueNode;
if ( newPtr != NULL )
{
newPtr->data = value;
newPtr->nextPtr = NULL;
if ( isEmpty( *headPtr ) )
*headPtr = newPtr;
else
( *tailPtr )->nextPtr = newPtr;
*tailPtr = newPtr;
}
else
printf( "%c No Insertado. No Memoria Disponible.\n", value );
}
char dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr )
{
char value;
QueueNodePtr tempPtr;
value = ( *tailPtr )->data;
tempPtr = *headPtr;
*headPtr = ( *tailPtr )->nextPtr;
if ( *headPtr == NULL )
*tailPtr = NULL;
free( tempPtr );
return value;
}
int isEmpty( QueueNodePtr headPtr )
{
return headPtr == NULL;
}
void printQueue( QueueNodePtr currentPtr )
{
if ( currentPtr == NULL )
printf( "La Cola esta Vacia.\n\n" );
else
{
printf( "La Cola Es:\n" );
while ( currentPtr != NULL )
{
printf( "%c --> ", currentPtr->data );
currentPtr = currentPtr->nextPtr;
}
printf( "NULL\n\n" );
}
}


Reply With Quote
  #2 (permalink)  
Old April 28th, 2004, 07:24 PM
Friend of Wrox
Points: 2,570, Level: 21
Points: 2,570, Level: 21 Points: 2,570, Level: 21 Points: 2,570, Level: 21
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Jun 2003
Location: San Diego, CA, USA
Posts: 836
Thanks: 0
Thanked 0 Times in 0 Posts
Default

please please PLEASE format your code so that it's easy to read!
  (e.g. http://p2p.wrox.com/topic.asp?TOPIC_ID=11967)

Many editors will do it for you! Here's your code, reformatted. Any comments I have will be in the next post.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct queueNode
{
   char data;
   struct queueNode *nextPtr;
};
typedef struct queueNode QueueNode;
typedef QueueNode *QueueNodePtr;
void printQueue( QueueNodePtr );
int isEmpty( QueueNodePtr );
char dequeue( QueueNodePtr *, QueueNodePtr * );
void enqueue( QueueNodePtr *, QueueNodePtr *, char );
void instructions( void );
int main()
{
   QueueNodePtr headPtr = NULL, tailPtr = NULL;
   int choice;
   char item;
   instructions();
   printf( "? " );
   scanf( "%d", &choice );
   while ( choice != 3 )
   {
      switch( choice )
      {
      case 1:
         printf( "Introduzca un Caracter: " );
         scanf( "\n%c", &item );
         enqueue( &headPtr, &tailPtr, item );
         printQueue( headPtr );
         break;
      case 2:
         if ( !isEmpty( headPtr ) )
         {
            item = dequeue( &headPtr, &tailPtr );
            printf( "%c a Sido Eliminado.\n", item );
         }
         printQueue( headPtr );
         break;
      default:
         printf( "Opcion Invalida.\n\n" );
         instructions();
         break;
      }
      printf( "? " );
      scanf( "%d", &choice );
   }
   printf( "Fin de Corrida.\n" );
   return 0;
}
void instructions( void )
{
   printf ( "Introduzca su Opcion:\n"
      " 1 Para Insertar un Elemento a la Cola\n"
      " 2 Para Eliminar un Elemento de la Cola\n"
      " 3 Para Salir\n" );
}
void enqueue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr, char value )
{
   QueueNodePtr newPtr;
   newPtr = new QueueNode;
   if ( newPtr != NULL )
   {
      newPtr->data = value;
      newPtr->nextPtr = NULL;
      if ( isEmpty( *headPtr ) )
         *headPtr = newPtr;
      else
         ( *tailPtr )->nextPtr = newPtr;
      *tailPtr = newPtr;
   }
   else
      printf( "%c No Insertado. No Memoria Disponible.\n", value );
}
char dequeue( QueueNodePtr *headPtr, QueueNodePtr *tailPtr )
{
   char value;
   QueueNodePtr tempPtr;
   value = ( *tailPtr )->data;
   tempPtr = *headPtr;
   *headPtr = ( *tailPtr )->nextPtr;
   if ( *headPtr == NULL )
      *tailPtr = NULL;
   free( tempPtr );
   return value;
}
int isEmpty( QueueNodePtr headPtr )
{
   return headPtr == NULL;
}
void printQueue( QueueNodePtr currentPtr )
{
   if ( currentPtr == NULL )
      printf( "La Cola esta Vacia.\n\n" );
   else
   {
      printf( "La Cola Es:\n" );
      while ( currentPtr != NULL )
      {
         printf( "%c --> ", currentPtr->data );
         currentPtr = currentPtr->nextPtr;
      }
      printf( "NULL\n\n" );
   }
}


Take care,

Nik
http://www.bigaction.org/
Reply With Quote
  #3 (permalink)  
Old April 28th, 2004, 07:55 PM
Friend of Wrox
Points: 2,570, Level: 21
Points: 2,570, Level: 21 Points: 2,570, Level: 21 Points: 2,570, Level: 21
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Jun 2003
Location: San Diego, CA, USA
Posts: 836
Thanks: 0
Thanked 0 Times in 0 Posts
Default

Okay, after reviewing your code, I have a couple questions.

Are you programming in C or C++? You use primarily C conventions, but use 'new' to allocate a new node, which is a C++ operator. You deallocate nodes using free(), which is a C function that frees pointers allocated by malloc(). The C++ operator to deallocate memory allocated w/ 'new' is 'delete'.

Either way, I suggest you create a struct or class to represent the Stack itself, that way, you don't have to maintain head and tail pointers to the structure. The stack is not very useful to the programmer that uses it because there's too much knowledge involved in it's use. You should be able to say:

  stack.enqueue('c'); // the C++ OOP way.

or

  enqueue(pStack, 'c'); /* the C way */


Also, if there is a subtle logic flaw in your code, then stepping through your code in a debugger will likely point out where you've gone wrong.

If you don't have access to a debugger, or don't really know how to use one effectively, I suggest you get one and learn. In addition (or instead of), you can trace your logic manually (on paper, whiteboard, chalkboard, etc). Just draw pictures to represent your structure when the program starts, as you insert a couple items, and as you remove them.



Take care,

Nik
http://www.bigaction.org/
Reply With Quote
  #4 (permalink)  
Old April 28th, 2004, 07:58 PM
Friend of Wrox
Points: 2,570, Level: 21
Points: 2,570, Level: 21 Points: 2,570, Level: 21 Points: 2,570, Level: 21
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Jun 2003
Location: San Diego, CA, USA
Posts: 836
Thanks: 0
Thanked 0 Times in 0 Posts
Default

ALL that being said (whew), you need to look at your enqueue() and dequeue() logic. A LIFO (Last In First Out) structure is called a Stack. Typically, adding things onto the stack is called "pushing" it onto the stack. Removing things is called "popping" the stack. You might want to rename enqueue and dequeue to push() and pop() to stick with convention.

On to your push/pop logic. You're implementing a stack using a singly-linked list -- that is, a list of nodes that store a pointer to the next node in the list. If you read the code for your enqueue() function, you push an item onto the stack by appending it after the LAST node in the list (the TAIL).

This is not the ideal solution, because there's no easy way to get to the node before the tail. You need to access this because after you free the last node, you need to reset the tail pointer to the new tail node.

Here's a visual representation of what I mean. Imagine you have a stack where you've inserted the letters 'a', 'b', and 'c':

       +-----+ +-----+ +-----+
       | a | --> | b | --> | c |
       +-----+ +-----+ +-----+
          ^ ^
 Head ----+ |
 Tail ---------------------------+


Now when you dequeue, you want to remove the 'c'. But that means you need to set Tail to the node containing 'b'. This isn't easy to do because you have to start at Head and iterate all the way until you find the node where (node->next == Tail). This is an inefficient way to search for items, since the time it takes to search is linearly proportional to the length of the list.


What's the better solution, then? Since you have arrows pointing in only one direction, it would be better to insert new items at the HEAD of the list, not at the tail. That way, when you pop an item off, you don't need to search through the list at all -- the new Head = (Head->next).


       +-----+ +-----+ +-----+
       | c | --> | b | --> | a |
       +-----+ +-----+ +-----+
          ^ ^
 Head ----+ |
 Tail ---------------------------+

     (remove 'c')
node * nextHead = Head->next;
free(Head);
Head = nextHead;

       +-----+ +-----+
       | b | --> | a |
       +-----+ +-----+
          ^ ^
 Head ----+ |
 Tail ---------------+



If you take a moment to examine this approach, you realize that you don't need to store a second pointer to the Tail anymore. You never use it. The only reason you had a tail pointer was so you could insert at one location but remove at another. Now you insert and remove from the same place. That means you enqueue and dequeue (well, push n' pop) functions don't need to accept the TAIL pointer. You know when you're at the tail node because the next ptr of that node will be NULL.


Hope this helps get you on your way...


Take care,

Nik
http://www.bigaction.org/
Reply With Quote
  #5 (permalink)  
Old May 2nd, 2004, 06:41 PM
Registered User
 
Join Date: Mar 2004
Location: nogales, sonora, Mexico.
Posts: 9
Thanks: 0
Thanked 0 Times in 0 Posts
Default

ok i think i did what you said here's my code

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct queueNode
{
   int data;
   struct queueNode *nextPtr;
};
typedef struct queueNode QueueNode;
typedef QueueNode *QueueNodePtr;
void printQueue( QueueNodePtr );
int isEmpty( QueueNodePtr );
int dequeue( QueueNodePtr *, QueueNodePtr * );
void enqueue( QueueNodePtr *, QueueNodePtr *, int );
void instructions( void );
int main()
{
   QueueNodePtr headPtr = NULL, tailPtr = NULL;
   int choice;
   int item;
   instructions();
   printf( "? " );
   scanf( "%d", &choice );
   while ( choice != 3 )
   {
      switch( choice )
      {
      case 1:
         printf( "Introduzca un Caracter: " );
         scanf( "\n%c", &item );
         enqueue( &headPtr, &tailPtr, item );
         printQueue( headPtr );
         break;
      case 2:
         if ( !isEmpty( headPtr ) )
         {
            item = dequeue( &headPtr, &tailPtr );
            printf( "%c a Sido Eliminado.\n", item );
         }
         printQueue( headPtr );
         break;
      default:
         printf( "Opcion Invalida.\n\n" );
         instructions();
         break;
      }
      printf( "? " );
      scanf( "%d", &choice );
   }
   printf( "Fin de Corrida.\n" );
   return 0;
}
void instructions( void )
{
   printf ( "Introduzca su Opcion:\n"
      " 1 Para Insertar un Elemento a la Cola\n"
      " 2 Para Eliminar un Elemento de la Cola\n"
      " 3 Para Salir\n" );
}
void enqueue( QueueNodePtr *headPtr, int value )
{
   QueueNodePtr newPtr;
   newPtr = new (QueueNode);
   if ( newPtr != NULL )
   {
      newPtr->data = value;
      newPtr->nextPtr = *headPtr;
      *headPtr = newPtr;
   }
   else
      printf( "%c No Insertado. No Memoria Disponible.\n", value );
}
int dequeue( QueueNodePtr *headPtr )
{
   QueueNodePtr tempPtr;
   int value;

   tempPtr = *headPtr;
   value = ( *headPtr )->data;
   *headPtr = ( *headPtr )->nextPtr;
   free( tempPtr );
   return value;
}

void printQueue( QueueNodePtr currentPtr )
{
   if ( currentPtr == NULL )
      printf( "La Cola esta Vacia.\n\n" );
   else
   {
      printf( "La Cola Es:\n" );
      while ( currentPtr != NULL )
      {
         printf( "%c --> ", currentPtr->data );
         currentPtr = currentPtr->nextPtr;
      }
      printf( "NULL\n\n" );
   }
}

when i compile it it doesn't mark any errors, but then when i try to run it i get these:
! ERROR: Unresolved external 'enqueue(queueNode**,queueNode**,int)' referenced from C:\MY DOCUMENTS\MY STACK.OBJ
! ERROR: Unresolved external 'isEmpty(queueNode*)' referenced from C:\MY DOCUMENTS\MY STACK.OBJ
! ERROR: Unresolved external 'dequeue(queueNode**,queueNode**)' referenced from C:\MY DOCUMENTS\MY STACK.OBJ

Reply With Quote
  #6 (permalink)  
Old May 5th, 2004, 06:25 PM
Registered User
 
Join Date: Mar 2004
Location: nogales, sonora, Mexico.
Posts: 9
Thanks: 0
Thanked 0 Times in 0 Posts
Default

i've never come across with these kinda errors so if anybody could help i would be really happy, cuz to tell the truth even when my teacher saw this errors he didn't knew what they were

Reply With Quote
  #7 (permalink)  
Old May 13th, 2004, 06:44 PM
Friend of Wrox
Points: 2,570, Level: 21
Points: 2,570, Level: 21 Points: 2,570, Level: 21 Points: 2,570, Level: 21
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Jun 2003
Location: San Diego, CA, USA
Posts: 836
Thanks: 0
Thanked 0 Times in 0 Posts
Default

Your teacher didn't know what unresolved externals were? That's not a good sign. Typically, an unresolved external means that you're code calls a function that's declared somewhere, but never implemented. An example:


/* main.c */

int do_stuff(void);

int main(int argc, char ** argv)
{
    return do_stuff();
};


This will not compile because do_stuff() is never implemented. This usually happens because you're including a header and using functions defined in that header, but not linking in the objects created when compiling that header's corresponding C++ file.

If you look at your code, you declare all the functions giving you problems, but you didn't actually implement those functions. That is, you didn't write the functions, you just gave them names.


Take care,

Nik
http://www.bigaction.org/
Reply With Quote




Similar Threads
Thread Thread Starter Forum Replies Last Post
LIFO in Array mafuka C++ Programming 3 April 22nd, 2004 06:15 PM
FIFO mafuka C++ Programming 4 March 26th, 2004 12:34 PM





Powered by vBulletin®
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright (c) 2020 John Wiley & Sons, Inc.