Lesson 16

Stack

• It’s a linear data structure

• it’s a LIFO data structure: Last In, First Out

  • push: can only add elements on top of the stack

  • pop: can only remove elements on top of the stack

  • peek: can view the top item of the stack

  • is_full: when you have a fixed sized stack and each element is been allocated. Helps prevent data overflow.

  • is_empty: when there are no items in the stack. Helps prevent data underflow.

• It’s a more constrained version of linked list

• The first element is the top, the last is the bottom of the stack

Queue

• It’s a linear data structure

• Similar to a checkout line in a store, it’s a FIFO data structure: First In, First Out.

  • enqueue: Adds a node at the beginning of the queue

  • dequeue: Removes a node at the end of the queue

• It’s also a more constrained version of linked list

• The first element is called head and the last is called a tail

Binary Tree

• It’s a non-linear data structure.

• Trees contain contains 2 or more links. In the case of a Binary Tree, it only contains only 2.

• The root node is the first node in the tree

• Children of a node are called siblings

• Each node could have a left child (root of a subtree) and a right child (root of another subtree)

• A child with no children is called a leaf node

• There are 3 ways to traverse a binary tree

  • Pre order

  • In order

  • Post Order

• Example

          49
      28      83
    18  40  71  97
  
    Pre-Order  (Left / Print / Right) : 49 - 28 - 18 - 40 - 83 - 71 - 97
    In-Order   (Left / Print / Right) : 18 - 28 - 40 - 49 - 71 - 83 - 97
    Post-Order (Left / Print / Right) : 18 - 40 - 28 - 71 - 97 - 83 - 49
  
    Pre-Order recursive priority  (Print / Left / Right) :
        1st
    2nd     3rd
  
    In-Order recursive priority  (Left / Print / Right) :
        2nd
    1st     3rd
  
    Post-Order recursive priority  (Left / Right / Print) :
        3rd
    1st     2nd
  

File Processing

• Files are used to persist data

• There are 2 accessibility types: sequential-access and random-access

• Files are considered a stream of data. So we can say we have a stream of data when we open a file.

• Files are terminated wither with an end-of-file marker (EOF available in stdio.h) or a character maintained used by the program.

• Every program is associated to 3 files:

  • stdin: standard input

  • stdout: standard output

  • stderr: standard error

• FILE *open(const char *file_name, const char *mode); opens a file where

  • FILE * is the pointer to the stream of data. returns 0 if file could not be opened.

  • const char *file_name is the name of the file

  • const char *mode is the mode we are writing the file in

    • Read operations

      • r open in read mode

      • rb opens in binary write mode

      • r+ opens in write + read mode

      • rb+ opens or creates in write + read binary mode

    • Write operations discarding content if any exist

      • w opens or creates in write mode

      • w+ opens or creates in write + read mode

      • wb opens or creates in binary write mode

      • wb+ opens or creates in write + read binary mode

    • Write operations maintaining content and appending to the end

      • a opens or creates in write mode but writes to the end of file

      • a+ opens or creates in write + read mode but writes to the end of the file

      • ab opens or creates in write binary mode but appends to the end of file

      • ab+ opens or creates in write binary mode but appends to the end of file

Character & String manipulators for streams: fgetc, fputc, fgets and fputs

• int fgetc(FILE *stream); Reads a character from a data stream

  • int is the character read from the stream

  • FILE *stream is the stream read from (including stdin).

  • Returns an int read which may mean:

    • A character read

    • EOF (end-of-file) if reached the end of file or if an error occurred

• int fputc(char c, FILE *stream); Writes a character to a data stream

  • char c is the char we want to write

  • FILE *stream is the stream read from (including stdout).

  • Returns an int written which may mean:

    • A character written

    • EOF (end-of-file) if reached the end of file or if an error occurred

• char *fgets(char *str, int size, FILE *stream); reads a line from a data stream - adds a NULL terminator (\0)

  • char *str extracts the string into an already existing string

  • FILE *stream is the stream read from (including stdin).

  • Returns char * read which may mean

    • A pointer to str on success.

    • EOF (end-of-file) if reached the end of file or if an error occurred

• int fputs(const char str, FILE *stream); puts a string into a data stream

  • const char str is the stream being written

  • FILE *stream is the stream read from (including stdin).

  • Returns int written which may mean

    • A pointer to str on success.

    • EOF (end-of-file) if reached the end of file or if an error occurred

Data manipulators for streams: fscanf and fprintf

• int fscanf(FILE *stream, const char format, ...); reads data from a data stream using specific format - does not add the NULL terminator (\0)

  • FILE *stream is the stream read from (including stdin).

  • const char format the format specifier (eg. %d, %s, etc)

  • ... data to read from data stream

  • Returns int which may mean

    • The number of successfully read items.

    • EOF if an error or end of file occurs.

• int fprintf(FILE *stream, const char format, ...); writes data into a data stream using specific format

  • FILE *stream is the stream read from (including stdout).

  • const char format the format specifier (eg. %d, %s, etc)

  • ... data to write into data stream

  • Returns int which may mean

    • The number of successfully written items.

    • Negative value if an error or end of file occurs.