【图解数据结构】 栈&队列

1.栈

1.1栈的定义

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

我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不包含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。

栈的插入操作,叫做进栈,也称压栈、入栈。

栈的删除操作,叫做出栈,也称弹栈。

1.2栈的顺序存储结构及实现

既然栈是线性表的特例,那么栈的顺序存储其实也是线性表顺序存储的简化。

用数组实现,下标为0的一端作为栈底比较好,因为首元素都存在栈底。

栈的结构定义:

定义一个top变量来指示栈顶元素在数组中的位置,若存储栈的长度为SackSize,则栈顶位置top必须小于SackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件为top=-1。

typedef int SElemType;
typedef struct 
{
    SElemType data[MAXSIZE];
    int top;        /*用于栈顶指针*/
} SqStack;

1.3栈的顺序存储结构——进栈操作

代码实现:

#define MAXSIZE 5
#define OK 1
#define ERROR 0

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, SElemType e)
{
    if (S->top == MAXSIZE - 1)  /*栈满*/
    {
        return ERROR;
    }
    S->top++;
    S->data[S->top] = e;
    return OK;
}

测试代码:

int main()
{
    SqStack stack = { {1,2},1 }; /*初始化栈内有两个元素,top=1*/
    Push(&stack, 3);
}

运行结果:

1.4栈的顺序存储结构——出栈操作

代码实现:

#define MAXSIZE 5
#define OK 1
#define ERROR 0

/*若栈不为空,则删除S的栈顶元素,用e返回其值*/
Status Pop(SqStack *S, SElemType *E)
{
    if (S->top == -1)
    {
        return ERROR;
    }
    *E = S->data[S->top];
    S->data[S->top] = NULL;
    S->top--;
    return OK;
}

测试代码:

int main()
{
    SElemType e;
    SqStack stack = { {1,2},1 }; /*初始化栈内有两个元素,top=1*/
    Push(&stack, 3);
    Pop(&stack, &e);
}

运行结果:

验证了后进先出的结构。

1.5栈的链式存储结构及实现

栈的链式存储结构,简称为栈链。由于单链表有头指针,而栈顶指针也是必须的,那么便可以让它俩合二为一。以为就是说栈顶放在单链表的头部。

对于链栈来说,基本不存在栈满的情况,除非内存已经没有可以使用的空间。但是对于空栈来说,链表原定义是头指针指向空,那么链栈的空其实就是top=NULL。

栈链的结构代码如下:

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

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

1.6栈的链式存储结构——进栈操作

代码实现:

#define OK 1
#define ERROR 0
typedef int Status;
typedef int SElemType;

/*插入元素e为新的栈顶元素*/
Status Push(LinkStatck *S, SElemType e)
{
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data = e;
    s->next = S->top;
    S->top = s; /*将新的节点s赋值给栈顶指针*/
    S->count++;
    return OK;
}

测试代码:

int main()
{
    LinkStatck stack = { NULL ,0}; /*初始化一个空链栈*/
    Push(&stack, 1);
    Push(&stack, 2);
    Push(&stack, 3);
}

运行结果:

动画模拟:

1.7栈的链式存储结构——出栈操作

代码实现:

#define OK 1
#define ERROR 0
typedef int Status;
typedef int SElemType;

/*若栈不为空,则删除S的栈顶元素,用e返回其值*/
Status Pop(LinkStatck *S, SElemType *e)
{
    LinkStackPtr p;
    if (S->count == 0)
    {
        return ERROR;
    }
    *e = S->top->data;
    p = S->top; /*将栈顶节点赋值给p*/
    S->top = S->top->next;  /*使栈顶指针下移一位,指向后一节点*/
    free(p);        /*释放节点p*/
    S->count--;
    return OK;
}

测试代码:

int main()
{
    LinkStatck stack = { NULL ,0}; /*初始化一个空链栈*/
    Push(&stack, 1);
    Push(&stack, 2);
    Push(&stack, 3);
    SElemType e;
    Pop(&stack, &e);
    Pop(&stack, &e);
    Pop(&stack, &e);
}

运行结果:

动画模拟:

2.队列

2.1队列的定义

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。

2.2队列的顺序存储结构

我们假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组。

现在进行入队操作,就是在队尾插入一个元素,不需要移动任何元素,因此时间复杂度是O[1]。

出队操作是在队头,那么队列中所有的元素都要向前移动一个位置,确保下标为0的位置不为空,时间复杂度是O[n],这是个问题。

