home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12255 < prev    next >
Encoding:
Text File  |  1992-08-12  |  1.9 KB  |  74 lines
  1. Xref: sparky comp.lang.c:12255 comp.programming:2292
  2. Path: sparky!uunet!cs.utexas.edu!asuvax!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  3. From: dave@cs.arizona.edu (Dave Schaumann)
  4. Newsgroups: comp.lang.c,comp.programming
  5. Subject: Re: A LITTLE BRAINTEASER...
  6. Message-ID: <1992Aug13.030019.195@organpipe.uug.arizona.edu>
  7. Date: 13 Aug 92 03:00:19 GMT
  8. References: <aet.713608023@munagin>
  9. Sender: news@organpipe.uug.arizona.edu
  10. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  11. Followup-To: comp.lang.c
  12. Organization: University of Arizona
  13. Lines: 58
  14. In-Reply-To: aet@mullian.ee.mu.OZ.AU (bert thompson)
  15.  
  16. In article <aet.713608023@munagin>, aet@mullian (bert thompson) writes:
  17. >i have a small problem that's been bugging for a while now.
  18. >
  19. >here's a program that reverses input from the keyboard:
  20. >
  21. >main()
  22. >    char ch = getchar();
  23.         ^^^^
  24. Should be `int'
  25.  
  26. >    if (ch == EOF)
  27. >        ;
  28. >    else {
  29. >        main();
  30. >        putchar(ch);
  31. >    }
  32. >}
  33. >
  34. >the interesting thing about the program is that it uses no data structures
  35. >(structs, arrays, pointers, etc..), to do its thing. everything is thrown
  36. >on the stack.
  37.  
  38. But the stack /is/ a data structure!  Just because push is defined as
  39. procedure call and pop is defined as procedure return doesn't make it
  40. any less of a data structure than if you had programmed an explicit
  41. stack.
  42.  
  43. In fact, the I/O streams you are also relying on can be considered a
  44. queue.  Using a stack as temporary storage, you can easily reverse
  45. any queue:
  46.  
  47.   queue_t queue ;
  48.   stack_t stack ;
  49.  
  50.   ...
  51.  
  52.   stack.make_empty() ;
  53.   while( !queue.empty() )
  54.     stack.push( queue.get() ) ;
  55.  
  56.   while( !stack.empty() )
  57.     queue.put( stack.pop() ) ;
  58.  
  59. Writing this as a recursive subroutine (which uses an implicit stack), you get
  60.  
  61. void reverse_queue( queue_t queue ) {
  62.  
  63.   data_t data ;
  64.  
  65.   if( !queue.empty() ) {
  66.     data = queue.get() ;
  67.     reverse_queue( queue ) ;
  68.     queue.put( data ) ;
  69.     }
  70.   }
  71.  
  72. -- 
  73. Dave Schaumann            dave@cs.arizona.edu
  74.