栈

定义

栈是限定仅在表尾进行插入和删除操作的线性表。又叫后进先出线性表（弹夹），简称LIFO结构。

栈顶（top）：栈中允许插入和删除的一端。
栈底（bottom）：栈的底部。
空栈：不含任何数据元素的栈。
栈的插入（子弹入弹夹）：进栈，压栈，入栈
栈的删除（子弹出弹夹）：出栈，弹栈

栈的顺序存储结构

结构定义

#define MAXSIZE 100

typedef int SElemType; 

typedef struct
{
    SElemType data[MAXSIZE];    /* 用于存储栈中元素 */
    int top;                    /* 用于栈顶指针，初始值为 -1，表示空栈 */
} SqStack;

进栈

#define ERROR 0
#define OK 1

typedef int SElemType;
typedef int Status;
typedef struct{
    SElemType data[MAXSIZE];
    int top;
} SqStack;

Status Push(SqStack *S, SElemtype e)
{
    if(S->top == MAXSIZE - 1) /* 满栈 */
        return ERROR；

    S->top++;                /* 栈顶指针上移动一位 */
    S->data[S->top]=e;       /* 把元素 e 存放到栈顶中 */

    return OK;
}

出栈

#define ERROR 0
#define OK 1

typedef int SElemType;
typedef int Status;
typedef struct{
    SElemType data[MAXSIZE];
    int top;
} SqStack;

Status Pop(SqStack *S, SElemtype e)
{
    if(S->top == -1)
        return ERROR;

    *e = S->data[S->top];           /* 取出要弹出的元素 */
    S->top--;                       /* 栈顶指针下移动一位 */

    return OK;
}

两者没有涉及到任何循环语句，因此时间复杂度均是 0(1);

栈的链式存储结构

定义

用链表来实现栈的一种方式，又叫链式栈。

通过一组地址任意的存储单元存放栈中元素：数据域 + 指针域；
只放到链表的一端（栈顶）经行插入和删除操作。
不受栈容量限制，动态分配内存。
栈顶指针（top）指向链表的第一个结点（即栈顶元素）。
入栈和出栈操作都在链表头部进行，时间复杂度为O(1)。

数据结构

/* 链式栈结点定义 */
typedef struct StackNode {
    int data;                   /* 数据域 */
    struct StackNode *next;     /* 指针域，指向下一个结点 */
} StackNode;

/* 链式栈 */
typedef struct {
    StackNode *top;         /* 栈顶指针 */
    int count;              /* 记录当前链式栈中元素个数 */
} LinkStack;

进栈

进栈步骤由上图所示 1->3。

定义一个新结点 p 是要插入的结点。把元素 e 放入结点 p 的数据域。
把结点 p 的指针域指向 S 的栈顶。
把栈顶指针指向新结点 p。

Status Push (LinkStack *S, SElemType e)
{
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode);

    p->data = e;
    p->next = S->top;
    S->top = p;

    S->count++;

    return OK;
}

出栈

结点 p 是要出栈的结点。

将栈 S 的 top 指针下移动一个：S->top = S->top->next;
释放 p: free(p);

Status Pop(LinkStack *S, SElemType *e)
{
    LinkStackPtr p;

    if(StackEmtpy(*e))  /* 判断栈是否为空 */
        return ERROR;

    *e = S->top->data;  /* 取出要弹出的元素 */
    p = S->top;         /* 栈顶赋值给p, 表示p为栈顶结点 */

    S->top = S->top->next;  /* 下移动栈顶指针 */
    free(p);                /* 释放结点p */

    S->count--;

    return OK;

}

总结：

进栈和出栈没有任何循环，时间复杂度都为O(1)。

顺序栈与链式栈，它们在时间复杂度上是一样的，均为 0(1) 。

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链式栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

栈的应用-递归

