Programexempel från Progmet-föreläsning 6, tisdag 21 september 2010
===================================================================

Planering för idag:

1. Mer om tidskomplexitet, inlämningsuppgift 2
2. Två abstrakta datatyper: Stackar och köer
       Kö: FIFO (First In, First Out)
       Stack: LIFO (Last In, First Out)
3. Olika implementationer av stack och kö
4. En stack "direkt i programmet"
5. En stack som en abstrakt datatyp: "StackOfDoubles"
6. En annan implementation av samma "StackOfDoubles"
7. En generisk stack ur standardbiblioteket i C++: std::stack
8. En kö "direkt i programmet"
9. En generisk kö ur standardbiblioteket i C++: std::queue
10. Läs mer



1. Mer om tidskomplexitet, inlämningsuppgift 2
==============================================

Exempel 1:

Hundkojan är 1x1x1 meter,
lagerlokalen är 10x10x10 meter,
VAB är 100x100x100 meter.

N är sidan (1, 10 eller 100 meter).

Att plantera blommor runt väggen är O(N).
Att måla golvet är O(N^2).
Att fylla huset med pingisbollar är O(N^3).
Att ta kort på huset är O(1)

Ignorera konstanter!

Tid(N) = 1.02 N = O(N)
Tid(N) = 1000000 N = O(N)
Tid(N) = 1.02 N + 17 = O(N)

Bara de dominerande termerna!

Tid(N) = 0.000000000001 N^2 + 3 = O(N^2)
Tid(N) = 1000000 N + 17 = O(N)

Traveling salesman-problemet, fullständig sökning: O(N!)

Exempel 2:

Tiden det tar att måla en ballong: O(n^2)
Tiden det tar att blåsa upp ballongen: O(n^3)

En ballong med diametern 1 dm tar 1 minut att måla och 1 minut att blåsa upp
En ballong med diametern 2 dm tar 4 minuter att måla och 8 minuter att blåsa upp
En ballong med diametern 10 dm tar 100 minuter att måla och 1000 minuter att blåsa upp

Men det behöver inte vara exakt Tid(n)=n^2. Exempel:

Tiden det tar att måla en ballong: Tid(n) = 2.17 n^2 + 3 = O(n^2)
Tiden det tar att blåsa upp ballongen: O(n^3) = 0.19 * n^3 + 1.4 * n^2 + 26 = O(n^3)

Tiden det tar att gå förbi ballongen: Tid(n) = n/2 = O(n)
Tiden det tar att titta på ballongen: Tid(n) = 7 = O(1)



2. Två abstrakta datatyper: Stackar och köer
============================================

Kö: FIFO (First In, First Out)
Prioritetskö: sorterad i prioritetsordning
Stack: LIFO (Last In, First Out)
FILO? LILO?
Datorer: GIGO...



3. Olika implementationer av stack och kö
=========================================

"Stack" och "kö" är abstrakta datatyper.
De är inte länkade listor, arrayer, filer eller något annat.
Men de kan implementeras ("förverkligas") med hjälp av
länkade listor, arrayer, filer eller något annat.



4. En stack "direkt i programmet"
=================================

pushpop-1.cpp
-------------

// pushpop-1.cpp -- push och pop på en stack

#include <stdlib.h>
#include <stdio.h>

#define STACK_MAX_SIZE 100

double stack[STACK_MAX_SIZE];
int stack_size = 0;

int main(void) {
    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            stack[stack_size++] = the_number;
        }
        else {
            double the_number = stack[--stack_size];
            printf("Poppat tal: %f\n", the_number);
        }
        printf("Antal element på stacken nu: %d\n", stack_size);
    }

    return 0;
}



pushpop-2.cpp
-------------

// pushpop-2.cpp -- push och pop på en stack, med mer felkontroll

#include <stdlib.h>
#include <stdio.h>

#define STACK_MAX_SIZE 100

double stack[STACK_MAX_SIZE];
int stack_size = 0;

int main(void) {
    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            if (stack_size == STACK_MAX_SIZE) {
                printf("Stacken är redan full!\n");
            }
            else {
                printf("Vilket tal? ");
                double the_number;
                scanf("%lf", &the_number);
                stack[stack_size++] = the_number;
            }
        }
        else if (operation == 2) {
            if (stack_size == 0) {
                printf("Stacken är redan tom!\n");
            }
            else {
                double the_number = stack[--stack_size];
                printf("Poppat tal: %f\n", the_number);
            }
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element på stacken nu: %d\n", stack_size);
    }

    return 0;
}



