专栏首页张俊红数据结构-栈和队列

数据结构-栈和队列

总第117篇

前言

本章节开始数据结构第二篇,栈和队列:

栈:

  • 栈的存储结构
  • 栈的基本操作

队列:

  • 队列的存储结构
  • 队列的基本操作

前文回顾:数据结构—线性表

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

栈首先是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系,只不过它是一种特殊的线性表而已。

栈的特殊之处在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。

栈的插入操作,叫做进栈;栈的删除操作叫做出栈。

1.栈的存储结构

用来存放栈的数据元素对应的数据存储结构称为栈的存储结构。

1.1栈的顺序存储结构

栈是线性表的特例,所以栈的顺序存储结构其实就是线性表顺序存储结构的简称,我们简称为顺序栈。线性表是用数组来实现的,对于栈这种只能一头插入删除的线性表来说,用数组下标为0(栈底不变,只需要跟踪栈顶的变化即可)的一端作为栈底比较合适。

顺序栈定义如下:

typedef struct
{
    int data[maxsize];    //定义一个数组大小为maxsize的数组,用来存放栈中数据元素
    int top;              //栈顶指针
}SqStack;                 //顺序栈定义

1.2栈的链式存储结构

栈顶放在单链表的头部,用链表来存储栈的的数据结构称为链栈。

链栈结点定义如下:

typedef struct LNode
{
    int data;                //数据域
    struct LNode *next;      //指针域
}LNode;                      //链栈结点

2.栈的操作

2.1顺序栈的操作

对于顺序栈,一共有4个要素,包括两个特殊状态和两个操作。

特殊状态: 1)栈空状态:st.top == -1,也有的用st.top = 0表示栈空,这个时候栈顶位置为0。 2)栈满状态:st.top == maxsize-1表示栈满。maxsize为栈中最大元素个数,maxsize-1为栈满时栈顶元素在数组中的位置,因数组位置是从0开始的。

操作: 顺序栈的进栈和出栈操作都是在栈顶进行的,所以只需要更改栈顶位置即可达到进栈和出栈的目的。

1)初始化栈:

void initStack(SqStack &st)    //初始化栈
{
    st.top = -1;               //栈顶指针设置为-1
}

2)进栈操作:

int push(SqStack &st,int x)
{
    if(st.top == maxsize-1)    //判断栈是否满,如果满,则不能进栈
        return 0;
    ++(st.top);                //栈顶指针位置加1
    st.data[st.top] = x        //x进栈,放在st.top位置
        return 1;
}

3)出栈操作: 出栈与进栈是相对应的操作

int push(SqStack &st,int x)
{
    if(st.top == -1)           //判断栈是否为空,如果空,则不能进行出栈
        return 0;
    x = st.data[st.top]     //先把栈顶元素取出来
    --(st.top);                 //栈顶指针位置减1
    return 1;
}

4)简化版的操作:

/*初始化栈*/
int stack[maxsize];
int top = -1;

/*元素x进栈*/
stack[++top] = x

/*元素x出栈*/
x = stack[top--]

/*注意++top和top++的区别*/
top = 1
a = ++top
b = top++

a = 2
b = 1

2.2链栈的操作

与顺序栈对应,链栈也有4个元素,包括两个状态和两个操作。

状态: 1)栈空:lst -> next == NULL,即栈没有后继结点时,栈为空。 2)栈满:如果存储空间无限大的话,不会存在栈满的情况。

操作: 链栈的进栈就是头插法建立链表的插入操作;出栈就是单链表的删除操作。

链栈的插入操作

栈的删除操作 1)链栈初始化:

void initStack(LNode *&lst)
{
    lst = (LNode*)malloc(sizeof(LNode));    //制造一个头结点
    lst -> next = NULL;                     //初始头结点指向为NULL
}

2)进栈:

void push(LNode *lst,int x)
{
    LNode *p;
    p = (LNode*)malloc(sizeof(LNode));    //为进栈元素申请结点空间
    p -> next =NULL;                      //初始化结点不指向任何元素

    /*进栈,相当于链表的头插法*/
    p -> data = x;    //将x赋值给p结点的值域
    p -> next = lst -> next;    //p指针指向原lst指向的结点
    lst -> next = p;            //lst指向结点p
}

3)出栈:

