IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构笔记3——栈和队列 -> 正文阅读

[数据结构与算法]数据结构笔记3——栈和队列

笔记中图片均来源于课堂PPT

正在学习中,如有错误欢迎指正!


一、栈的简介及性质

栈是一种特殊的线性表,仅在表的一端进行插入或删除操作。

最令人关心的是栈的性质:栈中的元素遵循着后进先出,先进后出的规则(LIFO),出于这个性质,我们可以将栈类比于抽屉这样的存储结构,所有最先放入抽屉中的元素会被放到最深处,难以拿到,只有最后才能出栈。所以,我们大多数对栈的操作,实质上都是对栈顶元素、栈顶位置的操作。

??附上PPT中辅助理解的一个例子:

小陈作业没有及时完成,第二天写完后,交到段老师的办公室里,正好段老师不在。小陈看到大家的作业本都摞成一叠放在段老师的办公桌上,就把自己的作业本放到本子堆上。正要离开的时候,他突然想把本子插到作业本堆的下面。在他费力地搬开上面的作业本时,段老师回来了,及时地制止了他……

此处插入到最下端的操作换成栈的语言就是:小陈想将最后的元素插入到栈底结果遭到阻止,违背了栈后进先出的规则(最后插入的作业却放到栈底想最后被批到),这显然是不可取的。?

二、栈的基本操作

栈的基本操作有:创建,入栈,出栈,遍历,下面我们来一个一个拆解着分析。

1.栈的定义

为了方便后续操作,在创建一个栈之前,我们先来定义栈的数据类型。前面已经提到,栈是特殊的线性表,所以栈的定义应该和线性表有相似之处,根据线性表的定义,可以知道:栈也应该有两种定义方式,它们是顺序栈和链栈,分别对应着顺序表和链表。接下来,我们也用这两种方式来定义栈。

①顺序栈

顺序栈和顺序表非常相似,它们都由一个int型单变量和一个int型数组构成,其中数组寄存着元素的数值;对于栈中的另一个int型元素,我们定义它为top,其意义为栈顶目前所处的位置。

如此一来,我们既有了栈当前元素(也就是栈顶元素)的值,又有了它在整个栈中的位置,就可以利用数组和数组下标top来实现栈的其他基本操作了。

不过这里要注意的是,虽然在大多数情况下我们都把top作为栈数组下标来完成操作,但stack->top却是从-1开始的,也就是说,当栈空时的stack->top=-1,这点理解起来确实很别扭,遇到变下标的问题时,要和数组区分好。

顺序栈定义的代码如下:

typedef struct stacktype
{
    int elem[maxnum];//存放栈中元素的一维数组
    int top;//数组下标top
} mystack;

②链栈

链栈理解起来更容易一点,它和链表比较相似,但是在栈的定义中,我们不需要定义头结点(后面会详细介绍原因),只需要定义一个data指向元素域,*next指针指向下一个元素,以及栈的长度length即可完成栈的操作。

链栈的定义如下:

typedef struct lineStack {
    int data;
    lineStack* next;
    int length;
}mystack;

2.入栈操作

在已经学过顺序表的插入之后,对于入栈来说,我们唯一需要再仔细思考的就是栈满条件,对于顺序栈和链栈,栈满条件并不相同,下面我们逐个分析。

?①顺序栈

在顺序栈中没有length的属性,所以为了定义栈满的状态,在全局中定义了一个maxnum作为栈的最大长度(其实这就是变相的定义length),此刻,栈满的条件也显而易见的浮出水面:因为stack->top从-1开始,所以栈满时必有stack->top == (maxnum - 1)

谈完了栈满,再来看常规操作:在每一次元素入栈时,首先为这个元素腾出一个新的位置(top++),然后在这个空位置放入元素(elem[stack->top] = x),就完成了入栈操作。

代码如下:

#define maxnum 10
void push(mystack *stack, int x)
{
   
    if (stack->top == (maxnum - 1))
    {
        printf("the stack is full");
        return;
    }
    stack->top++;
    stack->elem[stack->top] = x;
}

②链栈

链栈元素的入栈方式与链表比较像,它们大体上都是通过动态分配内存、data赋值、next变化来完成插入或入栈操作的。特殊的是,在栈中,为了维护栈“后入先出”的特性,我们需要对插入的顺序进行一定的变化:将插入元素放在第一位,然后接原来的stack。例如:插入元素为4,原来的栈中元素为3、2、1,令4->next=stack,可以得到新栈4、3、2、1)这样就做到了新插入的元素放在表的第一位。

代码如下:

