栈和队列
常见提问方式的问题：
1、设入栈顺序为A,B,C,D,E.则出栈序列不可能为（B）
A、EDCBA
B、ADEBC
C、ABCDE
D、ABDCE
这种题目都有一种规律:先出来的序号后面一定不能有比他本身小的从小到大排列的序列。
比如
12345
45321 正确
43512（5后面有比它本身小且从小到大排序所以是错的）
2、若进栈序列为1,2,3.4假定进栈和出栈可以穿插进行，则可能的出栈序列是(D)
A、2,4,1,3
B、3,1,4,2
C、3,4,1,2
D、1,2,3,4
原则：如果想要后面的先出栈，那么按照1234的入栈顺序，前面的必须已经入栈，比如要让3第一个出栈，那么入栈顺序为：
1入栈，2入栈，3入栈，之后3出栈，这样3就是第一个出栈的，如果想让4接着出栈，那么就4入栈，然后再出栈，然后2出栈，1出栈
最后出栈顺序为：
3421
以此规则分别分析ABCD
A 表示：
1入栈，2入栈，2出栈，3入栈，4入栈，4出栈，后面3必须先出栈，1才能出栈，所以A错
B表示：
1入栈，2入栈，3入栈，3 出栈，后面2必须先出栈，1才能出栈，所以B错
C表示：
1入栈，2入栈，3入栈，3 出栈， 4入栈，4出栈， 后面2必须先出栈，1才能出栈，所以C错
D表示：
1入栈，1出栈， 2入栈，2 出栈， 3入栈，3 出栈， 4入栈，4出栈，正确
3、队列{a,b,c,d,e}依次入队，允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的 出队 序 列 是（C）
A、b， a， c， d， e
B、d， b， a， c， e
C、d， b， c， a， e
D、e， c， b， a， d
根据题目的意思，假设队列的两端依次是P和Q：（Q端删除）
A选项：a从P端先进入队列，然后b从Q端再进入队列，这个时候再执行出队操作，依次为b,a,c,d,e
B选项：a从P端先入队列，b从Q端进入队列，然后c再从P端进入队列，d再从Q端进入队列，执行出队操作，依次为d.b,a,c,e
D选型：依次操作为a从P入队，b，c，e依次从Q端入队列，d再从P端入队列，再依次出队，依次为e,c,b,a,d
在单链表中，指针P指向值为x的节点，能实现“删除x的后继”的语句是：p->next = p->next->next(要在链表删除一个元素，表示为它后面的后继元素不是它了即可，即p->next本来是x的后继，但是（p->next = p->next->next）这个语句表示x的后继是原来后面的第2个了)
4、设栈的顺序存储空间为 S(0:49) ，栈底指针 bottom=49 ，栈顶指针 top=30 （指向栈顶元素）。则栈中的元素个数为（ C）。
A、30
B、29
C、20
D、19
数据结构（数据+结构）：是指所有数据元素以及数据元素之间的关系。这是在说数据结构是除了存放数据还有存放这些被存放的数据之间的关系是吧（这些关系可以是：逻辑结构和存储结构，
逻辑结构又分：集合，线性结构，树形结构，图形结构。
存储结构：顺序存储结构，链式存储结构，索引存储结构，哈希（或散列）存储结构
单链表：
单链表插入：先指定当前节点的后继，再指定前面节点的后继（因为单链表只有指定后继就行了）
单链表的插入顺序：s-next = p->next；p->next = s;
这里删除指在单链表中删除节点的p的后继节点。
单链表的删除顺序:q = p->next;p->next = q->next;free(q);
双向链表：
双向链表的插入顺序：先搞定插入节点的前驱和后继，在搞定其后结点的前驱，最后搞定其前结点的后继。
循环队列：（front:队头，rear:队尾，Maxsize:队列长度）
判断循环队列元素个数： (R-F+M)％M
判断循环队列空：R = F
判断循环队列满：R+1%M = F
往循环队列插入元素：F= (F+1)%M
往循环队列删除元素：R = (R+1)%M
单链表：插入操作：s->next = p->next
p->next = s;
删除操作：p->next = p->next->next
假设在双链表中p所指结点之后插入一个节点s
双链表：插入操作：s->next = p->next
s-prior = p->next->prior
p-next-prior = s
p->next = s;
删除操作：p-next= q->next
q->next->prior = p;
1、对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为(D)
A、p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B、p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C、s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D、s->left=p;s->right=p->right;p->right->left=s;p->right=s;
2、设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D）。
A、p->right=s； s->left=p； p->right->left=s； s->right=p->right；
B、s->left=p；s->right=p->right；p->right=s； p->right->left=s；
C、p->right=s； p->right->left=s； s->left=p； s->right=p->right；
D、s->left=p；s->right=p->right；p->right->left=s； p->right=s；
解释：B选项先把p->right = s，然后再p->right->left，因为前面已经指定了p->right是s了，所以p->right->left其实是s->left也就是p自身节点，s->left = s;我觉得本身就不可以这样赋值的。牛客网的同志的解释说的是B选项这样，其实只是除了指定了s的前驱和后继，还指定了p的后继，但是没有指定s后那个节点的前驱，所以导致断裂了。
关于在单链表或者其它什么存储结构，删除或增加一个元素的时间复杂度。
4、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）；
A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;
C. s->next=p->next; p=s; C. p->next=s; s->next=p;
5、在一个单链表中，若删除p所指结点的后续结点，则执行（A）
A. p->next= p->next->next，free(p)； B. p= p->next; p->next= p->next->next，free(p)；
C. p->next= p->next，free(p)； D. p= p->next->next，free(p)；
解释：
3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为A。
(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；
(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；
(C) q=p->next；p->next=q->next；free(q)；
(D)q=p->next；p->data=q->data；free(q)；
解释：（跟上题比较一下，上题是删除p所指结点的后继节结点，这题是删除当前结点）首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。
单链表：插入、删除操作的时间复杂度分别为：
双链表：插入、删除操作的时间复杂度分别为：
6、在长度为n（n≥1）的单链表中删除尾结点的时间复杂度为（）。
A. O(1) B. O(log2n) C.O(n) D.O(n2)
7、对于长度为n（n≥1）的双链表L，在p所指结点之前插入一个新结点的算法的时间复杂度为（）。
A.O(1) B.O(n) C.O(n2) D.O(nlog2n)
8、在长度为n（n≥1）的循环双单链表L中，删除尾结点的时间复杂度为（ ）。
A.O(1) B.O(n) C.O(n2) D.O(nlog2n)
9、在长度为n（n≥1）的双链表中插入一个结点（非尾结点）要修改（ ）个指针域。
A. 1 B. 2 C. 3 D. 4
10、在长度为n（n≥1）的双链表中删除一个结点（非尾结点）要修改（）个指针域。
A. 1 B. 2 C. 3 D. 4
11、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为(O(n))，在表尾插入元素的时间复杂度为(O(1))
12、在一个长度为n的单链表L中，删除链表中*p的前驱节点的时间复杂度为（O（n）），删除*p结点的时间复杂度为（O（1））
双向链表的删除顺序：要删除双链表的一个结点，无非就是把要删除的结点去掉，然后重新指定前一个结点的前驱节点和后继结点，还有后面那个节点的前驱节点和后继结点。（就是修改p结点前驱结点的next指针和p结点后继结点的prior指针。）原来要删除结点的前驱节点变成原来删除结点的后继节点的前驱节点（p->next->prior = p->piror）,还有就是把原来要删除结点的后继节点变成原来删除结点的前驱节点的后继节点（p->piror-next = p->next），
注意：这删除结点的顺序是有要求的，哪个先，哪个后。
栈的应用
前缀，中缀和后缀表达式
中缀表达式转后缀表达式：
规则：从左到右遍历中缀表达式的每个数字和运算符，是数字就直接输出，如果是运算符的话，判断当前要进栈的运算符跟栈顶的运算符比较优先级，如果栈顶运算符优先级低于当前要进栈的运算符，就不输出，直接进栈，如果栈顶运算符优先级高于当前要进栈的运算符，就输出栈顶运算符，一直遍历到表达式最后。
补充说一下规则：像遇到括号了，要先左括号进栈了，然后一直遍历，再遇到右括号，就需要把出栈，直到吧左括号出栈即可（左括号输出后，栈里面还有符号就放着了，还有表达式是不用吧括号写上去的）。都是要先判断一下优先级关系，然后看要不要输出栈顶元素
中缀表达式转前缀表达式：
规则：从右向左遍历中缀表达式的每个数字和运算符，是数字就直接输出，如果是运算符的话，判断当前要进栈的运算符跟栈顶的运算符比较优先级，如果栈顶运算符优先级