一、栈

1.定义

栈是一种满足后进先出的数据结构；例：死胡同

允许进行插入、删除操作的一端称为栈顶 top
表的另一端称为栈底
当栈中没有数据元素时，称为空栈
栈的插入操作通常称为进栈或入栈
栈的删除操作通常称为退栈或出栈

void InitStack(SqStack *&s);
void DestroyStack(SqStack *&s);
bool StackEmpty(SqStack *s);
bool Push(SqStack *&s,ElemType e);
bool Pop(SqStack *&s,ElemType &e);
bool GetTop(SqStack *s,ElemType &e);

2.类型

2.1顺序栈

//顺序栈基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int top;//栈指针
} SqStack;//顺序栈类型
void InitStack(SqStack *&s)
{
    s=(SqStack *)malloc(sizeof(SqStack));
    s->top=-1;//top为下标，始终指向栈顶元素；在以数组构成的栈中，初始值为-1,自加一次则指向下标为0的元素
}
void DestroyStack(SqStack *&s)
{
    free(s);
}
bool StackEmpty(SqStack *s)
{
    return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e)
{
    if (s->top==MaxSize-1)//栈满的情况，即栈上溢出
        return false;
    s->top++;
    s->data[s->top]=e;
    return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
    if (s->top==-1)//栈为空的情况，即栈下溢出
        return false;
    e=s->data[s->top];
    s->top--;
    return true;
}
bool GetTop(SqStack *s,ElemType &e)
{
    if (s->top==-1)//栈为空的情况，即栈下溢出
        return false;
    e=s->data[s->top];
    return true;
}

2.2 链栈

//链栈基本运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct linknode
{
    ElemType data;              //数据域
    struct linknode *next;      //指针域
} LinkStNode;                   //链栈类型
void InitStack(LinkStNode *&s)
{
    s=(LinkStNode *)malloc(sizeof(LinkStNode));
    s->next=NULL;
}
void DestroyStack(LinkStNode *&s)
{
    LinkStNode *p=s->next;
    while (p!=NULL)
    {
        free(s);
        s=p;
        p=p->next;
    }
    free(s);    //s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
    return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{   LinkStNode *p;
    p=(LinkStNode *)malloc(sizeof(LinkStNode));
    p->data=e;              //新建元素e对应的结点p
    p->next=s->next;        //插入p结点作为开始结点
    s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{   LinkStNode *p;
    if (s->next==NULL)      //栈空的情况
        return false;
    p=s->next;              //p指向开始结点
    e=p->data;
    s->next=p->next;        //删除p结点
    free(p);                //释放p结点
    return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{   if (s->next==NULL)      //栈空的情况
        return false;
    e=s->next->data;
    return true;
}

二、队列

1.定义

2.类型

2.1 顺序队列（非环形）

//顺序队列（非环形队列）基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;                     //队头和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{   q=(SqQueue *)malloc (sizeof(SqQueue));
    q->front=q->rear=-1;
}
void DestroyQueue(SqQueue *&q)          //销毁队列
{
    free(q);
}
bool QueueEmpty(SqQueue *q)             //判断队列是否为空
{
    return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)    //进队
{   if (q->rear==MaxSize-1)             //队满上溢出
        return false;                   //返回假
    q->rear++;                          //队尾增1
    q->data[q->rear]=e;                 //rear位置插入元素e
    return true;                        //返回真
}
bool deQueue(SqQueue *&q,ElemType &e)   //出队
{   if (q->front==q->rear)              //队空下溢出
        return false;
    q->front++;
    e=q->data[q->front];
    return true;
}

2.2 顺序队列（环形）

//顺序队列（环形队列）基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;     //队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{   q=(SqQueue *)malloc (sizeof(SqQueue));
    q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
    free(q);
}
bool QueueEmpty(SqQueue *q)
{
    return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{   if ((q->rear+1)%MaxSize==q->front)  //队满上溢出
        return false;
    q->rear=(q->rear+1)%MaxSize;
    q->data[q->rear]=e;
    return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{   if (q->front==q->rear)      //队空下溢出
        return false;
    q->front=(q->front+1)%MaxSize;
    e=q->data[q->front];
    return true;
}

2.3 链队

//链队运算算法
#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct DataNode
{
    ElemType data;
    struct DataNode *next;
} DataNode;             //链队数据结点类型
typedef struct
{
    DataNode *front;
    DataNode *rear;
} LinkQuNode;           //链队类型
void InitQueue(LinkQuNode *&q)
{
    q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
    q->front=q->rear=NULL;
}
void DestroyQueue(LinkQuNode *&q)
{
    DataNode *p=q->front,*r;//p指向队头数据结点
    if (p!=NULL)            //释放数据结点占用空间
    {   r=p->next;
        while (r!=NULL)
        {   free(p);
            p=r;r=p->next;
        }
    }
    free(p);
    free(q);                //释放链队结点占用空间
}
bool QueueEmpty(LinkQuNode *q)
{
    return(q->rear==NULL);
}
void enQueue(LinkQuNode *&q,ElemType e)
{   DataNode *p;
    p=(DataNode *)malloc(sizeof(DataNode));
    p->data=e;
    p->next=NULL;
    if (q->rear==NULL)      //若链队为空,则新结点是队首结点又是队尾结点
        q->front=q->rear=p;
    else
    {   q->rear->next=p;    //将p结点链到队尾,并将rear指向它
        q->rear=p;
    }
}
bool deQueue(LinkQuNode *&q,ElemType &e)
{   DataNode *t;
    if (q->rear==NULL)      //队列为空
        return false;
    t=q->front;             //t指向第一个数据结点
    if (q->front==q->rear)  //队列中只有一个结点时
        q->front=q->rear=NULL;
    else                    //队列中有多个结点时
        q->front=q->front->next;
    e=t->data;
    free(t);
    return true;
}

称为

栈和队列

一、栈

1.定义

2.类型

2.1顺序栈

2.2 链栈

二、队列

1.定义

2.类型

2.1 顺序队列（非环形）

2.2 顺序队列（环形）

2.3 链队