数据结构---链表、堆栈、队列详解
一、两种存储方式
1、顺序存储
2、链式存储
二、顺序表
顾名思义，顺序表就是一段连续的存储空间，知道首地址，可以访问表中的任意元素；比如数组；
像这样的一段存储空间。
typedef struct
{
datatype data[MAXSIZE];
int len;
}sqlistnode, *sqlistlink;
sqlistnode 结构体变量名； sqlistlink 结构体指针变量名；
我们在封装表的时候这样定义一个结构体，里面存放顺序表的每一个元素及表长（元素的个数，不是元素下标）；
1、创建表
我们用malloc函数：sqlistlink*sq= (sqlistlink)malloc(sizeof(sqlistnode))
这样为结构体开辟一段空间，指针sq指向这段空间的首地址；
2、插入元素
顺序可以在表的任何地方进行插入和删除；插入时要进行元素的移位，思想是先判断顺序表是否已满，再确定待插入的位置，将带插入位置的元素逐个向后移动，将要插入的元素插入，同时表长自加:
sq->data[j+1]= sq->data[j];
sq->data[i-1] =x;
sq->len++;
3、元素的删除
删除时同样要进行元素的移位，思想是先判断顺序表是否为空，在确定待删除掉的元素位置，然后进行想前移位，在将表长减一；
sq->data[j-1]=sq->data[j];
sq->len--;
具体代码查看程序；
三、链表
链表在顺序表的基础上，增加了指向下一节点的地址，使得每个节点具有数据域和指针域；
一条链表有一个head指向的头结点（数据域为-1是自己设置的，个人有人的想法），有一个指针域为NULL的未节点；其中空链表头结点和未节点在一起；
typedef struct clist
{
datatype data;
struct clist *next;
}clistnode, *clistlink;
clistnode 结构体变量名； clistlink结构体指针变量名；
创建一个链表，具有指针域，数据域，在做操的过程中，头结点始终不变。
1、创建链表
clistlink creat_clist_node(datatype x)//创建一个节点，数据域为x,指针域为NULL
{
clistlink q = (clistlink)malloc(sizeof(clistnode));
assert(q); //判断声请的空间是否没空
q->data = x;
q->next = NULL;
return q;
}
clistlink creat_clist(void)//创建空链表
{
clistlink head = creat_clist_node(-1);//将头结点的数据域赋-1，以便后面做区别
return head;
}
2、插入节点
和顺序表一样，可以在任何地方插入，但头结点不动；注意：链表没有满这一说，只有你内存足够大；
先定义两个指针，clistlink p = NULL, q =NULL;
让其中一个指向表头：p = head;
一个指向待插入节点q = creat_clist_node(x)；
确定要插入的位置，然后将p指针指向要插入位置的前一个节点；
注意；指针不能在链表上后退；可以p = p->next这样移动；现在p指向待插入位置
的前一个节点，现在让带插入节点指向后面的节点(数据域data3的这个节点)：q->next = p->next;
带插入前一个节点指向带插入节点；p->next = q; 这样一个节点就插入到这条链表中去，
说的有点罗素，其实明白了很简单；
3、删除节点
删除链表思想就是：将待删除前一个节点指向待删除后一个节点即可；记着要释放被删除的空间，用malloc函数申请的空间必须要程序员手动释放(free)，不然造成内存耗光；
四、栈
我们经常接触到的都是满递增的栈，满：就是栈顶元素是满的，相对，空就是站定元素是空的。 如下图：栈是以一种先进后出的算法，插入和删除都在栈顶进行，
top是空时，进栈时先装入元素，再top自加，而top是满时，先装入，再自加，
也就是当空栈时，top始终指向栈顶前面一个元素，满栈时，top指向栈顶，
顺序栈也是顺序表的一种，具有顺序表同样的存储方法，由数组定义。
typedef struct clist
{
datatype data;
struct clist *next;
}clistnode, *clistlink;
进栈代码：
出栈代码；
*ret = st->data[st->top];
st->top--; //注意：进栈和出栈的代码很对称；
五、链式栈
链式栈不同链表的是插入和删除都在表头进行，数据域，指针域，表头等信息。 在这里，栈有带头节点，不带头节点，相对来说，带头结点的栈要好操作；
1、有头节点
注意：栈顶与头节点不是一个
typedef struct chainstackaa
{
datatype data;
struct chainstack *next;
}cstacknode, *cstacklink;
入栈
先定义两个指针q，一个指向我们新定义的节点，数据域为x，指针域为空；
cstacklink q = (cstacklink)malloc(sizeof(cstacknode));
q->data = x;
让带插入节点指向栈顶节点，q->next=top->next；然后将带插入节点的地址付给top->next；top->next=q；这样新插入的节点就是栈顶；
出栈
定义一个指针p指向栈顶：
q=p=top->next;
p=p->next; p现在指向data2这个地方；
Top->next=p;
就是让头节点指向栈顶下一个节点，已删除栈顶节点，记着要释放空间
free（q）；q=NULL;
六、队列
是限制在两端进行插入操作和删除操作的线性表。插入在队尾，删除在对头；特点：先进先出
1、顺序队列
基本定义：他是顺序表的一种，具有顺序表同样的存储结构，有数组定义，配合用数组下标表示的对头指针和队尾指针完成各种操作。对于顺序队列有两个规则；
规则1：front指向队头元素的前一个位置；rear指向队尾元素所在的位
这样，在入队的时候，先给队尾指针加1，在将带插入元素插入到队尾指针所指向的地址
在出对时，先将对头指针向下移动一位，在取出其中的值保存起来
规则2：front指向队头元素的位置；rear指向队尾元素的下一个位置
这样入队的时候，向插入元素，再将rear向下移动一个位置
在出对时，先将头指针向下移动一位，在取出其中的值保存起来；
注意；1、在队列操作过程中，为了提高效率，已调整指针代替队列元素的移动，并将数组作为循环队列的操作空间，2、为区别队和满队，满队元素的个数比数组元素个数少一个；
typedef struct
{
datatype data[MAXSIZE];
int front, rear;
}squeuenode, *squeuelink;
⑴、空队列的建立
void creat_squeue(squeuelink *sq)
{
*sq = (squeuelink)malloc(sizeof(squeuenode));
(*sq)->front = (*sq)->rear = 0;
} //接着将对头着队尾指向同一个0地址；
⑵、入队，在队尾进行 先要判断队列是否有满队
void in_squeue(squeuelink sq, datatype x)
{
if(isfull_squeue(sq))
{
printf("squeue is full!\n");
return;
}
sq->rear = (sq->rear + 1) % MAXSIZE;
sq->data[sq->rear] = x;
}
⑶、出对，在对头进行 先要判断队列是否有元素
int out_squeue(squeuelink sq, datatype *ret)
{
if(isempty_squeue(sq))
{
printf("squeue is empty!\n");
return FALSE;
}
sq->front = (sq->front + 1) % MAXSIZE;
*ret = sq->data[sq->front];
return TRUE;
}
2、链式队
是链表的一种，具备链式表的所有特性，但是同样插入操作在队尾进行，删除操作在对头进行，由对头指针和队尾指针控制队列的操作
1、带头节点
2、不带头节点