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

typedef struct Node *NodePtr;
typedef struct Node{
	int data;
	NodePtr next;
}Node;

int empty(NodePtr top){
	if(top==NULL){
		return 1;
	}else{
		return 0; 
	}
}



void push(int data,NodePtr *top){
	NodePtr newNode = (Node*)malloc(sizeof(Node));
	newNode->data=data;
	newNode->next=*top;
	
	*top = newNode;
}

NodePtr pop(NodePtr *top,NodePtr *backup_top){
	if(empty(*top)==1){
		return NULL;
	}else{
		//store 
		int data = (*top)->data;
		push(data,backup_top);
		//pop
		NodePtr current=*top;
		*top = (*top)->next;
 		return current;
	}	
} 

void prints(NodePtr *top){
	NodePtr current=*top;
	int i=1;
	while(current!=NULL){
		printf("%d ",current->data);
		current = current->next;
		if(i%10==0&&i!=1){
			printf("\n");
		}
		i++;
	}
	printf("\n");
}

void random_generate_number(NodePtr *top){
	srand(time(NULL));
	int i;
	for(i=1;i<=50;i++){
		int number=rand()%10;
		push(number,top);
	}
}


void freeList(NodePtr *top) {
    NodePtr current = *top;
    NodePtr next;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }

    *top = NULL;
}



int main(){
	

	NodePtr top=NULL;
	NodePtr backup_top=NULL;

	//p1.指定m 的數值為頂端算起的第三元素，且不改變堆疊
	random_generate_number(&top);
	int i;
	int m;
	printf("原亂數 :\n");
	prints(&top);
	printf("Q1 : 指定m 的數值為頂端算起的第三元素，且不改變堆疊\n\n");
	for(i=0;i<3;i++){
		m=(pop(&top,&backup_top))->data;
	}
	printf("m=%d\n\n",m); 
	
	for(i=0;i<3;i++){
		int data=backup_top->data;
		int n=(pop(&backup_top,&top))->data;
	}
	prints(&top);
	
	freeList(&top);
	freeList(&backup_top);
	
	
	//p2. 指定m 的數值為頂端算起的第十二元素，且不改變堆疊
	random_generate_number(&top);
//	printf("原亂數 :\n");
//	prints(&top);
	printf("Q2 : 指定m 的數值為頂端算起的第十二元素，且不改變堆疊\n\n");
	for(i=0;i<12;i++){
		m=(pop(&top,&backup_top))->data;
	}
	printf("m=%d\n\n",m); 
	
	for(i=0;i<12;i++){
		int data=backup_top->data;
		int n=(pop(&backup_top,&top))->data;
	}
	prints(&top);
	
	freeList(&top);
	freeList(&backup_top);
	
	//p3. 指定m 的數值為底端，且不改變堆疊
	random_generate_number(&top);
//	printf("原亂數 :\n");
//	prints(&top);
	printf("Q3 : 指定m 的數值為底端，且不改變堆疊\n\n");
	for(i=0;i<50;i++){
		m=(pop(&top,&backup_top))->data;
	}
	printf("m=%d\n\n",m); 
	
	for(i=0;i<50;i++){
		int data=backup_top->data;
		int n=(pop(&backup_top,&top))->data;
	}
	prints(&top);
	
	freeList(&top);
	freeList(&backup_top);
	
	//p4. 指定m 的數值為底端算起的第二元素，且不改變堆疊。
	random_generate_number(&top);
//	printf("原亂數 :\n");
//	prints(&top);
	printf("Q4 : 指定m 的數值為底端算起的第二元素，且不改變堆疊\n\n");
	for(i=0;i<49;i++){
		m=(pop(&top,&backup_top))->data;
	}
	printf("m=%d\n\n",m); 
	
	for(i=0;i<49;i++){
		int data=backup_top->data;
		int n=(pop(&backup_top,&top))->data;
	}
	prints(&top);
	
	freeList(&top);
	freeList(&backup_top);
	
	//p5. 指定m 的數值為底端算起的第三元素，且不改變堆疊
	random_generate_number(&top);
//	printf("原亂數 :\n");
//	prints(&top);
	printf("Q5 : 指定m 的數值為底端算起的第三元素，且不改變堆疊\n\n");
	for(i=0;i<48;i++){
		m=(pop(&top,&backup_top))->data;
	}
	printf("m=%d\n\n",m); 
	
	for(i=0;i<48;i++){
		int data=backup_top->data;
		int n=(pop(&backup_top,&top))->data;
	}
	prints(&top);
	
	freeList(&top);
	freeList(&backup_top);
	
	//p6. 指定m 的數值為底端算起的第四元素，且不改變堆疊
	random_generate_number(&top);
//	printf("原亂數 :\n");
//	prints(&top);
	printf("Q6 : 指定m 的數值為底端算起的第四元素，且不改變堆疊\n\n");
	for(i=0;i<47;i++){
		m=(pop(&top,&backup_top))->data;
	}
	printf("m=%d\n\n",m); 
	
	for(i=0;i<47;i++){
		int data=backup_top->data;
		int n=(pop(&backup_top,&top))->data;
	}
	prints(&top);
	
	freeList(&top);
	freeList(&backup_top);
}