精华内容
下载资源
问答
  • 1、栈是什么 首先线性表是使用非常广泛的一类数据结构,它对数据的顺序非常敏感,而且它对数据的增删操作非常灵活。 栈是一种特殊的线性表。栈与线性表的不同,体现在增和删的操作。具体而言,栈的数据结点必须后进...

    1、栈是什么

    首先线性表是使用非常广泛的一类数据结构,它对数据的顺序非常敏感,而且它对数据的增删操作非常灵活。
    是一种特殊的线性表。栈与线性表的不同,体现在增和删的操作。具体而言,栈的数据结点必须后进先出

    宏观上来看,与数组或链表相比,栈的操作更为受限,那为什么我们要用这种受限的栈呢?其实,单纯从功能上讲,数组或者链表可以替代栈。然而问题是,数组或者链表的操作过于灵活,这意味着,它们过多暴露了可操作的接口。这些没有意义的接口过多,当数据量很大的时候就会出现一些隐藏的风险。一旦发生代码 bug 或者受到攻击,就会给系统带来不可预知的风险。虽然栈限定降低了操作的灵活性,但这也使得栈在处理只涉及一端新增和删除数据的问题时效率更高。

    举个实际的例子,浏览器都有页面前进和后退功能,这就是个很典型的后进先出的场景。假设你先后访问了五个页面,分别标记为 1、2、3、4、5。当前你在页面 5,如果执行两次后退,则退回到了页面 3,如果再执行一次前进,则到了页面 4。处理这里的页面链接存储问题,栈就应该是我们首选的数据结构。

    栈既然是线性表,那么它也包含了表头表尾。不过在栈结构中,由于其操作的特殊性,会对表头和表尾的名字进行改造。表尾用来输入数据,通常也叫作栈顶(top);相应地,表头就是栈底(bottom)。栈顶和栈底是用来表示这个栈的两个指针。跟线性表一样,栈也有顺序表示和链式表示,分别称作顺序栈和链栈。

    2、栈的基本操作

    栈对于数据有增、删、查处理。对于栈的新增操作,通常也叫作 push 或压栈。对于栈的删除操作,通常也叫作 pop 或出栈。栈分为顺序栈和链栈。
    线性栈:
    栈的顺序存储可以借助数组来实现。一般来说,会把数组的首元素存在栈底,最后一个元素放在栈顶。然后定义一个 top 指针来指示栈顶元素在数组中的位置。假设栈中只有一个数据元素,则 top = 0。一般以 top 是否为 -1 来判定是否为空栈。当定义了栈的最大容量为 StackSize 时,则栈顶 top 必须小于 StackSize。

    当需要新增数据元素,即入栈操作时,就需要将新插入元素放在栈顶,并将栈顶指针增加 1。如下图所示:
    在这里插入图片描述
    删除数据元素,即出栈操作,只需要 top - 1 就可以了。

    对于查找操作,栈没有额外的改变,跟线性表一样,它也需要遍历整个栈来完成基于某些条件的数值查找。

    链栈:
    关于链式栈,就是用链表的方式对栈的表示。通常,可以把栈顶放在单链表的头部,如下图所示。由于链栈的后进先出,原来的头指针就显得毫无作用了。因此,对于链栈来说,是不需要头指针的。相反,它需要增加指向栈顶的 top 指针,这是压栈和出栈操作的重要支持。
    在这里插入图片描述
    对于链栈,新增数据的压栈操作,与链表最后插入的新数据基本相同。需要额外处理的,就是栈的 top 指针。如下图所示,插入新的数据,则需要让新的结点指向原栈顶,即 top 指针指向的对象,再让 top 指针指向新的结点。
    在这里插入图片描述
    在链式栈中进行删除操作时,只能在栈顶进行操作。因此,将栈顶的 top 指针指向栈顶元素的 next 指针即可完成删除。对于链式栈来说,新增删除数据元素没有任何循环操作,其时间复杂度均为 O(1)。

    对于查找操作,相对链表而言,链栈没有额外的改变,它也需要遍历整个栈来完成基于某些条件的数值查找。

    展开全文
  • 限制后的线性表--

    2020-12-31 17:24:28
    栈是什么 栈是一种特殊的线性表。栈的数据结点必须后进先出。 栈既然是线性表,那么它也包含了表头和表尾。不过在栈结构中,由于其操作的特殊性,会对表头和表尾的名字进行改造。表尾用来输入数据,通常也叫作栈顶...

    拉钩公瑾数据结构和算法课程笔记
    栈是什么
    栈是一种特殊的线性表。栈的数据结点必须后进先出。

    栈既然是线性表,那么它也包含了表头和表尾。不过在栈结构中,由于其操作的特殊性,会对表头和表尾的名字进行改造。表尾用来输入数据,通常也叫作栈顶(top);相应地,表头就是栈底(bottom)。栈顶和栈底是用来表示这个栈的两个指针。跟线性表一样,栈也有顺序表示和链式表示,分别称作顺序栈和链栈。

    1. 栈的基本操作
    • 顺序栈

    在这里插入图片描述

    • 链栈
      在这里插入图片描述
    1. 栈的案例
    • 例 1,给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。有效字符串需满足:左括号必须与相同类型的右括号匹配,左括号必须以正确的顺序匹配。例如,{ [ ( ) ( ) ] } 是合法的,而 { ( [ ) ] } 是非法的。

    • 例 2,浏览器的页面访问都包含了后退和前进功能,利用栈如何实现?

    为了支持前进、后退的功能,利用栈来记录用户历史访问网页的顺序信息是一个不错的选择。此时需要维护两个栈,分别用来支持后退和前进。

    在这里插入图片描述
    3. 总结
    好的,这节课的内容就到这里了。这一节的内容主要围绕栈的原理、栈对于数据的增删查操作展开。

    栈继承了线性表的优点与不足,是个限制版的线性表。限制的功能是,只允许数据从栈顶进出,这也就是栈后进先出的性质。不管是顺序栈还是链式栈,它们对于数据的新增操作和删除操作的时间复杂度都是 O(1)。而在查找操作中,栈和线性表一样只能通过全局遍历的方式进行,也就是需要 O(n) 的时间复杂度。

    栈具有后进先出的特性,当你面对的问题需要高频使用新增、删除操作,且新增和删除操作的数据执行顺序具备后来居上的相反关系时,栈就是个不错的选择。例如,浏览器的前进和后退,括号匹配等问题。栈在代码的编写中有着很广泛的应用,例如,大多数程序运行环境都有的子程序的调用,函数的递归调用等。这些问题都具有后进先出的特性。关于递归,我们会在后续的课程单独进行分析。

    展开全文
  • 什么是线性表

    千次阅读 2011-11-14 13:49:47
    简介  线性表是最基本、最简单、也最常用一种数据结构。线性表中数据元素之间关系一对一关系,即... 线性表是一种常用数据结构,以下介绍线性表及其顺序存储,并对和队列及它们顺序实现给出了详细

    简介

            线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

    结构

      线性表是一种常用的数据结构,以下介绍线性表及其顺序存储,并对栈和队列及它们的顺序实现给出了详细的设计描述。   在实际应用中,线性表都是以、队列、字符串数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性,因此,掌握这些特殊线性表的特性,对于数据运算的可靠性和提高操作效率都是至关重要的。  线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。一般地,一个线性表可以表示成一个线性序列:k1,k2,…,kn,其中k1是开始结点,kn是终端结点。   是一个数据元素的有序(次序)集

    特征

      线性结构的基本特征为:  

    1.集合中必存在唯一的一个“第一元素”;  

    2.集合中必存在唯一的一个 “最后元素” ;  

    3.除最后一个元素之外,均有 唯一的后继(后件);  

    4.除第一个元素之外,均有 唯一的前驱(前件)。  

    由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。  数据元素的个数n定义为表的长度。  当n=0时称为空表。  常常将非空的线性表(n>0)记作:  (a1,a2,…an)   数据元素ai(1≦i≦n)只是一个抽象的符号,其具体含义在不同的情况下可以不同。  

    线性表的基本操作  

    1)MakeEmpty(L) 这是一个将L变为空表的方法  

    2)Length(L) 返回表L的长度,即表中元素个数  

    3)Get(L,i) 这是一个函数,函数值为L中位置i处的元素(1≤i≤n)  

    4)Prev(L,i) 取i的前趋元素  

    5)Next(L,i) 取i的后继元素  

    6)Locate(L,x) 这是一个函数,函数值为元素x在L中的位置  

    7)Insert(L,i,x)在表L的位置i处插入元素x,将原占据位置i的元素及后面的元素都向后推一个位置  

    8)Delete(L,p) 从表L中删除位置p处的元素  

    9)IsEmpty(L) 如果表L为空表(长度为0)则返回true,否则返回false  

    10)Clear(L)清除所有元素  

    11)Init(L)同第一个,初始化线性表为空  

    12)Traverse(L)遍历输出所有元素  

    13)Find(L,x)查找并返回元素  

    14)Update(L,x)修改元素  

    15)Sort(L)对所有元素重新按给定的条件排序

    结构特点

      线性表具有如下的结构特点:  1.均匀性:虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。  2.有序性:各数据元素在线性表中的位置只取决于它们的序与,数据元素之前的相对位置是线性的,即存在唯一的“第一个“和“最后一个“的数据元素,除了第一个和最后一个外,其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素(直接后继)。  在实现线性表数据元素的存储方面,一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍,本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈.队列和串也是线性表的特殊情况,又称为受限的线性结构。   


    附一道选择题:  

    下列哪个不是线性表(d)  

    A. 链表 B. 队列 C.栈 D.关联数组


    展开全文
  • 线性表

    2019-09-02 10:31:23
    目录 1.什么是栈 2.栈的存储结构 顺序存储结构(本节所展示的方式) ... 栈是限定在表尾进行插入和删除操作的线性表 2.栈的存储结构 顺序存储结构(本节所展示的方式) 链式存储结构 3.栈的应用 递...

    目录

    1.什么是栈

    2.栈的存储结构

       顺序存储结构(本节所展示的方式)

       链式存储结构

    3.栈的应用

       递归

       四则运算表达式

    4.入栈操作

    5.出栈操作

    6.打印栈的内容

    7.主函数



    1.什么是栈

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

    2.栈的存储结构

       顺序存储结构(本节所展示的方式)

       链式存储结构

    3.栈的应用

       递归

        递归是一种选择结构;递归调用会创建函数的副本,耗费大量的内存和时间;迭代使用循环结构,不需要占用额外的内存。

       四则运算表达式

    4.入栈操作

    Stacks* pushin(Stacks* p,int e)
    {
    	if(p->top==(M-1))
    	{
    		printf("the stack is full\n");
    	}
    	p->top++;
    	p->data[p->top] = e;
    	return p;
      } 

    5.出栈操作

    Stacks* popout(Stacks* p)
    {
    	if(p->top==(-1))
    	{
    		printf("the stack is empty!\n");
    		return 0;
    	}
    	p->top--;
    	return p;
     }

    6.打印栈的内容

    int printstack(Stacks p)
    {
    	if(p.top==(-1))
    	{
    		printf("the stack is empty!\n");
    		return 0;
    	}
    	while(p.top!=(-1))
    	{
    		printf("%d %d\n",p.data[p.top],p.top);
    	    p.top--;
    	}
    	return 0;
     }

    7.主函数

     

    //栈的顺序存储 
    #include "stdio.h"
    #include "stdlib.h" 
    #define M 5
    typedef struct{
    	int data[M];
    	int top;
    }Stacks;
    
    int main()
    {
    	Stacks p;
    	Stacks *q;
    	p.top = -1;
    	q = &p;
    	printstack(p);
        q = pushin(q,13);
        q = pushin(q,14);
        q = pushin(q,15);
        q = pushin(q,16);
        printstack(p);
        q = popout(q);
        printstack(p);
        return 0;
        
    }

     

    展开全文
  • 和队列都线性表,都限制了插入删除点的线性表(或者说控制了访问点的线性表)  共同点:都只能在线性表的端点插入和删除  不同点:的插入和删除都在线性表的同一个端点,该点通称栈顶,相应地,不能...
  • 什么和队列运算受限制的线性表呢,就是因为这俩哥们和普通的线性表不太一样。那么具体不一致的点在哪呢? 我们都知道不管顺序表还是链表都可以在其任意位置进行插入和删除操作的(前提在其索引范围内)...
  • 栈是限定仅在表位进行插入和删除操作的线性表 允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。 栈是一种先进后出的线性表(Last IN First Out),简称LIFO结构。 ...
  • 栈:后进先出的线性表如何实现增删查1)栈是什么?2)栈的基本操作 线性表是使用非常广泛的一类数据结构,它对数据的顺序非常敏感,而且它对数据的增删操作非常灵活。在有序排列的数据中,可以灵活的执行增删操作,...
  • 队列线性表线性链表树Here you will learn about linear queue in C++. 在这里,您将了解C ++中线性队列。 What is Queue? 什么是队列? The queue is a linear data structure where operations ...
  • 1. 什么是栈(stack)限定仅在表尾进行插入和删除操作的线性表。 2. 的特点: 1.) 又称为后进先出(Last In First out)的线性表元素具有线性关系,即前驱后继关系。 2.) 的...
  • 特殊线性表--

    2019-01-12 21:08:57
     栈是一种特殊的线性表,限定值能在表的一端进行插入和删除操作,俗称“后进先出”(FILO)。  操作数据的这段是表头,称为栈顶;相应的,表尾称为栈底。不含任何元素的栈称为空栈。 栈的基本操作: push:压栈...
  • 数据结构是什么? 数据结构存储结构: 线性表 树存储结构 图存储结构 一、基本概念 2、算法基本概念 二、线性表 三、和队列 四、树、二叉树 五、图 六、查找 七、排序 数据结构是什么? 我认为...
  • 一、什么是线性表 线性表是指零个或多个数据元素有限序列,首先线性表是一个序列,除了第一个元素没有前排元素(前驱)、最后一个元素没有后排元素(后继),其他元素每一个都有自己前驱以及后继。 顺序存储...
  • 今天我们来看看 (stack) 这个玩意是什么东东。 一 什么是 就是一种专有名词,没什么高大上也是线性表的一种,就同顺序表,链表都是线性表一样。但既然都是顺序表,为啥,分那么多名称呢?我就打个比喻,...
  • 线性表、队列

    2021-05-14 22:30:17
    什么是数据结构? 解决问题方法效率,跟数据组织方式有关 解决问题方法效率,跟空间利用效率有关 解决问题方法效率,跟算法巧妙程度有关 什么是算法? 一个有限指令集 接受一些输入(有情况不需要...
  • 受限线性表--

    2021-06-17 15:14:34
    一、pandas是什么? 示例:pandas 是基于NumPy 一种工具,该工具是为了解决数据分析任务而创建。 二、使用步骤 1.引入库 代码如下(示例): import numpy as np import pandas as pd import matplotl...
  • ,stack,限定在表的一端进行插入和删除预算的线性表  通常,将删除与插入的一端称为栈顶,每次退(即删除一个元素)的必最后一个进栈的元素,而第一个进栈的元素必然最后一个退的。即在中,元素具有...
  • 线性表、链表、、队列关系

    千次阅读 2017-05-16 09:14:31
    而对于第二个难题,数据结构与算法基本上每一个程序员都需要了解,因为,算法解答一个问题基本逻辑,如果你可以证明这个逻辑正确,那接下来问题就是应该采用什么数据结构来保证你程序能有最高执行...
  • 线性表是最基本、最简单、也最常用一种数据结构。一个线性表是n个具有相同特性数据元素有限序列。 线性表分为:顺序表,链表,,队列。 属于线性表的一种,具有先进后出,后进先出特点,底层可以由...
  • 线性表应用-educoder

    2020-10-08 22:00:21
    在cpp中存储个大问题,没有new,函数在跑完后就释放了所有其产生内存,导致在函数里加上去新栈顶也被清除,最后什么都没有发生,sk还变成了一个野指针—来自educoder评论 //为p分配内存空间很重要 intStack p=...
  • 栈是什么?

    2020-08-22 20:16:17
    栈是什么? 栈又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶...
  • (Stack)限定在仅在表尾插入的线性表。 因此对于来说,表尾具有特殊的含义。我们把表尾称作栈顶(top),把表头称作底(bottom)。不含元素的称为空栈。 想象一下进栈的顺序: 1.a1进,进到底 2.a2进...
  •   思考,如果要让你实现一个类似ArrayList的线性表,需要注意什么? 底层数据结构肯定采用Object[]数组,由于顺序存储结构,还可以定义一个length变量作为顺序线性表的长度值 该顺序存储结构的类需要使用...
  • 栈是一种’操作受限’的线性表,只允许在一端插入和删除数据,并且满足后进先出,先进后出的特性。 实际上,栈既可以用数组来实现,也可以用链表来实现,分别叫做顺序栈和链式栈。 一、如何用数组来实现一个栈 ? /*...
  • 线性表

    2009-10-14 22:25:00
    在开始本章节之前,我要说明两个问题:1 线性表的一个误解很多人认为,并且严老师书上也这么划分,就是将线性表,队列划分开来。其实并不这么回事,我们可以参考《计算机程序设计艺术》第一卷,第二章。...
  • 03_线性表应用一:

    2018-01-21 01:35:00
    一、什么是栈 一种“先进后出”数据结构;类似一个箱子, 先放进去后拿出来 栈的分类: 1.静态 : 以数组为内核 2.动态 : 以链表为内核 栈的算法: 出栈、压栈 二、栈的顺序存储 三、栈的链式...
  • 很多人想知道算法如何设计和分析的?那么在阅读和设计算法之前,学习和了解数据结构的设计和逻辑思维对...算法设计分析基础:数据结构中的线性表、队列、串; 数据结构设计中的主流的线性存储和链式存储方式。 ...
  • 队列和栈是什么,列出它们的区别? 1.队列(Queue):是限定只能在表的一端进行插入和在另一端进行删除操作的线性表 2.栈(Stack):是限定只能在表的一端进行插入和删除操作的线性表 3.队列先进先出(FIFO),栈先进后...

空空如也

空空如也

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

栈是什么的线性表