#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
  int data;
  struct Node * next;
} Node;

typedef Node* List;

void display_list(List head) {
  while (head != NULL) {
    printf("%d->", head->data);
    head = head->next;
  }
  printf("fin\n");
}

int size_list(List head) {
  int n=0;
  while (head != NULL) {
    head= head->next;
    n++;
  }
  return n;
}

bool add_head(List& Head, int d) {
  List e = new Node;
  if (e == NULL)
    return false;
  e->data = d;
  e->next = Head;
  Head=e;
  return true;
}

bool append_end(List& Head, int d) {
  List t;
  List e = new Node;
  if (e == NULL) {
    return false;
  }
  e->data = d;
  e->next = NULL;
  if (Head == NULL)
    Head = e;
  else {
    t= Head;
    while (t->next != NULL)
      t= t->next;
    t->next=e;
  }
  return true;
}

bool delete_head(List& Head) {
  List t;

  if (Head== NULL)
    return false;
  t = Head;
  Head =t->next;
  free(t);
  return true;
}

bool delete_end (List& Head) {
  List t, p;
  if (Head== NULL)
    return false;
  if (Head->next ==NULL) {
    free(Head);
    Head = NULL;
  } else {
    t = Head->next;
    while (t->next != NULL) {
      p=t ;
      t= t->next;
    }
    p->next=NULL;
    free(t);
  }
  return true;
}

void delete_list(List &Head) {
  while (delete_head(Head));
}

typedef struct Queue {
  struct Node* first, *last;
  int size;
} Queue;

Queue * initQ() {
  Queue *Q=new Queue;
  Q->first =NULL;
  Q->last =NULL;
  Q->size =0;
}

bool isEmpty(Queue *Q) {
  return Q->size ==0;
}

void enQueue(Queue *Q, int x) {
  Node *e = new Node;
  e->data = x;
  e->next = NULL;
  if(isEmpty(Q))
    Q->first =e;
  else
    Q->last->next =e;
  Q->last =e;
  Q->size++;
}

int deQueue(Queue *Q) {
  Node* t;
  int x;
  if(isEmpty(Q)) {
    printf("error: Queue is empty");
    exit(1);
  }
  t = Q->first;
  x = t->data;
  Q->first = t-> next;
  free(t);
  Q->size--;
  return x;
}

int Pop(List& Head) {
  List t;
  int x;
  if(Head==NULL) {
    printf("error: Stack is empty");
    exit(1);
  }
  t = Head;
  Head =t-> next;
  x=t->data;
  free(t);
  return x;
}

void Push(List& Head, int x) {
  List e = new Node;
  e-> data = x;
  e-> next = Head;
  Head=e;
}

int main() {

  return 0;
}