考研数据结构——栈和队列

古城微笑少年丶 2023-07-04 06:24 3阅读 0赞

> ### *怕什么前路太长，进一寸有一寸的欢喜* ###

栈：是线性表。是只能在一端进行插入和删除的线性表。

栈的基本操作：

InitStack(&S):初始化
    StackEmpty(S):判空
    Push(&S,x)插入元素入栈
    Pop(&S,&x)取出栈顶元素
    GetTop(S,&x)读取栈顶元素
    ClearStack(&S):销毁栈

顺序栈：

#define MaxSize 50
    typedef struct{
        Elemtype data[MaxSize];
        int top;
    }SqStack;
    
    初始化：
    void InitStack(&s){
        s.top = -1;
    }
    
    
    判空：
    bool StackEmpty(S){
        if(S.top==-1) teturn true;
        else return false;
    }
    
    入栈：
    bool Push(SqStack &S,Elemtype x){
        if(S.top==MaxSize-1) return false;
        S.data[++S.top] = x;
        teturn true;
    }
    
    出栈：
    bool Pop(SqStack &S,Elemtype &x){
        if(S.top==-1) return false;
        x = S.data[S.top--];
        return true;
    }

共享栈：两个栈空间相互调节，只有在整个存储空间被占满时才发生上溢。

链栈：不存在栈满上溢的情况，用单链表实现，所有操作都是在单链表表头进行，链栈没有头结点 。

队列：是线性表，是从尾进从头出的线性表。

#define MaxSize 50
    typedef struct{
        Elemtype data[MaxSize];   //队列是用数组定义的。
        int front,rear;
    }SqQueue;
    
    
    循环队列：
    
    初始化：
    void InitQueue(SqQueue &Q){
        Q.rear = Q.front = 0;
    }
    
    判断空：
    bool isEmpty(Q){
        if(Q.rear==Q.front) return true;
        else return false;
    }
    
    入队：
    bool EnQueue(SqQueue &Q,Elemtype x){
        if((Q.rear+1)%MaxSize==Q.front) return false;
        Q.data[rear] = x;
        Q.rear = (Q.rear+1)%MaxSize;
        return true;
    }
    出队：
    bool DeSqQueue(SqQueue &Q,Elemtype x){
        if(Q.rear==Q.front) return false;
        s = Q.data[rear];
        Q.rear = (Q.rear+1)%MaxSize;
        return true;
    }

链队：带有头指针和尾指针的单链表。

链式存储定义：
    typedef struct LinkNode{
        Elemtype data[];
        struct LinkNode *next;
    }LinkNode;
    
    typedef struct{
        LinkNode *front,*rear;
    }LinkQueue;
    
    
    初始化：
    void InitQueue(LinkQueue &Q){
        Q.front = ()malloc();
        Q.front->next = NULL;
    }
    判空：
    
    bool IsEmpty(LinkQueue &Q){
        if(Q.front==Q.rear) return true;
        return false;
    }
    入队：
    void InsertLinkQueue(LinkQueue &Q,Elemtype x){
        LinkNode *s;
        s = (LinkNode*)malloc(sizeof(LNode));
        s->data = x;
        Q.rear->next = s;
        Q.rear = s;
    }
    
    出队：
    bool DeQueue (LinkQueue &Q,Elemtype e){
        if(Q.front==Q.rear) return false;
        LinkNode *p;
        p = Q.fornt->next;
        e = p->data;
        Q.front->next = p->next;
        if(p==Q.rear) Q.front=Q.rear;
        free(p);
        return true;
    }

数组：一种逻辑结构，是线性表的推广。