顺序栈

类型描述

1
2
3
4
5
6
7
typedef int SElemType; 
typedef struct
{
    SElemType * base;//基址
    SElemType * top;//栈顶指针,旨在an的下一个位置
    int stacksize;  //分配空间大小
} SqStack;

初始化

1
2
3
4
5
6
7
8
Status InitStack(SqStack &S)
{
    S.base=new SElemType[MAXSIZE];
    if(!S.base) exit(OVERFLOW);
    S.top=S.base; //初始化为空栈
    S.stacksize=MAXSIZE;
    return ok;
}

入栈

1
2
3
4
5
6
7
Status Push(SqStack &S,SElemType e)
{
    if(S.top-S.base==S.stacksize)    return ERROR;
    *S.top=e;
    *S.top++;
    return OK;
}

出栈

1
2
3
4
5
6
7
Status Pop(SqStack &S,SElemType &e)
{
    if(S.top==S.base)    return ERROR;
    e=*S.top;
    *S.top--;
    return OK;
}

取栈顶元素操作

1
2
3
4
5
Status GetTop(SqStack S,SElemType &e)
{
    if(S.top!=S.base)
    return *(S.top-1);
}

链栈

类型描述

1
2
3
4
5
typedef int SElemType;
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, * LinkStack;

注意链栈的指针指向栈顶元素，栈底元素为NULL。这个特点在写代码中很容易出错。

初始化

1
2
3
4
5
Status InitStack(LinkStack &S)
{
    S=NULL;
    return ok;
}

出栈

1
2
3
4
5
6
7
8
9
Status Pop(LinkStack &S,SElemType &e)
{
    if(S==NULL)    return ERROR;
    e=S->data;
    StackNode *p=S;
    S=S->next;
    delete p;
    return OK;
}

入栈

1
2
3
4
5
6
7
8
Status Push(LinkStack &S,SElemType e)
{
    StackNode *p=new StackNode;
    p->data=e;
    p->next=S;
    S=p;
    return OK;
}

循环队列

类型

1
2
3
4
5
6
typedef struct
{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

取队首元素

1
2
3
4
5
6
7
Status GetHead(SqQueue Q,QElemType &e)
{
    if(Q.front==Q.rear)    return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}

入队

1
2
3
4
5
6
7
Status EnQueue(SqQueue &Q,QElemType e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front )   return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}

出队

1
2
3
4
5
6
7
Status DeQueue(SqQueue &Q,QElemType &e)
{
    if(Q.front==Q.rear)    return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
    return OK;
}