数据结构：栈、队列、排序、 算法的复杂度

一、栈和队列
栈和队列都是对结点操作位置有要求的特殊线性表
栈（先进后出）----->子弹入膛
队列（先进先出）----->食堂排队
二、栈（数据结构）
1.概念
    线性表的插入（压栈）和删除（出栈）都只能在同一个端点进行，不能在其他位置，这样的结构称之为栈
2.分类
    顺序栈、链式栈（带头结点的单向不循环链表）
3.特性
    后进先出，一端是完全封死的，只有另外一端是用来控制和插入的，所以说，最先进来的结点肯定是最后出去的
4.链式栈（stack）
    其实就是一个头插头删或者尾插尾删的链表
三、链式栈的设计和创建

1.设计：
typedef int SElemType_t;
//数据结点
struct node
{
    SElemType_t data;
    struct node *next;
};
//链式栈的管理结构体（头结点）
struct list_stack
{
        struct node *stack;//保存首结点的地址
        int size;//栈结构体中元素的个数（结点个数）
};
struct list_stack *managerStack;
//2.初始化栈
bool init_stack()
{
    //1)申请栈管理结构体的内存空间
    managerStack=malloc(sizeof(struct list_stack));
    if(managerStack==NULL)
    {
        printf("malloc managerStack error\n");
        return false;
    }
    //2)初始化
    managerStack->size=0;
    managerStack->stack=NULL;
    return true;
}
//3.入栈（压栈）
bool push(SElemType_t inputData)
{
    //1、申请栈元素的结点的内存空间
    struct node *newNode=malloc(sizeof(struct node));
    if(newNode==NULL)
    {
        printf("malloc newNode error\n");
        return false;
    }
    //2、初始化
    newNode->data=inputData;
    newNode->next=NULL;
    //3、插入
    if(managerStack->stack==NULL)//从无到有
    {
        managerStack->stack=newNode;
    }
    else//(由少到多)（头插）
    {
        newNode->next=managerStack->stack;
        //更新首结点
        managerStack->stack=newNode;
    }
    //栈元素+1
    managerStack->size++;
    return true;
}
bool isEmpty()
{
    return managerStack->size==0;
}
//出栈--删除（头删）
bool pop(SElemType_t *outData)
{
    //1、先判断当前有没有栈元素
    if(isEmpty())
        return false;
    //2、先获取出栈的数据
    *outData=managerStack->stack->data;
    //先定义一个临时的指针存储当前删除结点的地址
    struct node*delNode=managerStack->stack;
    //更新首结点
    managerStack->stack=delNode->next;
    //释放
    free(delNode);
    //size--
    managerStack->size--;
    return true;
}
//销毁栈
void destory_stack()
{
    if(managerStack==NULL)
        return;
    //1.遍历所有的结点，每个点都删除
    struct node *p=managerStack->stack;
    struct node *pnext=NULL;
    while(p)
    {
        pnext=p->next;
        free(p);
        p=pnext;
    }
    //2.释放头结点（栈管理结构体）
    free(managerStack);
    managerStack=NULL;
}

demo.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int SElemType_t;
 
struct node{
	SElemType_t data;
	struct node *next;
};
 
struct list_stack
{
	struct node *stack;
	int size;
};
 
struct list_stack *managerStack;
 
bool init_stack()
{
	managerStack = malloc(sizeof(struct list_stack));
	if(managerStack == NULL)
	{
		printf("malloc managerStack error\n");
		return false;
	}
	
	managerStack->size = 0;
	managerStack->stack = NULL;
	
	return true;
}
 
bool push(SElemType_t inputData)
{
	struct node *newNode = malloc(sizeof(struct node));
	if(newNode==NULL)
	{
		printf("malloc newNode error\n");
		return false;
	}
	
	newNode->data = inputData;
	newNode->next = NULL;
	
	if(managerStack->stack == NULL)
	{
		managerStack->stack = newNode;
	}
	else
	{
		newNode->next = managerStack->stack;
		managerStack->stack = newNode;
	}
	
	managerStack->size++;
	
	return true;
}
 
bool isEmpty()
{
	return managerStack->size==0;
}
//出栈--删除（头删）
bool pop(SElemType_t *outData)
{
	//1、先判断当前有没有栈元素
	if(isEmpty())
		return false;
	//2、先获取出栈的数据
	*outData=managerStack->stack->data;
	//先定义一个临时的指针存储当前删除结点的地址
	struct node*delNode=managerStack->stack;
	//更新首结点
	managerStack->stack=delNode->next;
	//释放
	free(delNode);
	//size--
	managerStack->size--;
	return true;
}
//销毁栈
void destory_stack()
{
	if(managerStack==NULL)
		return;
	//1.遍历所有的结点，每个点都删除
	struct node *p=managerStack->stack;
	struct node *pnext=NULL;
	while(