通常指的是在递归调用过程中，系统自动利用栈结构来保存每一层递归调用的现场信息（如参数、局部变量、返回地址等）。每进入一次递归，就把当前状态压入栈中，递归返回时再依次弹出，恢复现场。本质：递归调用依赖栈来保存和恢复各层调用的状态，实现“后进先出”的调用关系。

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数
每个递归定义必须至少有 1 个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

示例：

// 递归实现阶乘，并演示系统调用栈的作用
#include <stdio.h>

// 计算 n 的阶乘
int factorial(int n) {
    if (n == 1)           // 递归出口
        return 1;
    else
        return n * factorial(n - 1); // 递归调用，系统自动用栈保存每层状态
}

int main() {
    int num = 5;
    printf("%d! = %d\n", num, factorial(num));
    return 0;
}

队列

定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。也是一种先进先出（First In First Out）的线性表，简称FIFO。

队列的顺序存储缺点与改进：缺点：

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为 1 种特殊的线性表，也同样存在这两种存储方式。

假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组：

入列就是在队尾加一个元素，不需要移动任何元素，此时时间复杂度为O(1)。

出列在队头，即下标为 0 的位置，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为 0 的位置不为空，此时时间复杂度为 O(n)。

改进：

但是出队列时为什么一定要所有元素都移动呢，如果不限制队列的存储元素必须存储在前n个范围，即对头不一定要在下标为0的位置，出队性能就大大增加。如下图：

循环队列

定义

头尾相接的顺序存储结构称为循环队列

为了避免当有一个元素时，队头和队尾重合使处理变得麻烦，所以定义2个指针:

front: 指向队头元素。
rear：指向队尾元素的下一个位置。

这样当 front = rear 时，此队列不是还剩一个元素，而是空队列。

定义队列的长度为： QueueSize

则队列满的条件为：(rear + 1) % QueueSize == front。当 rear > front 时，此时队列的长度为 rear - front。当 rear < front 时，队列长度一段是 QueueSize - front，另一段是 0 + rear。两段加在一起：rear - front + QueueSize。因此通用的计算队列长度公式为：

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

/* 循环队列求长度 */
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->fornt) /* 队列满的判断*/
        return ERROR;

    Q->data[Q->rear] = e; /* 将元素e赋值给队尾 */
    Q->rear = (Q->rear+1)%MAXSIZE;  /* rear指针后移一位 */

    return OK;
}

循环队列的出队列操作

/* 若队列不空，则刪除Q中队头元素，用e返回其值*/
Status DeQueue(SqQueue *Q, QElemType *e)
{
    if (Q->front == Q->rear) /* 队列空的判断 */
        return ERROR;
    *e = Q->data[Q->front];  /* 将队头元素赋值给e */
    Q->front = (Q->front+1)%MAXSIZE; /* front 指针后移一位 */

    return OK;
}

队列的链式存储结构

定义

队列的链式存储结构，就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

数据结构

typedef int QElemType;

/* 结点结构 */
typedef struct QNode{
    QElemtype data;
    struct QNode *next;
}QNode, *QueuePrt;

/* 队列的链表结构 */
typedef struct{
    QueuePtr front,rear; /* 队头，队尾指针 */
}LinkQueue;

入队

入队操作，就是在链表尾部插入结点。

Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s)
        return ERROR;

    s->data = e;
    s->next = NULL;
    Q->rear->next = s; /* 把拥有元素e新结点s赋值给原队尾结点的后继 */

    Q->rear = s;    /* 把当前的s设置为队尾结点，rear指向s */

    return OK;
}

出队

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;

    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;
    free(p);

    return OK;
}

总结：

在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

栈

定义

栈的顺序存储结构

结构定义

进栈

出栈

栈的链式存储结构

定义

数据结构

进栈

出栈

总结：

栈的应用-递归

队列

定义

循环队列

定义

数据结构

循环队列的入队列操作

循环队列的出队列操作

队列的链式存储结构

定义

数据结构

入队

出队

总结：

发送评论 编辑评论

推荐文章

发送评论编辑评论