int pop(LNode *lst,int &x)
{
    LNode *p;
    if(lst -> next == NULL)    //栈空则不能出栈,返回0;而栈不会满,所以在进栈的时候未作判断
        return 0;
    /*出栈,相当于链表的删除结点*/
    p = lst -> next;
    x = p -> data;
    lst -> next = p -> next;
    free(p);
    return 1;
}

4)简化版操作:

/*元素(指针p所指)进栈操作*/
/*类似于头插法建立链表*/
p -> next = lst -> next;    //将空栈的头结点指向p
lst -> next = p;            //将指针p指向空栈头结点


/*出栈操作(出栈元素保存在x中)*/
/*类似于单链表的删除操作*/
p = lst -> next;
x = p -> data;
lst -> next = p -> next;
free(p);

队列:

队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表,队列是一种先进先出的线性表,简称FIFO,允许插入的一端称为队尾(Rear),允许删除的一端称为队头(Front)。向队中插入元素称为进队,新元素进队后成为新的队尾元素;向队中删除元素称为出队,元素出队后,其后继元素就成为新的队头元素。

1.队列的存储结构

用来存储队列数据元素的数据结构。

1.1队列的顺序存储结构:

使用顺序表存储队列时,队列元素的出队是在队头,即下标为0的地方,当有元素出队时,出队元素后面的所有元素都需要向前移动,保证队列的队头始终处在下标为0的位置,此时会大大增加时间复杂度。

用顺序表来存储队列元素的数据结构称为队列的顺序存储结构,定义如下:

typedef struct
{
    int data[maxsize];        //定义数组
    int front;                //队首指针
    int rear;                 //队尾指针
}SqQuene;                     //顺序队列定义

1.2队列的链式存储结构:

用链表来存储队列元素的数据结构称为队列的链式存储结构,定义如下:

队列结点类型定义:

typedef struct QNode
{
    int data;                //数据域
    struct QNode *next;      //指针域
}QNode;                      //队结点类型定义

链队类型定义:

typedef struct
{
    QNode *front;        //队头指针
    QNode *rear;         //队尾指针
}LiQuene;                //链队类型定义

2.队列操作

2.1循环队列

因为顺序队列出队时时间复杂度较高,有问题总是要解决的,为什么一定要让队头出现在下标为0的位置呢?所以有人提出了不去限制队列元素必须存储在数组的前n个单元这一条件,这样队头元素就不需要一定在下标为0的位置。但是随着队列元素的出队,队头指针在向后移动,假设队尾指针已经在maxsize-1的位置,这个时候虽然队列还有存储空间,但是队尾已经无法进队了,比如下图这样:

虽然下标为0和1的位置处还有空间,但是队尾已经无法再有新元素进队,我们把这种情况称为“假溢出”,为了解决这种假溢出的问题,就提出了循环队列的概念,让队列的头尾进行相连,这种头尾相连的顺序存储结构称为循环队列。

循环队列需要损失一定的空白,这样只有在队空的时候才会出现front=rear。

循环队列的要素:

两个状态: 队空状态:

qu.rear = qu.front

队满状态:

(qu.rear+1)%maxsize == qu.front

两个操作: 元素x进队操作(移动队尾指针)

qu.rear = (qu.rear+1)%maxSize;
qu.data[qu.rear] = x;

元素x出队操作(移动队头指针)

qu.front = (qu.front+1)%maxSize;
x = qu.data[qu.front];

初始化队列算法:

void initQueue(SqQueue &qu)
{
    qu.front = qu.rear = 0;队首和队尾指针重合,并且指向0
}

进队算法:

int enQueue(SqQueue &qu,int x)
{
    if ((qu.rear + 1) % maxSize == qu.front)    //队满的判断条件,如果队满则不能进队,返回0
        return 0;
    qu.rear = (qu.reat+1)%maxSize;              //若队不满,先移动队尾指针
    qu.data[qu.rear] = x;                       //元素x进队
    return 1;
}

出队算法:

int enQueue(SqQueue &qu,int &x)
{
    if (qu.rear == qu.front)    //队空的判断条件,如果队空则不能出队,返回0
        return 0;
    qu.front = (qu.front+1)%maxSize;              //若队不空,先移动队首指针
    x = qu.data[qu.front] ;                       //元素x出队
    return 1;
}

2.2链队:

链队就是采用链式存储结构存储队列。链队的四个要素:队空和队满,元素进队和出队操作。

队空状态:

lqu -> rear == NULL; or lqu -> front == NULL

