IZLAZNI KOLOKVIJ - 16.02.2018.

// 1. zadatak
int* stack = (int*)malloc(10 * sizeof(int));
int size = 10;
int sp = -1;

bool IsEmpty() { return (sp == -1); }

bool IsFull() { return (sp == size - 1); }

void Push(int x) {
    if (IsFull()) {
        size += 10;
        stack = (int*)malloc(size * sizeof(int));
    }
    sp++;
    stack[sp] = x;
}

int Pop() {
    if (IsEmpty()) {
        printf("Stack is empty!");
        return -1;
    }
    int x = stack[sp];
    sp--;

    return x;
}

int main(void) {
    char arr[] = { '1', '15', '*', '3', '+', '1', '4', '*', '*' };
    for (int i = 0; i < 9; i++)  {
        if (arr[i] == '+') {
            Push(Pop() + Pop());
        }
        else if (arr[i] == '*') {
            Push(Pop() * Pop());
        }
        else {
            Push(arr[i]);
        }
    }
    return 0;
}

// 2. zadatak
struct Node
{
    int data;
    struct Node* next;
};

void newList(struct Node *p1, struct Node *p2, int n) {
    int count = n;
    struct Node* p1_new = (struct Node*)malloc(sizeof(struct Node));
    struct Node* p2_new = (struct Node*)malloc(sizeof(struct Node));

    while (count-- > 0) {
        p1_new->data = p1->data;
        p2_new->data = p2->data;
        p1 = p1->next;
        p2 = p2->next;
        p1_new->next = (struct Node*)malloc(sizeof(struct Node));
        p1_new = p1_new->next;
        p2_new->next = (struct Node*)malloc(sizeof(struct Node));
        p2_new = p1_new->next;
    }

    while (p1->next != NULL && p2->next != NULL) {
        p1_new->data = p2->data;
        p2_new->data = p1->data;
        p1 = p1->next;
        p2 = p2->next;
        p1_new->next = (struct Node*)malloc(sizeof(struct Node));
        p1_new = p1_new->next;
        p2_new->next = (struct Node*)malloc(sizeof(struct Node));
        p2_new = p1_new->next;
    }

    p->next = NULL;

    for (int i = 0; i < n; i++) {
        p1 = p1->next;
        p2 = p2->next;
    }

    struct Node* temp = p1;
    p1->next = p2->next;
    p2->next = temp->next;
    free(temp);
}

// 3. zadatak
struct Node{
    int data;
    struct Node* next;
};

struct Node* front = NULL;
struct Node* rear = NULL;

void Enqueue(int x) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    temp->next = NULL;
    if (front == NULL && rear == NULL){
        front = rear = temp;
        return;
    }
    rear->next = temp;
    rear = temp;
}

void Dequeue() {
    struct Node* temp = front;
    if (front == NULL) {
        printf("Queue is Empty\n");
        return;
    }
    if (front == rear) {
        front = rear = NULL;
    }
    else {
        front = front->next;
    }
    free(temp);
}

bool IsEmpty() {
    return front == NULL && rear == NULL;
}

bool IsFull() {
    return rear->next != NULL;
}

// 4. zadatak
struct cvor {
    int x;
    struct cvor *left, *right;
};

void ubaci(struct cvor *r, struct cvor *p) {
    if ((r->right == NULL) && (p->x > r->x)) {
        r->right = p;
    }
    else if ((r->right != NULL) && (p->x > r->x)) {
        ubaci(r->right, p);
    }
    if ((r->left == NULL) && (p->x < r->x)) {
        r->left = p;
    }
    else if ((r->left != NULL) && (p->x < r->x)) {
        ubaci(r->left, p);
    }
}

void preorderIterative(Node *root)
{
    push(root);

    while (!empty())
    {
        Node *curr = pop();
        cout << curr->data << " ";

        if (curr->right) { push(curr->right); }
        if (curr->left) { push(curr->left); }
    }
}