2019考研计算机数据结构考点：栈和队列的链式存储结构

考研网

根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。
    　　三、栈和队列的链式存储结构
    1.栈的链式存储结构
    1.1概念
    采用链式存储结构称链栈，并由其栈顶指针惟一确定。
    设ls为栈顶指针，栈=(a1,a2,…,an)，a1为栈底元素，an为栈顶元素。
    1.2基本运算
    ①建栈。
    Void initstack(linkstack *s)
    {
    s->top=NULL;
    }
    ②判栈空。
    Int stackempty (linkstack *s)
    {
    return s->top==NULL;
    }
    3进栈。
    Void push(linkstack *s,datatype x)
    {
    stacknode *p=(stacknode *)malloc(sizeof(stacknode));
    p->data=x;
    p->next=s->top;
    s->top=p;
    }
    ④退栈。
    Datatype pop(linksatck *s)
    {
    datatype x;
    stacknode *p=s->top;
    if(stackempty(s))
    error(“stack underflow”);
    x=p->data;
    s->top=p->next;
    free(p);
    return x;
    }
    5取栈顶元素。
    Datatype stacktop(linkstack *s)
    {
    if(stackempty(s))
    error(“stack is empty”);
    return s->top->data;
    }
    2.队的链式存储结构
    2.1概念
    用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元
    素。如图所示：
   

    2.2基本运算
    ①建空队
    Void initqueue(linkqueue *q)
    {
    q->front=q->rear=NULL;
    }
    ②判队空。
    Int queueempty(linkqueue *q)
    {
    return q->front==NULL&&q->rear==NULL;
    }
    3入队。
    Void enqueue(linkqueue *q,datatype x)
    {
    queuenode *p=(queuenode *)malloc(sizeof(queuenode));
    p->data=x;
    p->next=NULL;
    if(queueempty(q))
    q-front=q->rear=p;
    else{
    q->rear->next=p;
    q->rear=p;
    }
    }
    ④出队。
    Datatype dequeue(linkqueue *q)
    {
    datatype x;
    queuenode *p;
    if(queueempty(q))
    error(“queue is underflow”);
    p=q->front;
    x=p->data;
    q->front=p->next;
    if(q->rear==p) q->rear=NULL;
    free(p);
    return x;
    }
    5取队头元素。
    Datatype queuefront(linkqueue *q)
    {
    if(queueempty(q))
    error(“queue is empty”);
    return q->front->data;
    }