//顺序表的静态存储,空间不可变
#define N 100
typedef int SLDataType;/*数据类型的别名*/

typedef struct SeqList
{
    SLDataType arr[N];/*定长数组*/
    size_t size;/*有效元素个数*/
}; SeqList

//顺序表的动态存储,空间可变
typedef int SLDataType;/*数据类型的别名*/

typedef struct SeqList
{
    SLDataType* _data;/*需要动态开辟的数组*/
    size_t size;/*有效元素个数*/
    size_t _capacity;/*容量,当前可以存放的最大元素个数*/
}; SeqList

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

typedef int SLDataType;

typedef struct SeqList
{
    SLDataType* _data;/*需要动态开辟的数组*/
    size_t _size;/*有效元素个数*/
    size_t _capacity;/*容量,当前可以存放的最大元素个数*/
} seqList;

void initSeqList(seqList* sl){
    sl->_data = NULL;
    sl->_size = sl->_capacity = 0;
}
//尾插一个数据
void checkCapacity(seqList* sl){
    //检查是否为空指针
    if (sl == NULL)
        return;
    //如果元素个数和容量相同,说明空间满了,需要扩容
    if (sl->_size == sl->_capacity){
        int newCapacity = sl->_capacity == 0 ? 1 : 2*sl->_capacity;
        //开一个更大的空间,拷贝原数据,释放原空间
        SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
        //内存拷贝
        memcpy(tmp, sl->_data, sizeof(SLDataType)* sl->_size);
     //释放原来空间
        free(sl->_data);
    //更新
        sl->_data = tmp;
        sl->_capacity = newCapacity;
    }
}
void pushBack(seqList* sl, SLDataType val){
    //检查容量
    checkCapacity(sl);
    sl->_data[sl->_size] = val;
    ++sl->_size;
}
void printSeqList(seqList*sl)
{
    for (int i = 0; i < sl->_size; ++i){
        printf("%d ", sl->_data[i]);
    }
    printf("\n");
}

//尾删一个数据
void popBack(seqList* sl){
    if (sl == NULL)
        return;
    if (sl->_size > 0)
        sl->_size--;
}
//头插:给顺序表第一个位置插入元素
//一般不进行头插,效率低
void pushFront(seqList* sl, SLDataType val){
    if (sl == NULL)
        return;
    //0.检查容量
    checkCapacity(sl);
    //1.移动元素,从后向前移动,以免覆盖元素
    int end = sl->_size;
    while (end > 0){
        sl->_data[end] = sl->_data[end - 1];
        --end;
    }
    //2.头插
    sl->_data[0] = val;
    sl->_size++;
}

//头删
void popFront(seqList* sl){
    if (sl == NULL || sl->_size==0)
        return;
    int start = 1;/*起始位置*/
    while (start < sl->_size){
        /*从前往后移动*/
        sl->_data[start - 1] = sl->_data[start];
        ++start;
    }
    --sl->_size;
}

void test (){
    seqList sl;
    initSeqList(&sl);
    pushBack(&sl, 1);
    pushBack(&sl, 2);
    pushBack(&sl, 3); 
    pushBack(&sl, 4);
    pushBack(&sl, 5);
    printSeqList(&sl);
    popBack(&sl);
    printSeqList(&sl);
    popBack(&sl);
    printSeqList(&sl);
    popBack(&sl);
    printSeqList(&sl);
    popBack(&sl);
    printSeqList(&sl);
    popBack(&sl);
    printSeqList(&sl);
    pushBack(&sl, 6);
    printSeqList(&sl);
    pushFront(&sl, 0);
    pushFront(&sl, -1);
    pushFront(&sl, -2);
    pushFront(&sl, -3);
    printSeqList(&sl);
    popFront(&sl);
    printSeqList(&sl);
    popFront(&sl);
    printSeqList(&sl);
    popFront(&sl);
    printSeqList(&sl);
    popFront(&sl);
    printSeqList(&sl);
    popFront(&sl);
    printSeqList(&sl);
}

int main(){
    test();
    system("pause");
    return 0;
}