5. En stack som en abstrakt datatyp: "StackOfDoubles"
=====================================================

StackOfDoubles.h
----------------

// StackOfDoubles.h

#ifndef STACKOFDOUBLES_H
#define STACKOFDOUBLES_H

#define STACKOFDOUBLES_MAX_SIZE 100

struct StackOfDoubles {
    double data[STACKOFDOUBLES_MAX_SIZE];
    int size;
};

extern StackOfDoubles *SOD_create(void);
extern void SOD_destroy(StackOfDoubles *this_stack);
extern int SOD_size(StackOfDoubles *this_stack);

extern void SOD_push(StackOfDoubles *this_stack, double new_data);
extern double SOD_pop(StackOfDoubles *this_stack);
extern double SOD_peek(StackOfDoubles *this_stack);
extern double SOD_is_empty(StackOfDoubles *this_stack);

#endif
// #ifndef STACKOFDOUBLES_H



StackOfDoubles.cpp
------------------

// StackOfDoubles.cpp

#include <stdlib.h>
#include <stdio.h>
#include "StackOfDoubles.h"

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "StackOfDoubles: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

StackOfDoubles *SOD_create(void) {
    StackOfDoubles *this_stack = (StackOfDoubles *) safe_malloc(sizeof(StackOfDoubles));
    this_stack->size = 0;
    return this_stack;
}

void SOD_destroy(StackOfDoubles *this_stack) {
    free(this_stack);
}

extern int SOD_size(StackOfDoubles *this_stack) {
    return this_stack->size;
}

void SOD_push(StackOfDoubles *this_stack, double new_data) {
    if (this_stack->size == STACKOFDOUBLES_MAX_SIZE) {
        fprintf(stderr, "StackOfDoubles: Stack is full (%d elements).\n", STACKOFDOUBLES_MAX_SIZE);
        exit(EXIT_FAILURE);
    }
    this_stack->data[this_stack->size++] = new_data;
}