队满状态: 一般来说不存在队满的情况,只要内存足够大。

元素进队操作(指针p指向进队元素)

lqu -> rear -> next = p;
lqu -> rear = p;

元素出队操作(x存储出队元素)

p = lqu -> front;
lqu -> front = p -> next;
x = p -> data;
free(p);

初始化链队算法

void initQueue(LiQuene *&lqu)
{
    lqu = (LiQueue*)malloc(sizeof(LiQueue));
    lqu -> front = lqu -> rear = NULL;
}

判断队空算法

int isQueueEmpty(LiQueue *lqu)
{
    if(lqu -> rear == NULL || lqu -> front == NULL)
        return 1;
    else
        return 0;
}

入队算法

void enQueue(LiQueue *lqu,int x)
{
    QNode *p;
    p = (QNode*)malloc(sizeof(QNode));
    p -> data = x;
    p -> next =NULL;
    if(lqu -> rear == NULL)
        lqu -> front = lqu -> rear = p;    //如果队列为空,则新结点既是队尾结点也是队首结点
    else
    {
        lqu -> rear -> next = p;           //将新结点链接到队尾,rear指向该结点
        lqu -> rear = p;
    } 
}

出队算法

int deQueue(LiQueue *lqu,int &x)
{
    QNode *p;
    if(lqu -> rear == NULL)    //判断队空,如果为空,则不能出队
        return 0;
    else
        p = lqu -> front;
    if(lqu -> front == lqu -> rear)    //队列中只有一个结点时的出队操作
        lqu -> front = lqu -> rear =NULL
    else
        lqu -> front = lqu -> front -> next;
    x = p -> data;
    free(q);
    return 1;
}

本文分享自微信公众号 - 张俊红(zhangjunhong0428)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-21

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 讲讲你不知道的窗口函数

    我们都知道 SQL 中的聚合函数,聚合函数顾名思义就是聚集合并的意思,是对某个范围内的数值进行聚合,聚合后的结果是一个值或是各个类别对应的值。如下所示:

    张俊红
  • 内连接的两种方式

    在前面的文章中我们讲过两个概念,宽表和窄表,在现实业务中,数据库中很多表存储其实都是以窄表的形式来存储的,但是我们一般从数据库中获取信息的时候,都是需要同时从多...

    张俊红
  • 谈谈弹性为何物

    弹性这个词感觉很熟悉又感觉很陌生,熟悉是因为平常经常会听到,比如弹性工作制、弹簧弹性等等,陌生是因为一下子好像也说不出这个词到底代表什么意思。今天这一篇就来捋一...

    张俊红
  • 队列

    队列的基本操作有初始化队列,判队列是否为空,入队,出队 栈可分为两种存储结构:顺序队和链队。 顺序队 /* 顺序队结构 */ typedef struct {...

    静默虚空
  • 01.【Kevin聊敏捷】传统项目管理VS敏捷项目管理对比-各模式的发展历程

     在1969年以前,不管是制造汽车还是制造轮船,全世界的项目管理都没有太多的章法和规则。直到1969年美国成立了PMI组织,推出了PM Bok一整...

    开心的Kevin
  • 数据结构【第六篇】队列 (queue) 的实现与讲解

    中午在食堂打饭,真是一个令人头疼的事情,去食堂的路上也总是步伐匆匆,为什么啊,这还用说,迟一点去,你就会知道什么叫做人山人海了,在食堂排队的时候,相比较学生来说...

    BWH_Steven
  • 数据结构(四)

    那么再简单地回顾一下,链表是一种数据的存储方式,保存数据在内存中不连续,用指针进行访问。

    可爱见见
  • 队列的存储结构的实现(C/C++实现)

    存档 1 #include "iostream.h" 2 #include "stdlib.h" 3 #define max 20 4 typedef ...

    Angel_Kitty
  • 使用Java操作Elasticsearch(Elasticsearch的java api使用)

    1、Elasticsearch是基于Lucene开发的一个分布式全文检索框架,向Elasticsearch中存储和从Elasticsearch中查询,格式是js...

    别先生
  • 解析ROS(机器人操作系统)

    在2007年,斯坦福人工智能实验室的人们意识到重用代码对社区有很大帮助时,ROS才开始活跃起来。之后,它搬到了硅谷的一个名为Willow Garage的孵化中心...

    AI研习社

扫码关注云+社区

领取腾讯云代金券