[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]

                           Turbo Pascal for DOS Tutorial
                                by Glenn Grotzinger
                            Part 12: Stacks and Queues
                     copyright(c) 1995-96 by Glenn Grotzinger

    Solution to part 11's problem....

    program part11; uses dos;

      { Lists files and data in a ZIP file. }

      type
        ziplocfileheader = record
          zipver: integer;
          bitfield: word;
          compmethod: integer;
          packtime: longint;
          crc32: longint;
          compsize: longint;
          uncompsize: longint;
          filelen: integer;
          xtralen: integer;
        end;

        zipcds = record
          ver: byte;
          hostos: byte;
          verxtr: byte;
          targos: byte;
          bitfield: word;
          compmethod: integer;
          packtime: longint;
          crc32: longint;
          compsize: longint;
          uncompsize: longint;
          filelen: integer;
          xtralen: integer;
          comtlen: integer;
          disknum: integer;
          intattr: integer;
          extattr: longint;
          roffset: longint;
        end;

        endcdsheader = record
          numdisk: integer;
          numdiska: integer;
          numfiles: integer;
          entries: integer;
          size: longint;
          ofs: longint;
          comtlength: integer;
        end;

      var
        zipfile: file;
        outfile: text;
        locfile: ziplocfileheader;
        dirstr: zipcds;
        endcds: endcdsheader;
        filechar: char;
        filelength: array[1..20] of char;
        id: array[1..4] of char;
        i: integer;
        totsize, compsize, uncompsize: longint;
        param1, param2: string;

      { Example structure of a ZIP file.
          localheader1
          loccompresseddata1
          localheader2
          loccompresseddata2
          centraldirectorystructure1
          centraldirectorystructure2
          endofcentraldirectorystructure }

      procedure readzip;

        { ZIP is a random data binary file.  We read the ID to check it, then
          differentiate it from there.  We also devise a test of whether the
          "ZIP file" is a valid ZIP file here. }

        begin
          blockread(zipfile, id, sizeof(id));
          totsize := totsize + 4; { totsize is a seek index }
          if (id[1] <> 'P') and (id[2] <> 'K') then
            begin
              writeln('Corrupted ZIP file, or not a ZIP file.');
              halt(1);
            end;
          case id[3] of
            #05: begin
                   blockread(zipfile, endcds, sizeof(endcds));
                   totsize := totsize + sizeof(endcds);
                 end;
            #03: begin
                   blockread(zipfile, locfile, sizeof(locfile));
                   totsize := totsize + sizeof(locfile);
                 end;
            #01: begin
                   blockread(zipfile, dirstr, sizeof(dirstr));
                   totsize := totsize + sizeof(dirstr);
                 end;
          end;
        end;

      function zero(int: integer):string;
        {places zero on the beginning of a number if it's < 10 }
        var
          strng: string;
          numerr: integer;
        begin
          str(int, strng);
          if int < 10 then
            strng := '0' + strng;
          zero := strng;
        end;

      function strip(str: string):string;

        { removes null characters from random-read filename }

        var
          tstr: string;
          i: integer;
        begin
          tstr := '';
          for i := 1 to length(str) do
            if str[i] <> #0 then
              tstr := tstr + str[i];
          strip := tstr;
        end;

      function exist(filename: string):boolean;
        { file existence test }
        var
          thefile: text;
        begin
          assign(thefile, filename);
          {$I-}reset(thefile);{$I+}
          if IOResult <> 0 then
            exist := false
          else
            begin
              exist := true;
              close(thefile);
            end;
        end;

      procedure header(filename: string);
        { writes header of data }
        var
          s: string;
        begin
          writeln(outfile, 'Files contained in ':41, filename);
          writeln(outfile);
          writeln(outfile, 'NAME', 'COMP-SIZE':21, 'DATE':9,'TIME':12,
                  'UNCOMP-SIZE':15, 'COMP-METHOD':13);
          fillchar(s, 75, '-');
          { fillchar fills a set of contiguous bytes of any type defined by
            the position s is in, for x number of spaces (75), with a char-
            acter represented by - }
          s[0] := #74;  { set length byte }
          writeln(outfile, s);
        end;

      procedure footer(compsize, uncompsize: longint);
        { write footer of data }
        var
          s: string;
        begin
          fillchar(s, 75, '-');
          s[0] := #74;
          writeln(outfile, s);
          writeln(outfile, compsize:22, uncompsize:34);
          writeln(outfile);
          writeln(outfile, endcds.numfiles, ' files; Effective compression',
                           ' ratio: ', (compsize / uncompsize)*100 :0:1, '%');
        end;

      procedure writehelp;
        { help for incorrect usage }
        begin
          writeln('ZIPLIST <zipfile> <datafile>');
          halt(1);
        end;

      procedure writedata(locfile: ziplocfileheader);
        var
          dt: datetime;
        begin
          unpacktime(locfile.packtime, dt);
          { this handles the MS-DOS time format }
          writeln(outfile, strip(filelength):12, locfile.compsize:10,
          zero(dt.month):7,'-',zero(dt.day),'-',dt.year,
          zero(dt.hour):6,':', zero(dt.min),
          locfile.uncompsize:10, locfile.compmethod:12);
        end;

      begin
        if paramcount <> 2 then  { incorrect parameters? }
          writehelp;
        totsize := 0;compsize := 0;uncompsize := 0;
        param1 := paramstr(1);
        param2 := paramstr(2);
        assign(zipfile, param1);
        if exist(param1) = false then
          begin
            writeln(param1, ' does not exist!');
            halt(1);
          end;
        reset(zipfile, 1);
        assign(outfile, param2);
        rewrite(outfile);

        header(param1);
        readzip;

        while id[3] = #03 do
         { process local file headers and compressed data }
          begin
            blockread(zipfile, filelength, locfile.filelen);
            compsize := compsize + locfile.compsize;
            uncompsize := uncompsize + locfile.uncompsize;
            writedata(locfile);
            totsize := totsize + locfile.filelen;
            totsize := totsize + locfile.xtralen;
            fillchar(filelength, sizeof(filelength),#0);
            seek(zipfile, totsize);
            totsize := totsize + locfile.compsize;
            seek(zipfile, totsize);
            readzip;
          end;

        while id[3] = #01 do
          { process central directory structure }
          begin
            totsize := totsize + dirstr.filelen;
            seek(zipfile, totsize);
            totsize := totsize + dirstr.xtralen;
            seek(zipfile, totsize);
            readzip;
          end;

        footer(compsize, uncompsize);

        writeln(outfile);

        { handle ZIP comment }
        if endcds.comtlength = 0 then
          writeln(outfile, 'No comment in ZIP file.')
        else
          for i := 1 to endcds.comtlength do
            begin
              blockread(zipfile, filechar, sizeof(filechar));
              write(outfile, filechar);
            end;

        close(zipfile);
        close(outfile);
      end.

    Hello.  Basically, we are dealing in this part with specialized types of
    data structures called stacks and queues.

    Stacks
    ======
    A stack is best analagous to a stack of papers on a desk, only able to
    either place a sheet on the top of the stack, or take a sheet off the
    top of the stack.  It is generally defined as a record format, which
    can take on the following:

    stack = record
      elements: array[1..maxstacksize] of <whatever>;
      capacity: integer; {range of 0..maxstacksize}
    end;

    It is best described as a last in/ first out data structure, much like the
    sheet of paper analogy.  The elements array holds whatever information
    we need, while capacity tells us how many elements are still in the array.

    The best description I can use for this and queues is that it's a limited
    defined access structure.

    I will now describe the basic actions of working with stacks.  The best
    way to think about coding this is to use the stack of paper as a view-
    point, and using the sample stack record above.

    To initialize or effectively kill a stack currently in usage is to set
    capacity to 0.  We can do this, because all work with a stack ultimately
    comes down to usage of capacity as an index.  If we have 0 sheets of paper
    on an imaginary stack, essentially, the stack is empty.

    Now, let's add a sheet of paper to our imaginary stack.  We recognize that
    there is one more sheet of paper on the stack now.  Then we have to place
    that sheet on the stack...also, we have to keep in mind if we have hit our
    arbitrarily set limit of sheets on the stack, and notify of such thing.

    What now, if we have to remove the sheet of paper from our imaginary stack
    of paper?  We would need to check if we had a sheet of paper to remove.
    Then after that, we would need to pull the sheet off of the stack, then
    recognize that we removed the sheet.

    How do we recognize if we have a full stack or an empty stack?  Look at the
    value of capacity.  If it's 0, then it's empty.  If it's the value for the
    maximum capacity of the stack we decide, then we know it's full.

    Basically, in the last four paragraphs, I have, in discussing the actions
    of working with stacks, have given you all the pseudocode you need to
    be able to come up with the code to work with a stack.

    It is basically good to develop all of these components as procedures.
    If you come across a problem where a last in, first out solution is
    needed, a stack may be the proper way to go.

    Queues
    ======
    A queue is set up much like a line at the local shop to pay the merchant
    at the cash register.  The first element in is the first element out.
    Much like a stack, a queue may be defined as a record format.

    queue = record
      elements: array[1..maxqueuesize] of <whatever>;
      front, back: integer;
      count: integer;
    end;

    Notice that the differences we see here, are that to take from the front
    of the so called line we need to know where the front is in the order.
    The same idea occurs with the back.  We need to know where the back is
    in the array.  Count just helps us in knowing how many values we currently
    have in the queue.

    To start up a queue, basically, we need to start the front at 1, the rear
    at the maximum size, and count at zero.

    To check whether it's full or  empty is basically set through count.  Check
    count to be zero for a queue to be empty and maxsize for a queue to be full.

    One sticky mess comes up when we try to add an element to the back of the
    line.  How do we keep track of things?  We increment the back unless it's
    maxqueuesize, then we set it to 1, essentially, to continue reusing the
    array storage as a loop....

    To add to the back of the line, we do like we did with the stack.  We add
    the element to the back, then we increment the back count as described
    above.

    To take from the front of the line, we pull the element from the front of
    the queue, and then increment the front count as described above.

    Basically, the effect we are getting is much like a message scrolling
    across a surface, like you may have seen on your television, and at
    Times Square in NY (on several movies).

    Conclusion
    ==========
    Both of these data storage schemes work beautifully, when you have a lot of
    data to deal with that can be passed through quickly, but needs to be
    released at other times...beyond that, at this point, I can't think of
    anything that can be done by only using a stack or a queue, so my
    suggestion for practice is to attempt coding each of these specialized
    data types to do simple things.

    Practice Programming Problem(s) #12
    ===================================
    Here are a couple of things for this one.

    1) Reverse a string of text inputted from the screen (not necessarily
    a string) of a maximum of 500 characters, and output the text back to
    the screen.

    Sample
    ------
    Enter a string: AbCdE

    Your string reversed is: EdCbA

    2) Use a queue to store a maximum set of numbers that is 50 numbers long.
    These numbers will come from a series of randomly generated numbers by your
    program.  The random numbers you will generate are from 1..1000, and
    the ones that are from 1..50 will be written out to the screen when the
    queue is filled up with those numbers.  Write the numbers in the queue out
    in 5 rows of 10, and at the bottom, write out the total number of random
    numbers you had to go through to get those 50 numbers in the proper range.

    Sample
    ------
    23 23 11 22 33 1 9 12 23 11
    23 3 11 22 33 11 9 12 23 11
    23 23 11 22 33 11 9 12 23 11
    23 29 11 2 33 11 9 12 23 11
    23 23 11 22 33 11 9 50 23 11

    987 numbers were generated from 1-1000 to get the 50 numbers from 1-50.

    Next Time
    =========
    Recursion. (n) See Recursion. :>

    Any comments?  Write ggrotz@2sprint.net.

[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]