@TOC

栈的相关概念

• 栈（stack）是一个特殊的线性表，是限定在仅在一端进行插入和删除操作的线性表，
• 又称==后进先出==（Last In First Out）的线性表，简称==LIFO==结构。
• 表尾称为栈顶（Top）；标头称为栈底（Base），
• 插入元素到栈顶（即表尾）的操作，称为入栈；从栈顶删除最后一个元素的操作，称为出栈。

顺序栈的表示及实现

栈的抽象数据类型的类型定义

ADT Stack {
    数据对象:
    D={ai,i=1,2,3,...}
    数据关系:
    R1 = {<ai-1,ai>}
    约定an端为栈顶，a1端为栈底。
    基本操作
}ADT Stack

顺序栈的表示

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。

#define MAXSIZE 100
typedef struct {
    SElenType *base;  //栈底指针
    SElenType *top;   //栈底指针
    int stacksize;    //栈可用最大容量
}SqStack;

顺序表的基本操作

顺序栈的初始化

//构造一个空栈
Status InitStack(SqStack & S) {
    S.base = new SElemType[MAXSIZE];
    //S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
    if(!S.base) return ERROR;  //存储分配失败
    S.top = S.base;    //栈顶指针等于栈底指针
    S.stacksize = MAXSIZE;
    return OK;
}

判断栈是否为空

//若栈为空，返回TRUE;否则返回FALSE
Status StackEmpty(SqStack S){
    if(S.top == S.base)
        return TRUE;
    else
        return FALSE;
}

顺序栈的入栈

/**
1.判断是否栈满，
2.元素e压入栈顶，
3.栈顶指针加1
*/
Status Push(SqStack &S,SElemType e){
    if(S.top-S.base == S.stacksize)  //栈满
        return;
    *S.top = e;
    S.top++;
}

顺序栈的出栈

/**
1.判断是否栈空，
2.取出栈顶元素e，
3.栈顶指针减1
*/
Status Pop(SqStack &S,SElemType &e){
    if(S.top == S.base)  //栈满
        return;
    --S.top;
    e=*S.top;
    return OK;
}

链栈的表示

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;
LinkStack S;

链栈的入栈

Status Push(LinkStack &S,SElemType e){
    p = new StackNode;  //生成新结点p
    p->data = e;
    p->next = S;   //将新结点插入栈顶
    S = p;           //修改栈顶指针
    return OK;
}

链栈的出栈

Status Pop(LinkStack &S,SElemType &e){
    if(S == NULL) return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}

队列的基本表示及操作

顺序队列

#define MAXSIZE 100
typedef struct {
    QElenType *base;  //初始化的动态分配空间
    int front;   //头指针
    int rear;    //尾指针
}SqQueue;

循环队列的初始化

Status InitQueue(SqQueue &Q){
    Q.base = new QElemType[MAXSIZE];   //分配数组空间
    //Q.base = (QElemType*)malloc(MAXSIZE*sizeof(QElemType));
    if(!Q.base) return ERROR;  //存储分配失败
    Q.front = Q.rear = 0;
    return OK;
}

求循环队列的长度

int QueueLength(QsQueue Q){
    return (Q.rear-Q.front + MAXSIZE)%MAXSIZE;
}

循环队列的入队

Status EnQueue(SqQueue &Q,QElemType e){
    if((Q.rear + 1)%MAXSIZE == Q.front) return ERROR;  //队满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1)%MAXSIZE;
    return OK;
}

循环队列的出队

Status DeQueue(SqQueue &Q,QElemType &e){
    if(Q.front == Q.rear) return ERROR;  //队空
    e = Q.base[Q.front];       //保存队头元素
    Q.front = (Q.front+1)%MAXSIZE;
    return OK;
}

链队列

链队列的类型定义

#define MAXSIZE 100
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode.*QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

链队列初始化

Status InitQueue（LinkQueue &Q）{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) return ERROR;
    Q.front->next = NULL;
    return OK;
}

链队列入队

Status EnQueue（LinkQueue &Q,QElemType e）{
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) return ERROR;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

链队列出队

Status DeQueue（LinkQueue &Q,QElemType &e）{
    if(Q.front = Q.rear) return ERROR;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(Q.rear == p) Q.rear = Q.front;
    delete p;
    return OK;
}