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

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 条评论
登录 后参与评论

相关文章

来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2536
来自专栏魂祭心

原 canvas绘制clock

4064
来自专栏ASP.NETCore

ASP.NET Core 整合Autofac和Castle实现自动AOP拦截

除了ASP.NETCore自带的IOC容器外,我们还可以使用其他成熟的DI框架,如Autofac,StructureMap等(笔者只用过Unity,Ninjec...

674
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏菩提树下的杨过

Flash/Flex学习笔记(23):运动学原理

先写一个公用的小球类Ball: package{ import flash.display.Sprite; //小球 类 public class B...

25310
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

3859
来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6818
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2645
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2707
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4848

扫码关注云+社区