lineStack* push(mystack* stack, int a)
{
    lineStack* line = (lineStack*)malloc(sizeof(lineStack));
    line->data = a;
    line->next = stack;
    stack = line;
    return stack;
}

需要说明的是:该代码没有限制长度对入栈的限制,如果需要通过输入元素的个数来决定是否继续进行入栈,可以加入一个条件判断语句判定是否栈满。?

3.出栈操作

出栈的意思为:将栈中最顶层的元素弹出,并返回该元素的值,所以应该用一个int型函数来完成该操作。

①顺序栈

有了前面的数据结构作为铺垫以及我们日渐准确的直觉( ̄▽ ̄)~*?要想弹出元素,首先要判断栈是否非空,根据前面介绍的栈空条件(stack->top=-1)可以很简单的完成。

弹出元素和插入元素很相似,唯一需要注意的就是:在出栈过程中,需要先弹出元素,再改变top的位置,否则元素弹出的位置会错误(例如:栈的元素为4、3、2、1,若先改变top的位置,那么stack->top=3,弹出时得到的栈顶元素是错误的。)

int pop(mystack* stack)
{
    // 将stack的栈顶元素弹出,赋值给x
    int x = 0;
    if (stack->top == -1)
    {
        printf("the stack is empty\n");//栈空
        return -1;
    }
    x = stack->elem[stack->top];
    stack->top--;
    return x;
}

②链栈

链栈的出栈也很简单,和链表一样,它最核心的一步在于stack=stack->next,比较容易,就不细说啦,直接放代码:

mystack* pop(mystack* stack)
{
    int i=0;
    if (stack->data == NULL && stack->data != 0)
    {
        printf("no data");
    }
    i = stack->data;//弹出元素的值
    stack = stack->next;//注意这里变成next之后length就不要--了,因为我的这个length是对每个stack分别赋值的,是可变属性,改变了stack,也就改变了length。当然,如果你是在入栈结束后再统一赋予length的话,此处应该--
    printf("the out elem is:%d\n", i);//如果不需要打印弹出元素可以不打印此句
    return stack;
}

4.栈的遍历

①顺序栈

顺序栈的思路比较简单,我们需要做的只有:判空,循环,输出,和数组的遍历比较类似,代码如下:

void printstack(mystack* stack)
{
    if (stack->top == -1)
    {
        printf("no data\n");
        return;
    }
    printf("the data in the stack are:\n");
    int num = stack->length;//只要stack->length作为比较变量就会出现异常,所以只能先用数字储存了
    for (int i = 0; i < num; i++)
    {
        printf("%d ", stack->elem[i]);
    }
    printf("\n");
}

②链栈

链栈相对来说就复杂一些,但万变不离其宗,它的核心仍然是:print stack->data,stack=stack->next,只需要在变化过程中维护栈的性质不变。

首先,由于栈的不断遍历,stack变成stack->next,又变成stack->next->next......,这就导致了在执行完遍历函数回到main函数后,栈的top已经发生了变化,所以,要想正确的完成之下来的操作,需要将栈的top变为原来的top。在函数开头未进入循环时记录top值,在最后重新赋值就可以实现该过程。

void printstack(mystack* stack)
{
    int i;
    int p=stack->top;
    if (stack->data == NULL)
    {
        printf("no data");
        return;
    }
    int num = stack->length;//只要stack->length作为比较变量就会出现异常,所以只能先用数字储存了
    for (i = 0; i < num; i++)
    {
        printf("%d ", stack->data);
        if (stack->next == NULL)
        {
            return;
        }
        stack = stack->next;
    }
    stack->top=p;
}

三、队列的简介及性质

队列也是一种特殊的线性表,类比于栈,它和栈有着截然相反的性质。

如其名,队列的性质像“队列”一样:先排队、就先出队。也就是说,队列中的元素符合“先进先出,后进后出”(FIFO)的准则。根据这个性质,队列可被比作为钟摆:每次插入元素只在钟摆的一端(队尾)进行,删除元素在钟摆的另一端(队首)进行。所以,我们对队列的操作,也大多数是对队首元素和队尾元素的操作。

?四、队列的基本操作

队列的基本操作有:创建,入队,出队,遍历,下面我们来一个一个拆解着分析。

1.队列的定义

首先,我们来用数组实现队列。

设想一下,在这个定义队列的结构体中,必须要有一个储存队列每个元素值的数组,来存放数据的值;其次,为了方便后续对队首队尾的元素进行操作,我们定义两个指向队首队尾的“指针”变量。由于这是用数组实现的队列,所以指向位置的变量不必用真正的指针变量,用数组下标即可代替。

