#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<list>
using namespace std;
//only for int use;
/*
class MyList{
int *my;
MyList();
int back();//返回最后一个元素
int front();//返回第一个元素
void clear();//清除所有元素
bool empty();//是否为空
void insert(int item); //插入元素
int pop_back();
int pop_front();
void push_back(int item);
void push_front(int item);
void sort();
};
MyList::MyList()
{
my=new int[N];
}
*/
//it's a program to packing
//定义结构，单链表
typedef struct MyList{
int item;
struct MyList *next;
}MyList,*List;
List head,back;
int *a=new int[];
//从尾部插入
void push_back(int item)
{
List p=head;
while(p->next!=NULL){
p=p->next;
}
List q=(List)malloc(sizeof(MyList));
q->item=item;
q->next=NULL;
p->next=q;
back=q;
}
//从头部插入
void push_front(int item)
{
List p,q;
p=head;
q=p->next;
List in=(List)malloc(sizeof(MyList));
in->item=item;
p->next=in;
in->next=q;
}
//从尾部弹出
int pop_back()
{
List p,q;
q=head;
p=q->next;
while(p->next!=NULL){
q=p;
p=p->next;
}
q->next=NULL;
back=q;
int item=p->item;
free(p);
return item;
}
//从头部弹出
int pop_front()
{
List p=head;
List q=p->next;
int item=q->item;
p->next=q->next;
free(q);
return item;
}
//移除元素值为item的所有节点
int remove(int item)
{
List p=head;
List q=p->next;
int num=;
while(q!=NULL){
if(q->item==item){
num++;
p->next=q->next;
if(p->next==back){
back=p;
}
q=p->next;
}
else{
p=p->next;
q=p->next;
}
}
return num;
}
//清除所有元素
void clear()
{
List p=head;
p=p->next;
while(p!=NULL){
List q=p->next;
int item=p->item;
free(p);
p=q;
cout<<"clear() "<<item<<endl;
}
head->next=NULL;
}
//按位置（index）插入item
void insert(int index,int item)
{
List p;
p=head;
List q=p;
p=p->next;
int i=;
while(p!=NULL){
i++;
cout<<"i:"<<i<<endl;
if(i==index){
List t=(List)malloc(sizeof(MyList));
t->item=item;
q->next=t;
t->next=p;
break;
}
q=p;
p=p->next;
}
if(i!=index)
cout<<"你输入的数字错误：please reload:"<<endl;
}
//反转list 通过记录每个节点的值，然后重新赋值
//所以会用到clear（）函数 ，及清除原来链表生成新链表
void reverse()
{
List p=head;
int i=;
while(p->next!=NULL){
p=p->next;
int item=p->item;
a[i++]=item;
}
clear();
p=head;
cout<<i<<endl;
for(int j=i-;j>=;j--)
{
List q=(List)malloc(sizeof(MyList));
q->item=a[j];
q->next=NULL;
p->next=q;
p=q;
}
}
//排序list： 通过记录每个节点的值，然后重新对值进行排序
//所以会用到clear（）函数 ，及清除原来链表生成新链表
void sort()
{
List p=head;
int i=;
while(p->next!=NULL){
p=p->next;
int item=p->item;
a[i++]=item;
}
clear();
p=head;
sort(a,a+i);
for(int j=;j<i;j++)
{
List q=(List)malloc(sizeof(MyList));
q->item=a[j];
q->next=NULL;
p->next=q;
p=q;
}
}
//返回list大小
int size()
{
List p=head;
int i=;
while(p->next!=NULL){
p=p->next;
i++;
}
return i;
}
//判断是否为空
bool isEmpty()
{
if(head->next==NULL)
return true;
return false;
}
//for test use
void print()
{
List p=head;
while(p->next!=NULL){
p=p->next;
cout<<p->item<<" ";
}
cout<<endl;
}
int main()
{
head=(List)malloc(sizeof(MyList));
back=(List)malloc(sizeof(MyList));
head->next=NULL;
back=head;
push_front();
push_front();
push_back();
push_back();
push_back();
push_back();
push_front();
push_front();
print();
sort();
cout<<"after sort()"<<endl;
print();
reverse();
print();
cout<<"size() "<<size()<<endl;
insert(,);
print();
cout<<"remove() "<<remove()<<endl;
print();
cout<<"pop_back() "<<pop_back()<<endl;
cout<<"pop_front() "<<pop_front()<<endl;
print();
clear();
print();
return ;
}