数据结构栈（顺序栈、链栈、插入push、删除pop）、队（循环队，链队、入队push，出队pop）知识点梳理

数据结构栈知识点梳理

一栈的定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表

不含任何元素的栈称为空栈
允许插入和删除的一端成为栈顶（top），另一端称为栈底（bottom）
具有LIFO（Last In First Out）结构
栈元素具有线性关系，即前驱和后继，是特殊的线性表

二栈的插入、删除

栈的插入操作—进栈（push）

栈的删除操作—出栈（pop）

三栈的抽象数据类型

ADT 栈(stack)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
    InitStack(&S):初始化操作，建立一个空栈S
    DestroyStack(*S):若栈存在，则销毁它
    ClearStack(*S):将栈清空
    StackEmpty(S):若栈为空，返回true，否则返回false
    GetTop(S,*e):若栈存在且非空，用e返回S的栈顶元素
    Push(*S,e):若栈S存在，插入新元素e到栈S中并称为栈顶元素
    Pop(*S,*e):删除栈S中栈顶元素，并用e返回其值
    StackLength(S):返回栈S的元素个数
endADT

四栈的顺序存储结构

栈只能在一头插入和删除，下标为0的一端作栈底比较好。定义一个top变量来指示栈顶元素在数组中的位置。

存储栈的长度StackSize，栈顶位置top必须小于StackSize。

当栈有一个元素时，top=0，所以空栈的判定条件为top=-1

出栈和入栈的时间复杂度都是O(1)

栈的结构定义

typedef int SElemType;/*SElemType 类型根据实际情况而定，这里假设为int*/
typedef struct
{
    SElemType data[MAXSIZE];
    int top;/*栈顶指针*/
}SqStack;

进栈操作

进栈push操作

Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE - 1)/*栈满*/
    {
        return ERROR;
    }
    S->top++;/*栈顶指针+1*/
    S->data[S->top] = e;/*将新插入元素赋值给栈顶空间*/
    return OK;
}

出栈操作

Status Pop(SqStack *S,SElemType *e)
{
    if(S->top == -1)
        return ERROR;
    *e = S->data[S->top]; /*将要删除的栈顶元素赋值给e*/
    S->top--;
    return OK;
}

五两栈共享空间

栈的顺序存储

优点：插入和删除操作不需要元素

缺点：需要提前确认存储空间，或者用编程手段扩容，空间利用率不高

解决方法：两栈共享空间，为了增加空间利用率，可以用一个数组来存储两个栈

如图：让一个栈的栈底为数组的始端（下标为0处），另一个栈为栈的末端（下标n-1处），两个栈的元素增加，向中间延伸

栈1为空，top1 == -1；栈2为空，top2 == n；栈满 top1+1 == top2

/*两栈共享空间结构*/
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;
    int top2;
}SqDoubleStack;

插入操作

增加一个StackNumber判断插入栈1还是栈2

/*插入元素e为新的栈顶元素*/
Status	Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
    if(S->top1+1 == S->top2)
        return ERROR;
    if(stackNumber == 1)
        S->data[++S->top1]=e;
    else if(stackNumber == 2)
        S->data[--S->top2]=e;
    return OK;
}

插入操作

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR*/
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{
    if(stackNumber == 1)
    {
        if(S->top1 == -1)
            return ERROR;
        *e = S->data[S->top1--];
    }
    else if(stackNumber == 2)
    {
        if(S->top2 == MAXSIZE)
            return ERROR;
        *e = S->data[S->top2++];
    }        
    return OK;
}

六栈的链式存储结构

链栈不需要头结点

基本不存在栈满的情况，除非内存没有空间

链栈空top == NULL

链栈结构代码

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

进栈操作

/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S,SElemType e)
{
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=S->top;	
    S->top=s;
    S->count++;
    return OK;
}

出栈操作

Status Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    if(StackEmpty(*s))
        return ERROR;
    *e=S->top->data;
    p=S->top;
    S->top = S->top->next;
    free(p);
    S->count--;
    return OK;
}

七总结

栈在使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈。反之，大小在可控的范围内，用顺序栈。

栈更多的应用在递归。

数据结构队知识点梳理

一定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出（First In First Out）的线性表

允许插入的一端称队尾，允许删除的一端称队头

二队列的抽象数据结构

ADT 队列(Queue)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继
Operation
    InitQueue(*Q):初始化操作，建立一个空队列Q
	DestroyQueue(*Q):若队列Q存在，则销毁它
	ClearQueue(*Q):将队列清空
	QueueEmpty(Q):若队列为空，返回true，否则返回false
	GetHead(Q,*e):若队列Q存在且非空，用e返回队列Q的队头元素
	EnQueue(*Q,e):若队列存在，插入新元素e到队列Q中并成为队尾元素
	DeQueue(*Q,*e):删除队列Q中的队头元素，并用e返回其值
	QueueLength(Q):返回队列Q中的元素个数
endADT

三循环队列

顺序存储结构存在不足容易发生数组越界的错误，假溢出现象。
两个指针

为了避免队尾和队头重合使处理十分麻烦，所以引入两个指针。front指针指向队头元素，rear指针指向队尾元素；front==rear时，指空队列
循环队列定义

头尾相接的顺序存储结构称为循环队列。
出现的问题

当front==rear的时候可能是队列为空，或可能是队列为满

解决办法：

设置一个标志变量flag，当front == rear，且flag = 0时队列为空，当front == rear，且flag = 1时队列为满。
当队列空时，条件就是front == rear，当队列为满的时候，修改其中的条件，保留一个元素空间，意思就是当队列满的时候，数组中还有一个空闲单元。

第二种解决方式不允许出现的情况

队满情况

四循环队列一些列操作

顺序存储结构代码

队列满的条件：
(rear+1)%QueueSize == front

通用的计算队列长度公式：
（rear-front+QueueSize）%QueueSize

typedef int QElemType;
/*循环队列的顺序存储结构*/
typedef struct
{
    QElemType data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

初始化循环队列

/*初始化一个空队列*/
Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

循环队列求长度

/*返回Q的元素个数，也就是当前队列的长度*/
int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}

循环队列的入队

/*若队列未满，则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q,QElemType e)
{
    if((Q->rear+1)%MAXSIZE == Q->front)
        return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXSIZE;
    return OK;
}

循环队列的出队

/*若队列不空，则删除Q中队头元素，用e返回其值*/
Status DeQueue(SqQueue *Q,QElemType *e)
{
    if(Q->front == Q->rear)
        return ERROR;
    *e=Q->data[Q->front];
    Q->front = (Q->front+1)%MAXSIZE;
    return OK;
}

循环队列面临着数组溢出的问题，所以还需要不用担心队列长度的链式存储结构

五队列的链式存储结构

理解：队列的存储结构，相当于线性表的单链表，只不过它只能尾进头出，简称链队列

队头指针指向链队的头结点，队尾指针指向终端结点。

空队列，front和rear都指向头结点

链队的存储结构

typedef int QElemType
typedef struct QNode /*结点结构*/
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct /*队列的链表结构*/
{
    QueuePtr front rear;
}LinkQueue;

入队操作

/*插入元素e为Q的新的队尾元素*/
Status EnQueue(LinkQueue *Q,QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(！s)
        exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
    return OK;   
}

出队操作

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
Status DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;
    if(Q->front == Q->rear)
        return ERROR;
    p = Q->front->next;
    if(Q->rear == p)/*若队头是队尾*/
        Q->rear = Q->front;
    free(p);
    return OK;   
}