精华内容
下载资源
问答
  • (stack)是一种运算受限线性表。其受限是指进行插入和删除操作仅仅发生在该线性表尾部。

    栈(stack)是一种运算受限的线性表。其受限是指进行插入和删除操作仅仅发生在该线性表的尾部。


    Table of Contents

    线性栈

    动态线性栈

    链式栈


    线性栈

    栈的定义:

    1. 是一种只能在一端(一般是尾部)进行插入和删除操作的特殊线性表。
    2. 按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶;需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
    3. 栈也称为后进先出(List In First Out)的线性表,简称LIFO结构
    4. 它是一个线性表,也即,栈元素具有线性关系,即前驱后继关系
    5. 只不过它是一种特殊的线性表而已,进行插入和删除操作的只能在称为栈顶(top)的一端进行。另一端为栈底(bottom)。

    什么是线性栈:

    1. 用一组地址连续的存储单元(即数组)依次存放栈底到栈顶的数据元素,栈底位置固定不变,栈顶位置随着入栈和出栈操作而变化。
    2. 线性栈的理解:立起来的数组,操作都在数组的最后元素位进行

    线性栈的代码定义

    #define MAXSIZE 100
    typedef struct
    {
    	int data[MAXSIZE];
    	int top;
    }SeqStack;
    

    特性:

    1. 栈中元素个数为零时称为栈。
    2. 栈的插入操作,一般称为进栈(PUSH),也称压栈、入栈。删除则称为出栈(POP),也称弹栈。

    1. 它的特殊之处在于限制了这个线性表的插入和删除的位置,它始终只在栈顶进行。这也就使得:栈底是固定的,最先进栈的只能在栈底。
    2. 例如,递归时需要用到栈来记录断点;在浏览器的前进后退页也是利用栈来存储读取每个网页信息。

    第一个线性栈

    第一个线性栈
    #include <stdio.h>
    #define MAX 100
    
    typedef struct
    {
    	int data[MAX];
    	int top;
    }stack;
    
    int main()
    {
    	stack MyStack;
    
    	//初始化栈
    	MyStack.data[MAX] = 0;
    	MyStack.top = -1;
    
    	//进栈操作
    	MyStack.data[++MyStack.top] = 100;  //栈顶指针往上移
    	MyStack.data[++MyStack.top] = 200;
    
    	//取数据
    	printf("栈顶元素为:%d\n", MyStack.data[MyStack.top]);
    
    	//出栈操作
    	MyStack.top--;
    	printf("栈顶元素为:%d\n", MyStack.data[MyStack.top]);
    
    	return 0;
    }
    

    动态线性栈

    为什么要引入动态线性栈?

    1. 在C语言中的数组要求在编译时必须确定数组的大小。
    2. 在利用数组做为线性栈的实现时,也会遇到数组容量不可以动态拓展的问题。
    3. 可以利用动态分配内存解决这个问题,即动态一维数组。

    什么是动态线性栈?

    1. 动态的一维数组 + 栈的思想
    2. 动态申请一块内存,将栈中元素放入其中。当元素个数超过设定的最大长度时,可以在再动态申请更大的内存来存放元素。
    3. 通过动态内存申请返回的指针来以数组的形式访问栈中元素。

    如何实现动态线性栈?

    • 使用malloc函数申请内存,使用realloc函数扩大内存;

    第一个动态线性栈

    #include <stdio.h>
    #include  <stdlib.h>
    #include  <assert.h>
    
    typedef struct
    {
    	int* data;
    	int top;
    }stack;
    
    int main()
    {
    	int size = 5;
    	stack* MyStack = (stack*)malloc(sizeof(stack)); //为结构体分配内存
    	assert(MyStack);
    	
    	//初始化
    	MyStack->data = (int*)malloc(sizeof(int) * size); //为动态线性栈分配内存
    	assert(MyStack->data != NULL);
    	MyStack->top = -1;
    
    	//压栈
    	MyStack->data[++MyStack->top] = 100;
    	MyStack->data[++MyStack->top] = 200;
    	MyStack->data[++MyStack->top] = 300;
    
    	//出栈
    	MyStack->top--;
    	printf("栈顶元素为:%d\n", MyStack->data[MyStack->top]);
    
    	//重新分配大小
    	size *= 2;
    	MyStack->data = (int*)realloc(MyStack->data, size); //重新分配内存
    	assert(MyStack->data != NULL); //注意,这将可能会导致原始的MyStack->data块内存泄露;这里仅作为演示,实际开发时慎用!
    
    	MyStack->data[++MyStack->top] = 400;
    	printf("栈顶元素为:%d\n", MyStack->data[MyStack->top]);
    	return 0;
    }
    


    链式栈

    什么是链式栈:

    1. 链式栈 = 单链表 + 栈的思想
    2. 链式栈的本质:倒立竖着的单链表
    3. 每次入栈一个元素,向链表中添加一个节点(相当于头插法),出栈一个元素,释放一个节点。

    链式栈的本质就是一个“竖着”的链表!

    特性:

    1. 利用单链表的头插法,可以避免每次在链表的尾部进行插入和删除,就要遍历整个链表来找到尾节点
    2. 在头部进行插入和删除时,只需根据头指针即可找到链表的首元素结点。而无需遍历链表。所以链式栈的出,入栈通过对链表进行头删和头插来实现。
    3. 单链表中常用的的头结点也就失去了意义,不再需要头结点的。

    链式栈的代码定义

    typedef struct node
    {
    	int data;
    	struct node* next;
    }StackNode;
    

    第一个链式栈

    #include <stdio.h>
    #include  <stdlib.h>
    #include  <assert.h>
    
    typedef struct node
    {
    	int data;
    	struct node* next;
    }stack;
    
    int main()
    {
    	stack* top = NULL; //设置一个栈顶指针,方便出栈、取栈操作
    	stack* bottom = (stack*)malloc(sizeof(stack));
    	assert(bottom != NULL);
    	bottom->data = 100;
    	bottom->next = NULL;
    	top = bottom;
    
    	stack* NodeAa = (stack*)malloc(sizeof(stack));
    	assert(NodeAa != NULL);
    	NodeAa->data = 200;
    	NodeAa->next = bottom; //插入到bottom节点的前面,即头插法
    	top = NodeAa;
    
    	stack* NodeBb = (stack*)malloc(sizeof(stack));
    	assert(NodeBb != NULL);
    	NodeBb->data = 300;
    	NodeBb->next = NodeAa;
    	top = NodeBb;
    
    	printf("栈顶元素:%d\n", top->data);
    
    	//出栈
    	stack* t = top;
    	top = top->next;
    	free(t);
    	printf("栈顶元素:%d\n", top->data);
    	return 0;
    }
    

    展开全文
  • Werkzeug 通过自定义 werkzeug.local.Local 类实现线程隔离的结构, 封装了push, pop, 和top方法.可以将对象推入、弹出,也可以快速拿到栈顶对象....是一种先进后出的基本数据结构. from werkzeug.local imp...

    原文 
     
    Werkzeug 通过自定义 werkzeug.local.Local 类实现线程隔离的栈结构, 封装了push, pop, 和top方法.可以将对象推入、弹出,也可以快速拿到栈顶对象. 同样具有线程隔离的作用. 并没有直接使用threading.Local .

    1. LocalStack作为栈结构的特性

    栈是一种先进后出的基本数据结构.

    from werkzeug.local import LocalStack
    s = LocalStack()
    s.push(1)
    print(s.top)
    print(s.top)  # 获取栈顶元素
    print(s.pop())  # 弹出栈顶元素
    print(s.top)  # 弹出的栈顶元素会删除
    
    s.push(1)
    s.push(2)
    print(s.top) 
    print(s.top)
    print(s.pop())
    print(s.pop())
    
    1. 作为线程隔离的特性

    线程隔离的作用是: 使当前对象可以正确的使用自己创建的对象, 而不会使用和破坏其他进程的对象.

    my_stack = LocalStack()
    my_stack.push(2)
    print('in main thread after push , value is ', my_stack.top)  
    
    def my_work():
        print('in new thread before, value is ', my_stack.top)
        my_stack.push(3)
        print('after new thread after push, value is ', my_stack.top)
    new_thread = threading.Thread(target=my_work, name='my_work_thread')
    new_thread.start()
    time.sleep(1)
    print('finally, in new thread , value is', my_stack.top)

    打印结果为:

    in main thread after push , value is  2
    in new thread before, value is  None
    after new thread after push, value is  3
    finally, in new thread , value is 2

    源代码

    class Local(object):
        __slots__ = ('__storage__', '__ident_func__')
    
        def __init__(self):
            object.__setattr__(self, '__storage__', {})
            object.__setattr__(self, '__ident_func__', get_ident)
        ...
         def __setattr__(self, name, value):
            ident = self.__ident_func__()
            storage = self.__storage__
            try:
                storage[ident][name] = value
            except KeyError:
                storage[ident] = {name: value}

    __slots__限制了Local类只可以有两个属性:__storage__和__ident_func__。从构造函,__storage__是一个字典,而__ident_func__是一个函数,用来识别当前线程或协程.

    展开全文
  • 栈的基本操作

    2012-07-02 17:15:02
    掌握栈的顺序存储结构和操作特性,实现基于顺序栈的基本操作。
  • 栈的基本实现

    2016-07-19 23:45:57
     栈的基本操作受到限制,体现为它对数据元素的操作顺序,栈的数据元素具有后进先出的特性。  栈的基本操作包括入栈和出栈,栈的顶部和尾部分别用栈顶和栈底标注,如果一个栈是空栈,那么它的的栈顶等于栈底,...

            栈从逻辑结构上说,属于线性结构的范畴,但和线性表不同的是,栈所支持的基本操作是受到限制的,因此栈是一种限定性的数据结构。

            栈的基本操作受到限制,体现为它对数据元素的操作顺序,栈的数据元素具有后进先出的特性。

            栈的基本操作包括入栈和出栈,栈的顶部和尾部分别用栈顶和栈底标注,如果一个栈是空栈,那么它的的栈顶等于栈底,一般情况下,栈底总是等于-1,栈顶等于元素个数-1

            栈的顺序存储实现

            这个很简单,就是一个数组,并用一个指针(栈顶的引用)top来标志栈顶。栈的基本操作只能在栈顶执行,因此所有基本的操作的时间复杂度都为O(1)。

            栈的链式存储实现

            这里不再描述,实现非常简单。值得注意的是,在Java语言中,Stack(栈)这个类是继承于Vector的,也就是说,Java中的栈这个类是通过顺序存储实现的。

    展开全文
  • 3. 栈的基本操作; 1. 基本概念; 首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系; 栈是一种特殊的线性表,也叫受限线性表; 定义中说是在线性表的表尾进行插入和删除操作,这里表尾是...

    目录

     

    1. 基本概念;

    2. 特性;

    3. 栈的基本操作;


    1. 基本概念;

    首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系

    栈是一种特殊的线性表,也叫受限线性表

    定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶而不是栈底

     

    2. 特性;

    限制了这个线性表的插入和删除的位置,它始终只在栈顶进行

    栈底是固定的,最先进栈的只能在栈底

     

    3. 栈的基本操作;

    创建、销毁、清空、进栈、出栈、获取栈顶元素、获取栈的大小;

    栈的插入操作,也叫进栈、压栈等。类似子弹入弹夹(如下图所示);

    栈的删除操作,也叫出栈、退栈等。类似于弹夹中的子弹出弹夹(入下图所示);

    栈的抽象数据类型定义:

    ADT栈(Stack) 
    Data

             通线性表。元素具有相同的类型,相邻的元素具有前驱和后继关系。

    Operation(操作)
    // 初始化,建立一个空栈S
    InitStack(*S);
    // 若栈为空,返回true,否则返回false
    StackEmpty(S);
    // 将栈清空
    ClearStack(*S);
    // 若栈存在且非空,用e返回S的栈顶元素
    GetTop(S, *e);
    // 若栈S存在,插入新元素e到站S中并成为其栈顶元素
    Push(*S, e);
    // 删除栈S中的栈顶元素,并用e返回其值 
    Pop(*S, *e);
    // 返回栈S的元素个数
    StackLength(S);
    // 若栈存在,则销毁它
    DestroyStack(*S);

     

    展开全文
  • 栈的基本使用一、基本介绍二、基本应用场景三、基本操作代码实现 一、基本介绍 栈(stack)作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。 基本特性: 栈是一个先入后出的有序列表。 栈是...
  • 顺序栈的基本操作

    2020-03-01 18:52:51
    栈的定义 栈是限定在表的同一端进行插入或删除的线性表,进行插入或删除的一端为栈顶,另一端为栈底,没有数据元素的栈称为空栈,插入数据元素的操作为入栈,删除数据元素的操作为出栈。 栈具有后进先出的特性。 一...
  • 栈的定义:只允许在一端进行插入或删除操作的线性表,也可以将栈称作受限线性表。 能作插入或者删除操作的一端称为栈顶,另一端则为栈底。(假如a4取出,a3则为新的栈顶) 依次按a1、a2、a3、a4放入, 完全取出时顺序...
  • 栈的基本知识及应用

    2017-11-02 19:36:41
    栈的基本知识及应用 1.栈的概念和特性 栈(stack)是一种特殊的线性表。作为一个简单的例子,可以把食堂里冼净的一摞碗看作一个栈。在通常情况下,最先冼净的碗总是放在最底下,后冼净的碗总是摞在最顶上。而在使用...
  • 今天我们来聊聊栈,栈的基本模型其实比较简单,他所拥有的特性也就是LIFO(后进先出),实现起来可以通过顺序表的基本结构来实现,也可以用链表的基本结构来实现。 可是既然已经有了顺序表和链表这种结构,那么栈...
  • 栈的基本操作(C语言版)

    千次阅读 多人点赞 2018-06-26 11:20:27
    概念 一种特殊的线性表,只能在固定的一端进行插入和删除操作,这个固定的一端称为栈顶,另外一端称为栈底,没有...栈的基本操作 动态顺序栈的结构体———&gt;其中包括动态数组(_array),空间容量(_capaci...
  • 静态栈的简单操作先来简单的了解一下栈1.栈:一种特殊的线性表,其实只允许在固定的一端进行插入或删除操作。进行数据插入和删除的一端称为栈顶,另一端称为栈底。不含任何元素的栈称为空栈,栈又称为后进先出的...
  • 栈的基本概念及相应操作一、栈的定义及使用栈的定义特性栈的应用场景 一、栈的定义及使用 栈的定义特性 栈的应用场景 一、栈的定义及使用
  • 一、栈 栈(Stack)是只允许在一端进行插入或删除操作的线性表。线性表允许进行插入删除的一端为栈顶(Top),不允许进行插入和删除的一端为栈底(Bottom)。...二、使用数组模拟栈的基本操作 1、基本定义 (1)
  • 使用java设计实现顺序栈的基本结构

    千次阅读 2018-03-14 23:06:56
    使用java设计实现顺序栈的基本结构,输入一个字符串来判断()以及[]是否匹配 基本栈结构介绍 顺序栈是一种FILO的结构,根据顺序栈的特性可以通过数组来实现顺序栈的相关操作。 使用一个头指针来作为数组存储元素...
  • 虚拟机栈的指令集小,方便编译器解释,更容易实现跨平台的特性。但缺点也很明显,性能比寄存器要差很多。 栈是运行时的单位,而堆是存储的单位。 栈解决程序如何执行,如何处理数据,而堆解决数据怎么放,放哪的问题...
  • 栈 一种特殊的线性表,其只允许在固定的一端...栈的结构:   栈特性:后进先出(LILO)特殊线性表 。 栈功能:将数据从一种序列改变到另一种序列 。 顺序栈的结构c语言描述: typedef struct Stack {  SData...
  • 数据结构学习-Unit3栈与队列-栈 大一新生,刚学习数据结构。如有问题,望指正,本人将感激不尽。...我们先来看栈的结构: typedef struct stac { int *top; int *bottom; int stacksize; }Stack; t...
  • :什么是?又该怎么理解呢? (stack)又名堆栈,它是一种运算受限...(Stack)是操作系统在建立某个进程时或者线程(在支持多线程操作系统中是线程)为这个线程建立存储区域,该区域具有FIFO的特性,在编
  • Python算法实战视频课程--栈的应用

    千人学习 2016-05-11 09:21:09
    栈是程序设计中被广泛使用的数据结构, 很多问题都满足栈"后进先出"的特性, 本课程以实际应用为主, 先了解栈的基本特性, 操作接口以及python中的使用后, 以多个编程实例带领大家真正学会栈在实际问题中的运用.
  • 栈的基本操作的实现(初始化、赋值、取值、插入、删除等),要求分别采用顺序和链式存储结构。 写一个程序,将输入的十进制数据M 转换为八进制数据M8,将其调试通过。在此基础上修改程序,实现十进制数据M 向N 进制...
  • 和队列的基本操作

    千次阅读 2018-09-23 23:40:36
    栈   一种特殊的的线性表,只允许在固定的一端进行插入和删除操作。栈被称作是先进后出的线性表。 ...只允许在一端进行插入数据操作,在另一端删除数据操作的特殊...栈的基本操作 初始化、销毁、增、删、查 ...
  • 栈的特性:后进先出(LILO)特殊线性表 栈功能:将数据从一种序列改变到另一种序列 括号匹配问题: 思路: 1.检测该字符是否为括号,是括号继续,否则返回 2.如果是左括号,入栈 3.如果是右括号,判断栈...
  • 共享栈的定义以及基本操作

    千次阅读 2019-09-30 15:58:13
    1、共享栈:利用栈底位置相对不变的特性,让两个顺序栈共享一个一维数组空间。 2、共享栈的存储结构: #define stacklen 100 typedef struct{ char ch[stacklen]; int top1; //左边栈的栈顶 int top2; //右边...
  • 顺序栈的基本运算 栈的应用,先将所有的字符压入栈中,通过出栈一个个与数组str的字符从头到尾比较,根据栈的特性,先进后出,最先出栈的是字符串的尾 int Palindrome(char str[],int n) { SqStack st;//定义一个...
  •    顺序栈:栈的顺序存储结构,是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序 栈中的位置。    栈在数据结构中也是一个比较重要的结构,它有一个重要的特性...
  • 栈的定义及其基本运算

    万次阅读 2016-03-16 23:27:20
    栈的特征:由于栈只能从一端插入和删除元素,故栈具有后进先出(Last in,first out,LIFO)的特性。称插入和删除的一端为栈顶(top),另一端为栈底(bottom)。称插入元素为入栈或压栈(push),删除元素为出栈或弹栈(pop)
  • 从数据结构角度看,和队列也是线性表,其特殊在于和队列的基本操作是线性表操作的子集,他们是操作受限的线性表。但是从数据类型角度看,他们是和线性表大不相同的抽象数据类型。 是限定仅在表尾进行插入或者...

空空如也

空空如也

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

栈的基本特性