栈和队列

1、栈

栈的顺序存储

typedef struct SqStack{
    ElemType data[MaxSize];
    int top;
}SqStack;

初始化栈

void InitStack(SqStack &S){
    S.top = -1;
}

判断栈空

bool IsEmpty(SqStack S){
    return(S.top == -1);
}

进栈

bool Push(SqStack &S,ElemType x){
    if(S.top == MaxSize-1)
        return false;
    S.data[++S.top] = x;
    return true;
}

出栈

bool Pop(SqStack &S,ElemType &x){
    if(S.top == -1)
        return false;
    x = S.data[S.top--];
    return true;
}

2、链栈

存储结构

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode,*LinkStack;

判断是否为空

bool StackEmpty(LinkStack Ls){
    return(Ls->next==NULL);
}

进链栈

void Push(LinkStack &Ls,ElemType x){
    LinkNode *p;
    p=(LinkNode *)malloc(sizeof(LinkNode));
    p->data = x;
    p->next = Ls->next;
    Ls->next = p;
}

出链栈

bool Pop(LinkStack &Ls,ElemType &x){
    LinkNode *p;
    if(Ls->next == NULL)
        return false;
    p = Ls->next;
    x = p->data;
    Ls->next = p->next;
    free(p);
    return true;
}

3、队列

存储结构

typedef struct SqQueue{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

4、循环队列

初始化

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=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;
    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;
}

5、链队

存储结构

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;
}

判断是否为空

bool IsEmpty(LinkQueue &Q){
    return(Q.front == Q.rear);
}

入链队

bool EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

出链队

bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == Q.rear)
        return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next=p->next;
    if(Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return true;
}