如果不限定出队操作时所有的元素都要向前移动,也就是说队头不一定必须在下标为0 的位置,出队的性能就会大大增加。

但是这样又会出现另一个问题——假溢出,就是假设队列前面的位置是空着的,但是从队尾入队已经满了。

循环队列可以解决这一个问题,后面满了,就从头再开始,也就是头尾相接的循环,这种头尾相接的顺序存储结构称为循环队列。

但是循环队列还是会面临着数组溢出的问题。

2.3队列的链式存储结构及实现

队列的链式存储结构,其实就是线性表的单链表,只不过它能尾进头出而已,简称链队列。

队头指针指向链队列的头节点,而队尾指针指向终端节点:

空队列时都指向头节点:

链队列的结构如下:

typedef int QElemType;
typedef struct QNode /*结点结构*/
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

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

2.4队列的链式存储结构——入队操作

入队操作,在队尾插入新元素。

代码实现:

#define OK 1
#define ERROR 0

typedef int Status;
/*插入元素e为Q的新的队尾元素*/
Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    s->data = e;
    s->next = NULL;

    Q->rear->next = s;      /*把拥有元素e新节点s赋值给原队尾结点的后继*/
    Q->rear = s;        /*把s设置为队尾结点,rear指向s*/

    return OK;
}

测试代码:

int main()
{
    /*头结点*/
    QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
    head->data = 0;
    head->next = NULL;

    LinkQueue q = { head ,head }; //空队列,队头、队尾指针都指向头结点

    EnQueue(&q, 1);
    EnQueue(&q, 2);
}

运行结果:

动画模拟:

2.4队列的链式存储结构——出队操作

代码实现:

#define OK 1
#define ERROR 0

typedef int Status;
/*若队列不为空,删除Q的队头元素,用e返回其值*/
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if (Q->front == Q->rear)
    {
        return ERROR;
    }
    p = Q->front->next;  /*将欲删除的队头节点暂存给p*/
    *e = p->data;
    Q->front->next = p->next;    /*将原队头结点后继赋值给头结点后继*/

    if (Q->rear == p) /*若队头是队尾,则删除后将rear指向头结点*/
    {
        Q->rear = Q->front;
    }

    free(p);
    return OK;
}

测试代码:

int main()
{
    /*头结点*/
    QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
    head->data = 0;
    head->next = NULL;

    LinkQueue q = { head ,head };

    EnQueue(&q, 1);
    EnQueue(&q, 2);
    QElemType e;
    DeQueue(&q, &e);
}

运行结果:

动画模拟:

原文发布于微信公众号 - 撸码那些事(lumanxs)

原文发表时间:2018-05-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

用O(1)的时间复杂度删除单链表中的某个节点

给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下: struct ListNode { int m_nKe...

1958
来自专栏十月梦想

js二维数组遍历

732
来自专栏大壮

iOS直播(基础篇)-rtmpdefine NALU_TYPE_SLICE 1define NALU_TYPE_DPA 2define NALU_TYPE_DPB 3define NALU_TYPE_

1272
来自专栏积累沉淀

初识HtmlParser

1、概念 网页解析,即程序自动分析网页内容、获取信息,从而进一步处理信息。 htmlparser包提供方便、简洁的处理html文件的方法,它将html页面中...

1905
来自专栏张俊红

数据结构-栈和队列

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

932
来自专栏闪电gogogo的专栏

【数据结构(C语言版)系列二】 栈

栈和队列是两种重要的线性结构。从数据结构角度看,栈和队列也是线性表,但它们是操作受限的线性表,因此,可称为限定性的数据结构。但从数据类型角度看,它们是和线性表大...

802
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(二):基本操作(判断、运算、基本函数)

SAS生成新变量 SAS支持基本的加减乘除,值得一提的是它的**代表指数,而不是^。 * Modify homegarden data set with ass...

3524
来自专栏WindCoder

Java设计模式学习笔记—建造者模式

文章最后“Java设计模式笔记示例代码整合”为本系列代码整合,所有代码均为个人手打并运行测试,不定期更新。本节内容位于其Builder包(package)中。

582
来自专栏菩提树下的杨过

无限级分类(非递归算法/存储过程版/GUID主键)完整数据库示例_(2)插入记录

-- ======================================== -- Author:  <杨俊明,jimmy.yang@cntvs.c...

1839
来自专栏数据结构与算法

P2580 于是他错误的点名开始了

题目背景 XS中学化学竞赛组教练是一个酷爱炉石的人。 他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉...

2727

扫码关注云+社区