计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。
OPNDType EvalueExpression()
{ //OPTR 和OPND分别为运算符栈和操作数栈
InitStack(OPTR);Push(OPTR,’#’);
InitStack(OPND);c=getchar();
While(c!=’#’|| GetTop(OPTR)!=’#’)
{
If(!IN(c,OP) ) //如果是操作数，直接入操作数栈
{ push(OPND,c);
c=getchar();
}
Else //如果是运算符，则与当前的栈顶比较
{
Switch(Precede(GetTop(OPTR),c))
{
Case ‘<’: push(OPTR,c);//比当前栈顶高，这入栈
c=getchar();
break;
Case ’= ’:Pop(OPTR,x); //在我们设计的优先级表中，
c=getchar(); //只有’(’和’)’存在相等的情况，
break; //而在规约中间只存在‘(’‘)’
//所以我们直接把’(’弹出就可以了
Case ‘>’: //比当前栈顶低，则要把栈顶先运算完(先规约)
pop(OPTR,theta); //把栈顶运算符弹出
Pop(OPND,b); //取出操作数，并且是前操作数
Pop(OPND,a); //在下面(栈的先进后出)
Push(OPND,Operate(a,theta,b)); //运算的结果入栈
//(他是其他运算符的操作数)
Break;
}//Switch
}//else
}//whild
Return GetTop(OPND);//操作数栈中最后剩下的就是整个表达式的结果了。
}
中缀表达式转化成后缀表达式算法
void trans-post(char E[n] ,char B[n]) //中、后缀表达式转换//
{ //E[n]是中缀表达式、B[n]是后缀表达式存储的空间
int i=0,j=0; char x; stype S;
Clearstack(S); Push(S,‘#’);//‘#’入栈//
do {
x=E[i++] ; //扫描当前表达式分量//
if (x=‘#’) //到了中缀表达式最后了
while(!Emptystack(S)) //全部退栈,#和#是优先级最低的，
B[j++]==pop(S); //所以当前栈的所有运算都要规约
//输出栈顶运算符，并退栈直到遇见栈底的开始放进去的那个#//
else if (isdigit(x))
B[j++]=x; //操作数直接输出//
else if (x=‘)’) //遇到)那么就一定要找到(
{
while (Getstop(S)!=‘(’)
B[j++]=pop(S); //输出栈顶，并退栈//
pop(S); //退掉‘(’//
}
else //x为运算符//
{
while (precede(Getstop(S), x)) //栈顶( q1)与x比较//
B[j++]=pop(S); // q1 >=x时，输出栈顶符并退栈//
Push(S,x); // q1 < x时x进栈//
}
} while (x!=’#’);
B[j]=’#’;
} //置表达式结束符//
双端队列：
两端都可以插入和删除，但实际应用中通常是输出受限的双端对列和输入受限的双端队列
输入受限的双端队列指的是：一端可以输入输出另一端只能输出不能输入
输出受限的双端队列指的是：一端可以输入输出另一端只能输入不能输出
求从迷宫入口到出口的一条最短路径
要用到队列，因为队列可以用在广度优先中，队列中的元素表示离中心点依次越来越远。
所以第一次找到出口肯定是半径最短的。
链式栈：
a0
^
a1
top ……
An
链式队列：
front
rear
q
头
a0
an-1
^
N个结点的不同二叉树有： 等于不同的进出栈总数
有n个数顺序(依次)进栈，出栈序列有Cn种，Cn=[1/(n+1)]*(2n)!/[(n!)*(n!)]。=
尾递归和单向递归的消除不需要借用栈
单向递归和尾递归可直接用迭代实现其非递归过程
其他情形必须借助栈实现非递归过程。
证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i
i
若Pi>Pj 说明大的数先于小的数出栈，那么在Pi出栈前Pj一定在栈中
证明：1)j
2)iPk 说明Pi出栈前，Pk在栈中
3)iPj 说明Pi出栈前Pj在栈中
而Pi是最先出栈的那么在Pi为栈顶的时候，Pj和Pk一定都同时被压入栈中，那么就与1矛盾了，1要求Pj要在Pk入栈前出栈，而此时Pk Pj都在栈中所以假设不成立。
用两个栈来模拟一个队列
栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且 s1也为空，才算是队列空。