double SOD_pop(StackOfDoubles *this_stack) {
    if (this_stack->size == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return this_stack->data[--this_stack->size];
}

double SOD_peek(StackOfDoubles *this_stack) {
    if (this_stack->size == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return this_stack->data[this_stack->size - 1];
}

extern double SOD_is_empty(StackOfDoubles *this_stack) {
    return this_stack->size == 0;
}



pushpop-3.cpp
-------------

// pushpop-3.cpp -- push och pop på en stack

#include <stdlib.h>
#include <stdio.h>
#include "StackOfDoubles.h"

int main(void) {
    StackOfDoubles *stack = SOD_create();

    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            SOD_push(stack, the_number);
        }
        else if (operation == 2) {
            double the_number = SOD_pop(stack);
            printf("Poppat tal: %f\n", the_number);
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element på stacken nu: %d\n", SOD_size(stack));
    }

    SOD_destroy(stack);

    return 0;
}



6. En annan implementation av samma "StackOfDoubles"
====================================================

StackOfDoubles.h
----------------

// StackOfDoubles.h

#ifndef STACKOFDOUBLES_H
#define STACKOFDOUBLES_H

#include "ListOfDoubles.h"

struct StackOfDoubles {
    ListOfDoubles* the_list;
};

extern StackOfDoubles *SOD_create(void);
extern void SOD_destroy(StackOfDoubles *this_stack);
extern int SOD_size(StackOfDoubles *this_stack);

extern void SOD_push(StackOfDoubles *this_stack, double new_data);
extern double SOD_pop(StackOfDoubles *this_stack);
extern double SOD_peek(StackOfDoubles *this_stack);
extern double SOD_is_empty(StackOfDoubles *this_stack);

#endif
// #ifndef STACKOFDOUBLES_H



// StackOfDoubles.cpp
---------------------

#include <stdlib.h>
#include <stdio.h>
#include "ListOfDoubles.h"
#include "StackOfDoubles.h"

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "ListOfDoubles: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

StackOfDoubles *SOD_create(void) {
    StackOfDoubles *this_stack = (StackOfDoubles *) safe_malloc(sizeof(StackOfDoubles));
    this_stack->the_list = LOD_create();
    return this_stack;
}

void SOD_destroy(StackOfDoubles *this_stack) {
    LOD_destroy(this_stack->the_list);
    free(this_stack);
}

extern int SOD_size(StackOfDoubles *this_stack) {
    return LOD_length(this_stack->the_list);
}

void SOD_push(StackOfDoubles *this_stack, double new_data) {
    LOD_insert_first(this_stack->the_list, new_data);
}

double SOD_pop(StackOfDoubles *this_stack) {
    if (LOD_length(this_stack->the_list) == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    double result = LOD_get_first(this_stack->the_list);
    LOD_remove_first(this_stack->the_list);
    return result;
}

double SOD_peek(StackOfDoubles *this_stack) {
    if (LOD_length(this_stack->the_list) == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return LOD_get_first(this_stack->the_list);
}

extern double SOD_is_empty(StackOfDoubles *this_stack) {
    return LOD_length(this_stack->the_list) == 0;
}



7. En generisk stack ur standardbiblioteket i C++: std::stack
=============================================================

pushpop-4.cpp
-------------

// pushpop-4.cpp -- push och pop på en stack, med std::stack

#include <stdlib.h>
#include <stdio.h>
#include <stack>

int main(void) {
    std::stack<double> stack;

    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            stack.push(the_number);
        }
        else if (operation == 2) {
            double the_number = stack.top();
            stack.pop();
            printf("Poppat tal: %f\n", the_number);
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element på stacken nu: %d\n", (int)stack.size());
    }

    return 0;
}



8. En kö "direkt i programmet"
==============================

putget-1.cpp
------------

// putget-1.cpp -- put och get på en kö

#include <stdlib.h>
#include <stdio.h>

#define QUEUE_MAX_LENGTH 100

double queue[QUEUE_MAX_LENGTH];
int queue_length = 0;

int main(void) {
    while (1) {
        printf("Put (1) eller get (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            queue[queue_length++] = the_number;
        }
        else {
            double the_number = queue[0];
            for (int i = 1; i < queue_length; ++i)
                queue[i - 1] = queue[i];
            --queue_length;
            printf("Talet som stod först i kön: %f\n", the_number);
        }
        printf("Antal element i kön nu: %d\n", queue_length);
    }

    return 0;
}



9. En generisk kö ur standardbiblioteket i C++: std::queue
==========================================================

putget-2.cpp
------------

// putget-2.cpp -- put och get på en kö, med std::queue

#include <stdlib.h>
#include <stdio.h>
#include <queue>

int main(void) {
    std::queue<double> queue;

    while (1) {
        printf("Put (1) eller get (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            queue.push(the_number);
        }
        else if (operation == 2) {
            double the_number = queue.front();
            queue.pop();
            printf("Talet som stod först i kön: %f\n", the_number);
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element i kön nu: %d\n", (int)queue.size());
    }

    return 0;
}



10. Läs mer
===========

Lästips om Komplexitetsteori
----------------------------

Vi lär oss det där med data: Grunderna om komplexitet
(http://basen.oru.se/kurser/progmet/2010-2011-p1/texter/thomas/komplexitet/index.html)

Janlert et al, "Datatyper och algoritmer", 2000: s 36-37 och kapitel 12, särskilt avsnitt 12.2

Weiss, "Data Structures and Algorithm Analysis in C++", 3d Ed, 2006: kapitel 2, särskilt avsnitt 12.1



Lästips om stackar och köer
---------------------------

Gunnar Jokis kompendium (på kursens hemsida): avsnitt 3.1 (s 41-49)

(Men missförstå inte kapitel 3: Stackar och köer är INTE en sorts länkade istor!
De är inte heller arrayer, filer eller något annat.
De är abstrakta datatyper, som kan implementeras ("förverkligas") med hjälp av
länkade listor, arrayer, filer eller något annat.)

Bilting, "Vägen till C", 2000:
s 158-160 om en implementation av en stack
s 297 om programstacken (där funktionsanrop lagras)
s 288 om ett bättre sätt att implementera en kö som en array

Weiss, "Data Structures and Algorithm Analysis in C++", 3d Ed, 2006:
avsnitt 3.6 om stackar
avsnitt 3.7 om köer

Janlert et al, "Datatyper och algoritmer", 2000:
kapitel 7 om den abstrakta datatypen stack
kapitel 8 om den abstrakta datatypen kö