精华内容
下载资源
问答
  • 栈的top指针指向哪里_栈和队列

    千次阅读 2020-12-03 08:48:27
    栈: 后进先出(Last In First Out,LIFO)的线性序列,称为“栈”。栈也是一种线性表,只不过它是操作受限的线性表,只能在一端进出操作。进出的一端称为栈顶(top),另一端称为栈底(base)。...(top指针永远指向...

    e70a2f2eac55ab11e41a4f5e394909c6.png
    • 栈:

    后进先出(Last In First Out,LIFO)的线性序列,称为“”。栈也是一种线性表,只不过它是操作受限的线性表,只能在一端进出操作。进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储,分别称为顺序栈链栈

    44041063715cc261813871ad2b4066ab.png

    顺序栈:

    顺序栈需要两个指针,base表示栈底指针(指向首地址或基地址)top表示栈顶指针。(top指针永远指向空,即指向栈顶元素的下一位置)

    9e8567ac4499242aa06a1813aae1b9fc.png
    typedef 

    顺序栈的动态分配

    e71c6cb0fb817c8af1c35b4edf81ddb3.png

    顺序栈的静态分配:

    e4f80d112954d5efa7982b9cec68e438.png

    顺序栈初始化:

    01892dfa3d6aaebfd15402c9cb96117d.png
    bool 

    顺序栈入栈:

    注意:每次入栈前,都需要判断栈是否已满。

    fc2b01933b5553b08c6f627a0696fe6b.png
    bool 

    顺序栈出栈:

    注意:每次出栈前都需要判断栈是否为空。

    e48a8ec3d22bb8cf06bb559e40973e22.png
    bool 

    顺序栈取栈顶:

    3f8688c48ef276da3386acae65d63d07.png
    int 
    • 链栈:

    链栈只需要一个指针S指向栈顶元素即可。

    fdbb7da4d9e1e9412739db239413262f.png

    链栈入栈:

    链栈入栈操作:入栈前:指针S指向栈顶结点;入栈后:新生成的结点,指针p指向它;然后把入栈前的栈顶结点的地址赋值给新生成结点的next域,最后更新S指针指向新生成的结点(指向栈顶结点)。

    046bf6bd13ce0d4e29e3b14fd372f5fc.png

    链栈出栈:

    链栈出栈:需要一个指针p标记栈顶元素,用于最后释放空间。出栈:首先:指针p指向栈顶结点,然后更新栈顶指针s指向下一个结点;最后释放指针p指向的结点即可。

    260cdd5166da0e3cb7f1a409e990be2f.png

    链栈取栈顶:

    链栈取栈顶只需要s->data,一步操作即可。

    b17441ff7b0aa6f2e34558f3ad4e31d3.png

    队列:

    先进先出(First In First Out,FIFO)的线性序列,称为“队列”。队列也是一种线性表,只不过它是操作受限的线性表,只能在两端操作:一端进,一端出。进的一端称为队尾(rear),出的一端称为队头(front)。队列可以用顺序存储,也可以用链式存储。

    aebabdb60f1ba4ad8dc3a6cb7b994f01.png

    顺序队列

    队列的顺序存储形式,可以用一段连续的空间存储数据元素,用两个整数变量记录队头和队尾元素的下标。

    3c587bd7f8f04fd4c47c1b5c09df44fb.png

    顺序队列动态分配

    typedef  

    44c0c97c8bb08c002cad541c0f75d5e6.png

    顺序队列静态分配:

    862b5b2ef2d630701e0be3b0be081d6a.png

    顺序队列初始化

    62da75193de40e6433455354545b7cea.png
    //队列的初始化
    

    顺序队列入队:

    02dcf486e33c7251a6eafaa4c0dbed16.png

    将新入队的元素,插在队尾,然后更新下表Q.rear。Q.rear和Q.front都是数组的下标,Q.base是数组。每次入队前要先判断对是否已满。

    Q

    cbe201727526f4fe779aa685c246af25.png

    也可以一边入队,一遍出队。出队Q.front向后移动。

    e

    c08abf009dfe60f2d3c16dafcc03558d.png

    当尾指针指向了空,但是队列前面还存在未占用的空间,这种情况叫做假溢出。此时,将新来的元素插入到队首,这种队列叫做循环队列。代码如下处理,每次移动指针后对Maxsize取余处理临界状态。

    (

    7b6de411ca844a3d706085f692dcfc60.png

    循环队列队空:

    • 循环队列队空条件:
    Q

    8037aeff5425eb6fd9c75cdf09f17b10.png
    • 循环队列队满:

    队满条件:浪费一个空间,当Q.rear的下一个元素为Q.front是表示队满。

    (

    5e4df7d2472270d8473b430c0579d1f5.png

    循环队列入队

    入队:

    Q

    e39b030da681b638b8cb345c5c98756e.png
    //循环队列的入队
    

    循环队列出队

    • 循环队列出队:
    e

    0435fbfb6cc68a85688c29c974c148fa.png
    • 队列中元素个数:
    (

    6f754c96b6f0ac66e257d5c0b39a394c.png
    //循环队列的出队
    

    链队:

    需要头指针,出队跳过第一个结点,入队将新结点插入到尾部即可。

    4394207b2610a56a6300b83db69a7e58.png

    链队出队:指针q指向要跳过的结点,如下图:

    q

    17c87530e4227c699e2a74c109d56aec.png

    链队入队:将新生成的结点,next域置空,原链队的next保存新生成的结点地址,更新Q.rear指向新入队的结点即可。

    Q

    9e2a3e9a4d3193bbeee1d1a797170a23.png

    栈完整代码:

    https://github.com/xinhai2017/Data-Structures-and-Algorithms/blob/master/3.1.SqStack.cppgithub.com

    队列完整代码:

    https://github.com/xinhai2017/Data-Structures-and-Algorithms/blob/master/3.2.SqQueue.cppgithub.com
    展开全文
  • 1. 栈的定义栈的定义:限定仅在表尾进行插入和删除操作的线性表。同时因为只能在表尾进行操作,所以栈又称为后进先出的线性表。见下图,浅灰色的元素后进入栈结构...顺序栈中我们定义一个top指针,其实这里只是个游...

    1. 栈的定义

    栈的定义:限定仅在表尾进行插入和删除操作的线性表。同时因为只能在表尾进行操作,所以栈又称为后进先出的线性表。见下图,浅灰色的元素后进入栈结构,出栈的时候却是第一个出去。

    e0ff71d47cf0fa57485efadc1abb4ab9.png

    我们针对栈结构元素的插入和删除,分别叫做“Push”压栈和“Pop”弹栈。

    2. 顺序栈的插入和删除

    既然栈是线性表,而线性表包括顺序表和链表,那么同样栈也包括顺序栈和链栈。顺序栈中我们定义一个top指针,其实这里只是个游标,对应着栈顶元素的下标,比如top是0,那栈顶元素下标就是0,表示只有一个0号元素,通常规定如果top等于-1,表示空栈。见下图所示,一个有5个元素空间的顺序栈结构,当top=1时,有两个元素,top=-1时,空栈,top=4时,满栈。

    85df6ba132eecd5186ea99830ec66b53.png

    那么进栈操作就很明显,只要移动我们的top游标即可,进一个top++,而删除的时候则top--

    12ad947e3f0a8fae2dc643cb38cd06a1.png

    3. 代码实现

    那么我们就来实现下顺序栈的push和pop,以及清空栈clear

    还是先定义一下数据元素,包含一个id和一个name

    typedef struct DataElement
    {
    	int id;
    	const char* name;
    }DataElement;

    接着定义顺序栈结构,包括数组元素、top指针(游标)、数组长度

    typedef struct SeqStack
    {
    	DataElement elements[MAX_SIZE];	//栈内元素数组
    	int top;	//栈顶(数组中下标),如果为-1,表明栈是空的
    	int length;	//当前栈的元素个数
    }SeqStack;

    然后我们来实现一下压栈push操作。注意:我们插入的元素下标是要将top加加后得到的值,因为top加加后才指向新的元素空间。

    void PushSeqStack(SeqStack* seqStack, DataElement element)
    {
    	if (seqStack->top == MAX_SIZE)
    	{
    		printf("满栈,压栈失败!n");
    		return;
    	}
    	seqStack->top++;
    	seqStack->elements[seqStack->top] = element;
    	seqStack->length++;
    	return;
    }

    接着实现弹栈pop操作,同理我们需要先将top值减减。

    void PopSeqStack(SeqStack* seqStack)
    {
    	if (seqStack->top == -1)
    	{
    		printf("空栈,弹栈失败!n");
    		return;
    	}
    	seqStack->top--;
    	seqStack->length--;
    	return;
    }

    然后实现一下初始化函数,初始化数组的长度和top指针后,直接压栈即可。

    void InitSeqStack(SeqStack* seqStack, int length, DataElement* dataArray)
    {
    	seqStack->length = 0;
    	seqStack->top = -1;
    	for (int i = 0; i < length; i++)
    	{
    		PushSeqStack(seqStack, dataArray[i]);
    	}
    }

    接着实现清空栈,直接将top赋值-1,数组长度归零即可。

    void ClearSeqStack(SeqStack* seqStack)
    {
    	seqStack->length = 0;
    	seqStack->top = -1;
    }

    然后是“是否为空”函数,也很简单,只需判断top是否为-1

    int IsEmpty(SeqStack* seqStack)
    {
    	if (seqStack->top == -1)
    		return 1;
    	return 0;
    }

    最后为了测试,实现一个打印顺序栈。这和遍历数组没多大区别。

    void PrintSeqStack(SeqStack* seqStack)
    {
    	if (seqStack->top == -1)
    	{
    		printf("空栈!n");
    		return;
    	}
    	for (int i = 0; i < seqStack->length; i++)
    	{
    		printf("%dt%sn", seqStack->elements[i].id, seqStack->elements[i].name);
    	}
    }

    4. 测试代码

    接着我们测试一下,先初始化待插入的数据元素

    DataElement dataArray[] =
    {
        { 1, "娜美"},
        { 2, "罗宾"},
        { 3, "大和"},
        { 4, "汉库克"}
    };

    然后实现测试函数,这次我们动态分配顺序栈空间,然后将4个元素全部压入栈中,接着将表尾元素弹栈,最后清空栈。

    void TestSeqStack()
    {
        SeqStack* seqStack = (SeqStack*)malloc(sizeof(SeqStack)); 
        int length = sizeof(dataArray) / sizeof(dataArray[0]);
        InitSeqStack(seqStack, length, dataArray);
        printf("压栈后:n");
        PrintSeqStack(seqStack);
        PopSeqStack(seqStack);
        printf("弹栈后:n");
        PrintSeqStack(seqStack);
        ClearSeqStack(seqStack);
        printf("清空栈后:n");
        PrintSeqStack(seqStack);
        free(seqStack);
    }

    编译运行,可以看到,弹栈后4号元素“汉库克”(下标为3的元素)被删除了。清空后也是没问题。

    d56f54a23635f71cb566e3060aeb010d.png

    5. 总结

    优点:顺序栈在插入和删除时候不需要移动元素,只需移动top指针。

    缺点:顺序栈和顺序表一样,都需要预先定好数组空间,不像链表那样机动。

    展开全文
  • 源码如下: ``` #include #include #include #define STACK_INIT_SIZE 20 ...#define STACK_INCREAMENT_SIZE ...因此十分确定是访问成员top指针时出现的错误.....现在一头雾水 不知道啥情况。求大家帮忙解决一下。
  • 怎么获取c++标准库中的栈的栈顶指针?? S.top()获取的是元素而不是指针啊变为*(S.top())又显示为非法访问 要怎么办呢??在此请教大家~
  • 栈只允许在有序的线性资料集合的一端(top)进行加入数据(push)和移除数据(pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。两种栈的实现方式: 1.顺序栈(数据实现) 2.链式栈(链表实现)1.顺序栈...

    61b69c3c105f34fef477bfaf73b91235.png

    栈只允许在有序的线性资料集合的一端(top)进行加入数据(push)和移除数据(pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。

    两种栈的实现方式: 1.顺序栈(数据实现) 2.链式栈(链表实现)

    1.顺序栈(数组实现栈)

    6572b181ca12a9b23b67b97de0e6b305.png
    顺序栈结构

    顺序栈的实现

    0.准备工作

    #define OK 1
    

    1.构建空栈

    // 构建一个空栈S
    

    2.将栈置空

    // 将栈置空
    

    3.判断顺序栈是否为空

    // 判断顺序栈是否为空;
    

    4.返回栈的长度

    // 返回栈的长度
    

    5.获取栈顶元素

    // 获取栈顶
    

    6. push元素e为新栈顶元素

    // 插入元素e为新栈顶元素
    

    7. pop S栈顶元素,并且用e带回

    // popS栈顶元素,并且用e带回
    

    8. 从栈底到栈顶依次对栈中的每个元素打印

    // 从栈底到栈顶依次对栈中的每个元素打印
    

    9.使用栈并打印

    // 使用栈
    

    打印出来的结果

    ba02be9be7cabb257b7d7af3c707ca8d.png
    打印的结果

    2.链式栈

    0.结构

    e33809dab2ddfd5225f802560d3b7ab2.png
    链式结构栈

    1.入栈(push)

    336f3570be18f4ba84e83a0a60de2b34.png
    入栈操作
    • 第0步:创建节点node
    • 第1步: 把创建的node的next指向栈顶top
    • 第2步:把top指向创建的node

    2.出栈(pop)

    8486e14a1101b345bc42cb8b8b24e0c7.png
    • 第1步: 记录需要弹出的节点P
    • 第2步: 把top指向top的next节点
    • 第3步: 释放节点P

    链式栈的实现

    0.准备工作

    #define OK 1
    

    1.构造一个空栈S

    // 构造一个空栈S
    

    2.把链栈S置为空栈

    Status 

    3. 检测空栈

    // 若栈S为空栈,则返回TRUE, 否则返回FALSE
    

    4.栈的长度

    // 返回S的元素个数,即栈的长度
    

    5. 获取栈顶元素

    // 若链栈S不为空,则用e返回栈顶元素,并返回OK ,否则返回ERROR
    

    6. 入栈(Push)

    // 插入元素e到链栈S (成为栈顶新元素)
    

    7. 出栈(Pop)

    // 若栈不为空,则删除S的栈顶元素,用e返回其值. 并返回OK,否则返回ERROR
    

    8.遍历链栈

    // 遍历链栈,其实就是遍历链表
    

    9.使用和打印

    int 

    打印的结果:

    39129a4b91ea5ef551ccca4e496bcc6f.png
    打印的结果
    展开全文
  • 数据结构-栈 更简单的介绍,在《程序是怎样跑起来的》一书中有简要形象的说明 一.栈的基本概念 栈是一种特殊的...主要步骤如下: 判断链栈是否为空,若空则返回null 修改top指针域的值,返回被删节点的数据域的值 def

    数据结构-栈

    更简单的介绍,在《程序是怎样跑起来的》一书中有简要形象的说明

    一.栈的基本概念

    栈是一种特殊的线性表,其插入删除操作都只能在表的尾部进行。

    栈中允许插入、删除操作的一端称为栈顶,另一端称为栈底。

    通常栈的插入操作叫入栈,栈的删除操作叫做出栈。

    栈的插入和删除操作只允许在栈顶进行,每次入栈的元素即成为栈顶元素,每次最先出栈的总是栈顶元素,所以栈是一种后进先出的线性表。

    f89661a696cfd6a8701bd331e5faaf8b.png

    二.顺序栈

    1.介绍

    顺序栈是用数组实现的,因为入栈和出栈操作都是在栈顶进行的,所以增加变量top来指示栈顶元素的位置,top指向栈顶元素存储位置的下一个存储单元的位置,空栈时top=0。

    2.基本操作

    1)入栈操作

    入栈操作push(x)是将数据元素x作为栈顶元素插入顺序栈中,主要操作如下:

    1. 判断顺序栈是否为满,若满则抛出异常
    2. 将x存入top所指的存储单元位置
    3. top加1
    def 

    2)出栈操作

    出栈操作pop()是将栈顶元素从栈中删除并返回,主要步骤如下:

    1. 判断顺序栈是否为空,若空则返回null
    2. top减1
    3. 返回top所指的栈顶元素的值
    def 

    fc947682ff410051f8f444d54cdea7cf.png

    3.应用

    利用顺序栈实现括号匹配:

    def 

    三.链栈

    1.介绍

    采用链式存储结构的栈称为链栈,由于入栈和出栈只能在栈顶进行,不存在在栈的任意位置进行插入和删除操作,所以不需要设置头节点,只需要将指针top指向栈顶元素节点。

    f6adeddcac9ade5c3d7a47108119a290.gif

    2.基本操作

    1)入栈操作

    入栈操作push(x)是将数据域为x的节点插入到链栈的栈顶,主要步骤如下:

    1. 构造数据值域为x的新节点
    2. 改变新节点和首节点的指针域,使新节点成为新的栈顶节点
    def 

    451cb2a023d332d0824036a995677bd0.png

    2)出栈操作

    出栈操作pop()是将栈顶元素从链栈中删除并返回其数据域的值,主要步骤如下:

    1. 判断链栈是否为空,若空则返回null
    2. 修改top指针域的值,返回被删节点的数据域的值
    def 

    053329731d14ca33073d9668e9d4158b.png
    展开全文
  • 关于内存的分类这里只是大致说明一下,关于内存更详细的内容可查看往期笔记: 【C语言笔记】内存笔记 例子:return返回指向栈内存指针 先看一个return返回指向栈内存指针的例子: #include ​ char *GetStr(void) {...
  • 栈(stack)是线性表的一个具体形式,其定义是一个后进先出...存储结构base:指向栈底的指针top:指向栈顶的指针stackSize:当前可使用的最大容量代码实现栈class 这是网上常见的python中栈的写法,但是我觉得有些取...
  • 我们定义top指针(这里的指针并非实际意义上的指针,只是一种称呼)用来记录栈顶元素在数组中的位置,若栈的长度为MAXSIZE,那么栈顶位置top必须小于MAXSIZE,当栈存在一个元素时,top等于0,若为空栈,则top等于-1。...
  • ② 置TOP=TOP+1(栈指针加1,指向进栈地址); ③ S(TOP)=X,结束(X为新进栈的元素); 退栈(POP)算法: ① 若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈, 空则下溢;不空则作②); ② X=S(TOP),...
  • (3)栈顶指针下移 top = top -> next; (4)释放存储空间 free(p); 代码实现: void StackPop(linklist top) { linklist p; if(top == NULL) { printf("Stack is empty."); } else { p = top; top = top -> next; ...
  • 在栈中进行插入和删除操作的一端称为栈顶(Top)。另一端被称为栈底(bottom)。不包含任何元素的栈称为空栈。1.1.1 栈的运算1.2 栈的存储结构1.2.1 栈的顺序存储栈的顺序存储是指用一组地址连续的存储单元依次存储...
  • 初始化链栈,为 top 指针申请一节点,申请之后却不用,而将 top 指针指向NULL??求大神指教这个申请节点的操作的作用何在? 代码如下: typedef int Status; typedef int SElemType; /* SElemType类型根据实际...
  • “栈”就可以解决这些问题,函数调用的时候,将参数和变量都压到一个栈中,这样避免产生太多的空间占用,也可以利用栈指针的偏移来完成存取,只要对应的函数栈指针是不同的,就不会发生冲突。 小结 关于“栈”的...
  • 栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中...
  • (三)顺序栈 base指针指向空间起始地址,top指针指向下一个元素进栈的位置。 判断空栈的标志:base == top . 问:为什么top不指向当前栈顶元素?答:这样就无法分辨空栈和有一个元素的栈了。 (1)顺序栈的初始化...
  • 数据结构中栈是一种受限的线性表,是一种先入后出的数据结构,大家重点掌握顺序栈的特点。 主要的重点冷月做出了标识,...栈顶(Top):允许插入或删除的那一端 栈底(Bottom):固定的,不允许插入或删除的那一端 物理结...
  • 10.1 栈和队列栈和队列都是动态集合, 栈(stack)是后进先出, 队列(queue)是先进先出;栈栈就相当于垒盘子, ... 该数组有一个属性S.top, 指向最新插入的元素, 栈中包含的元素为S[1..S.top], 其中S[1]是栈底元素, S[S...
  • if((*S).top-(*S).base>=(*S).stacksize) /* 栈满,追加存储空间 */ { (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW)...
  • 栈的基本操作—入栈(压栈) 入栈的基本顺序可以用以下图所示: 入栈(push)操作时,我们只需要找到top所指向的空间,创建一个新的结点,将新的结点的next指针指向top指针指向的空间,再将top指针转移,并且指向新的...
  • 理解静态栈中的top指针 对于顺序静态栈定义代码: typedef struct Stack { int s[10]; int top; } stack; 在C语言数据结构教材中常提到 : top指针,但是在top指针里面存放的是一个整型数据,需要注意的是,此指针而...
  • 指针引用和二级指针

    2013-10-07 09:20:15
    top指针可以用指针的引用,也可以用二级指针,都能达到修改top指针的指向的目的。 指针引用:引用就是别名,两个本质上一样,所以直接操作top指针。 二级指针:主函数中需要传一级指针的地址进入子函数...
  • /*栈的动态分配顺序存储初始化,且top指针指向栈顶元素 */ Status InitStack(SqStack *S) { S->base=(Elemtype*)malloc(sizeof(Elemtype)*INIT_SIZE); if(!S->base) { return ERROR; } S->top = S->base-1; ...
  • 栈--进栈,出栈指针修改的顺序问题

    千次阅读 2016-10-02 13:50:22
    策略设计一个顺序栈,附设的top指针有两种策略: 指向当前栈顶元素 指向栈顶上方空位 借助一篇文章深入分析二者的异同。top指向栈顶首先令top指向当前栈顶元素,这样进来一个新的元素时,新元素不能占据当前top指向...
  • 入栈时,top指针是 s.top++=e 还是s.++top=e? 出栈时,top指针是 s.top--=e 还是s.--top=e? 还有就是 top指针是指向栈顶元素or栈顶元素下一位置?
  • C++11智能指针的常见误区 Top10

    千次阅读 2017-05-13 16:41:48
    本文主要讲解了智能指针作为一把双刃剑,我们在使用它时需要特别注意避免的一些“雷区”,以及背后的原理。
  • !...[图片说明](https://img-ask.csdn.net/upload/201504/22/1429708158_525879.png)以上为链栈程序(无错),但为什么不能将...如果直接用struct node 定义一个top指针那么入栈部分将出错,为何?或者说这两者区别在哪?
  • 思路:将节点信息保存在哈希map中,然后复制链表的next和random指针。 class Solution { public: Node* copyRandomList(Node* head) { if (head == nullptr) { return head; } Node *cur = head; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,639
精华内容 1,055
关键字:

top指针