13、栈与队列u0026考研真题实战

本章需要掌握：

1、顺序栈（初始化、栈空？入栈、出栈、栈顶元素）
2、顺序队列（初始化、队列空？入队、出队）
3、链队列
4、2019真题循环队列

1、顺序栈（初始化、栈空？入栈、出栈、栈顶元素）

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];//数组
    int top;//始终指向栈顶的一个变量
}SqStack;
//初始化栈
void InitStack(SqStack &S)
{
    S.top=-1;//初始化栈，就是S.top=-1,让栈为空
}
bool StackEmpty(SqStack S)
{
    if(-1==S.top)
    {
        return true;
    }else{
        return false;
    }
}
//入栈
bool Push(SqStack &S,ElemType x)
{
    //判断栈是否满了
    if(S.top==MaxSize-1)
    {
        return false;
    }
    S.data[++S.top]=x;//等价于S.top=S.top+1;   S.data[S.top]=x;
    return true;
}
//获取栈顶元素
bool GetTop(SqStack S,ElemType &m)
{
    if(StackEmpty(S))
    {
        return false;
    }
    m=S.data[S.top];//拿栈顶元素
    return true;
}
//弹栈
bool Pop(SqStack &S,ElemType &m)
{
    if(StackEmpty(S))
    {
        return false;
    }
    m=S.data[S.top--];//出栈 后减减等价于 先m=S.data[S.top];S.top=S.top-1;
    return true;
}
int main() {
    SqStack S;
    InitStack(S);
    bool flag;
    flag=StackEmpty(S);
    if(flag)
    {
        printf("stack is empty\n");
    }
    Push(S,3);//入栈元素3
    Push(S,4);//入栈元素4
    Push(S,5);
    ElemType m;
    flag=GetTop(S,m);//获取栈顶元素
    if(flag)
    {
        printf("get top %d\n",m);
    }
    flag=Pop(S,m);//弹出栈顶元素
    if(flag)
    {
        printf("pop element %d\n",m);
    }
    return 0;
}

2、顺序队列（初始化、队列空？入队、出队）

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 5
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];//数组,存储MaxSize-1个元素
    int front,rear;//队列头 队列尾
}SqQueue;

void InitQueue(SqQueue &Q)
{
    Q.front=Q.rear=0;//初始化循环队列，就是让头和尾都指向零号
}
//判断循环队列是否为空
bool isEmpty(SqQueue Q)
{
    return Q.rear==Q.front;
}
//入队
bool EnQueue(SqQueue &Q,ElemType x)
{
    if((Q.rear+1)%MaxSize==Q.front)//判断循环队列是否满了，满了就不能入队了
    {
        return false;
    }
    Q.data[Q.rear]=x;//放入元素
    Q.rear=(Q.rear+1)%MaxSize;//rear要加1，如果大于数组最大下标，回到开头
    return true;
}
//出队
bool DeQueue(SqQueue &Q,ElemType &x)
{
    if(Q.rear==Q.front)//队列为空，无法出队
    {
        return false;
    }
    x=Q.data[Q.front];//出队
    Q.front=(Q.front+1)%MaxSize;
    return true;
}
//循环队列的代码实战
int main() {
    SqQueue Q;
    InitQueue(Q);
    bool ret;
    ret=isEmpty(Q);
    if(ret)
    {
        printf("SqQueue is Empty\n");
    }else{
        printf("SqQueue is not Empty\n");
    }
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    ret=EnQueue(Q,6);
    ret=EnQueue(Q,7);
    if(ret)
    {
        printf("EnQueue success\n");
    }else{
        printf("EnQueue failed\n");
    }
    ElemType element;//存储出队元素
    ret=DeQueue(Q,element);
    if(ret)
    {
        printf("DeQueue success\n");
    }else{
        printf("DeQueue failed\n");
    }
    ret=EnQueue(Q,8);
    if(ret)
    {
        printf("EnQueue success\n");
    }else{
        printf("EnQueue failed\n");
    }
    return 0;
}

3、链队列

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front,*rear;//链表头 链表尾,也可以称为队头，队尾
}LinkQueue;//先进先出

//队列的初始化，使用的是带头结点的链表来实现的
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}
//入队
void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *pnew=(LinkNode*)malloc(sizeof(LinkNode));
    pnew->data=x;
    pnew->next=NULL;//要让next为NULL
    Q.rear->next=pnew;//尾指针的next指向pnew，因为从尾部入队
    Q.rear=pnew;//rear要指向新的尾部
}
//出队
bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.rear==Q.front)//队列为空
    {
        return false;
    }
    LinkNode* q=Q.front->next;//拿到第一个结点，存入q
    x=q->data;//获取要出队的元素值
    Q.front->next=q->next;//让一个结点断链
    if(Q.rear==q)//链表只剩余一个结点时，被删除后，要改变rear
    {
        Q.rear=Q.front;
    }
    free(q);
    return true;
}
//通过链表来实现队列
int main() {
    LinkQueue Q;
    InitQueue(Q);//初始化队列
    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);
    ElemType element;
    bool ret;
    ret=DeQueue(Q,element);
    if(ret)
    {
        printf("DeQueue success element= %d\n",element);
    }else{
        printf("DeQueue failed\n");
    }
    DeQueue(Q,element);
    ret=DeQueue(Q,element);
    if(ret)
    {
        printf("DeQueue success element= %d\n",element);
    }else{
        printf("DeQueue failed\n");
    }
    return 0;
}

4、考研真题2019——循环队列

42.（10分）请设计一个队列，要求满足：①初始时队列为空；②入队时：允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不減；④入队操作和出队操作的时间复杂度始终保持为 O（1）。请回答下列问题：

（1）该队列是应选择链式存储结构，还是应选择顺序存储结构？

（2）画出队列的初始状态，并给出判断队空和队满的条件。

（3）画出第一个元素入队后的队列状态。

（4）给出入队操作和出队操作的基本过程。

4.1 答案

1、链式存储结构

2、

队空的判定条件∶front == rear。
队满的判定条件∶ front == rear->next。
3、插入第一个元素后的状态如下图所示。

4、操作的基本过程如下∶

（有个小问题就是入队的时候rear后插入一个新空闲节点，空闲节点指向front？可能代码有自纠错一类的）

4.2 王道代码

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;//指向下一个结点
}LNode, * LinkList;


void EnQueue(LinkList front, LinkList& rear, ElemType val)
{
    LinkList pnew;
    if (rear->next == front)//判断队列是不是满了
    {
        //队列满，申请一个结点的空间，放入队列
        pnew= (LinkList)malloc(sizeof(LNode));
        rear->data = val;//把入队元素放入rear指向结点
        rear->next = pnew;//放了一个结点，其相当于做了分割
        pnew->next = front;
        rear = pnew;
    }
    else {//如果队列不满，直接放值，让rear后移一个结点
        rear->data = val;
        rear = rear->next;
    }
}

void DeQueue(LinkList& front, LinkList rear)
{
    if (front == rear)
    {
        printf("queue is empty\n");
    }
    else {
        printf("dequeue %d\n", front->data);
        front = front->next;
    }
}
//循环队列操作的总流程
void CircleQueue(LinkList& front, LinkList& rear)
{
    //队列头和队列尾都指向一个结点，这时队列既是空的，也是满的
    front = (LinkList)malloc(sizeof(LNode));
    rear = front;
    rear->next = front;//构造循环队列
    //入队
    EnQueue(front, rear, 3);
    EnQueue(front, rear, 4);
    //出队
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
}


int main()
{
    LinkList front, rear;
    CircleQueue(front, rear);
    return 0;
}