这样一来,就有了储存元素值的储存结构,还有指向位置的“指针”用来进行位置的移动,这样就完成了队列的定义。

typedef struct queue
{
    int data[N];//数组存放元素值
    int rear;//队尾指针
    int front;//队首指针
}myQueue;

2.队列的初始化

我们在定义队列时,定义了两个int型变量,它们分别为rear和front,现在我们用这两个int型变量作为“指针”,在之后的操作中,我们将用这两个变量控制队尾和队首的元素。

当初始化队列时,队列中没有数据,只需将队首和队尾的“指针”归为同一值(且为零)即可

int initQueue(myQueue* q)//初始化队列
{
    q->front = 0;
    q->rear = 0;
    return 1;
}

3.入队操作

有了两个“指针”变量后,我们就可以随心所以的对队首和队尾元素进行操作了,插入新元素、更新队列自然是不在话下,所以我们重点要关注的就是队列满的条件,当队列满后,禁止对头尾元素进行操作。

但是仔细一想,用数组实现的队列好像有点儿难找出它的队满条件,因为如果用动态内存分配+队尾指针不停向后挪的话,它会一直向后延伸,似乎这个队列永远不会到达尽头。

为了节省空间复杂度,优化算法,在真正介绍入队操作之前,先引入一个常用(也常考)的用循环数组实现的队列,先来看两幅图:

白色代表空,绿色代表非空

?

这就是循环数组实现队列的特性:当rear指针指向当前队列最后一个元素且队列未满时,再次入队的元素会进入数组第一个元素中去,也就是说,rear和front指针不停的在[0—n-1]之间游走,每当走到最后一个位置,下一次再向前时,就返回到队列第一个位置,这就是循环数组定义的队列。还需要注意的是:作为编程的习惯,rear为指向队尾下一个可存放节点的位置,而不是当前队尾元素,这么说可能有点别扭,但在之后的例子中将深化对它的表述和理解接下来,我们的操作都是基于这种队列。

好了,那么我们来真正的判断队满的条件,注意一下:我们现在定义的队列满,不是真正意义上的全满,而是队列仍然有一个可以放元素的位置时,就判断它已经满。现在直接给出结论:

当 (rear +1) % MAXNUM = = front时,队列满。

maxnum代表循环数组的长度

?来解读一下这个判断式,rear指向下一个可放元素位置。根据图中可知,当rear和front成为邻居时,队伍可判满,而后面的对maxnum取余则是因为在循环数组中下标逐渐递增,当循环一圈会再次回头,所以要取余来变成物理意义上的位置。

比如说:maxnum=7,front=2,rear=1,带入队满条件后队列已满,所以该队满条件成立。

void inqueue(myQueue *queue, int elem)
{
    if ((queue->rear + 1) % N ==queue->front)
    {   printf("the queue is full");//队满条件:此位置的下一个地方有位置,否则rear挪不走
        return;
    }
    queue->data[queue->rear] = elem;//该能放入元素的队尾放入元素
    queue->rear = (queue->rear + 1) % N;//rear挪动到下一位
    
}

3.出队操作?

和入队相反的是,在出队过程中,我们首先要判断队列是否非空,非空则会得到错误输出,那么现在来寻找队空条件。

现在我们可以放心大胆的说:当rear==front的时候,队伍为空了,因为如果队列是空的,下一个放元素位置的指针rear和队首指针将会重合(如果它们不是一个位置的话,可以设想插入一个元素之后的情景,将会发生错误)

?出队代码如下,其中要注意移动front的位置以起到出队的效果。


int dequeue(myQueue *queue) 
{
    int out;
    if (queue->rear == queue->front)
    {
        printf("the queue is empty");
        return 0;
    }        
    else 
    {
    out =queue->data[queue->front];//提取队首元素
    queue->front = (queue->front + 1) %N;//移动指针,使front指向下一位
    }
    return out;
}

4.队列的遍历

其实队列的遍历和线性表比较相似,只要每次输出元素后,rear向后挪动一格,直到rear和front相遇(即每个元素都遍历到,队空),就结束遍历,比较简单,直接放代码了。

void printqueue(myQueue* queue)
{
    int elem;
    printf("the data in the queue are:\n");
    while (queue->rear!= queue->front)
    {
        elem = queue->data[queue->front];//提取队首元素
        queue->front = (queue->front + 1) % N;
        printf("%d ", elem);
    }
    return;
}

这篇笔记断断续续写了两个多月,我真是太能拖了quq

马上就要考数据结构啦,加油!?

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-10 11:18:39  更:2021-12-10 11:19:41 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/10 3:24:49-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码