精华内容
下载资源
问答
  • 2019-05-28 11:31:16
    后进先出是它最大的特点。 何时使用? 相比数组和链表,带给我的只有限制,并没有任何优势。那我直接使用数组或者链表不就好了吗?为什么还要用这个“操作受限”的“”呢?事实上,从功能上来说,数组或...

    从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在在一端插入和删除数据,只支持入栈和出栈操作。后进先出是它最大的特点。

    何时使用栈?

    相比数组和链表,栈带给我的只有限制,并没有任何优势。那我直接使用数组或者链表不就好了吗?为什么还要用这个“操作受限”的“栈”呢?事实上,从功能上来说,数组或链表确实可以替代栈,但你要知道,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

    当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。

    如何实现一个栈?

    栈主要包含两个操作,入栈出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。

    栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈

    操作的时间、空间复杂度是多少呢?

    入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是 O(1)

    不管是顺序栈还是链式栈,我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。注意,这里存储数据需要一个大小为 n 的数组,并不是说空间复杂度就是 O(n)。因为,这n 个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

    支持动态扩容的顺序栈

    时间复杂度分析:根据均摊复杂度的定义,可以得数组实现(自动扩容)符合大多数情况是O(1)级别复杂度,个别情况是O(n)级别复杂度,比如自动扩容时,会进行完整数据的拷贝。

    空间复杂度分析:在入栈和出栈的过程中,只需要一两个临时变量存储空间,所以O(1)级别。我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

    栈在软件工程中的实际应用

    1、栈在函数调用中的应用:

    为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?

    其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。

    从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。

    2、栈在表达式求值中的应用:

    编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。

    3、栈在括号匹配中的应用

    4、如何实现浏览器的前进、后退功能

    5、leetcode上关于栈的题目大家可以先做 20,155,232,844,224,682,496.

    展开全文
  • 栈是一种用于存储数据的简单数据结构(与链表类似),栈只有一个开口,先进去的就到最底下,后进来的就在前面,要是拿出去的话,肯定是从开口端拿出去,所以说先进后出,后进先出,只允许在一端进行插入和删除操作。...

    数据结构-栈和队列

    • 栈—Stack

           栈是一种用于存储数据的简单数据结构(与链表类似),栈只有一个开口,先进去的就到最底下,后进来的就在前面,要是拿出去的话,肯定是从开口端拿出去,所以说先进后出,后进先出,只允许在一端进行插入和删除操作。
           试图对一个空栈执行栈操作称为下溢(underflow);
           试图对一个满栈执行栈操作称为溢出(overflow)。
           通常,溢出和下溢均认为是异常;
    在这里插入图片描述

    首先我们来看看Stack源码:

    public class Stack<E> extends Vector<E> {
       // 首先可以看出继承Vector,所以我们在使用API的过程有好多方法是Vector的方法,
       // 而我们今天主要研究的是栈,所以忽略Vector提供的方法。
        public Stack() {
        }
    
    public E push(E item) {  //栈的添加方法--进栈
            addElement(item);//线程安全的
            return item;
        }
    
     public synchronized E pop() {  //出栈
            E       obj;
            int     len = size();
    
            obj = peek();
            removeElementAt(len - 1);
    
            return obj;
        }
    
    public synchronized E peek() { -- 取栈顶值(不出栈)
            int     len = size();
    
            if (len == 0)
                throw new EmptyStackException();
            return elementAt(len - 1);
        }
    
    
     public synchronized int search(Object o) {//方法调用返回从堆栈中,对象位于顶部的基于1的位置
            int i = lastIndexOf(o);
    
            if (i >= 0) {
                return size() - i;
            }
            return -1;
        }
    

    通过实例来验证先入后出,后入先出的原则:

    在这里插入图片描述
           我最后插入的一个元素为“D”,现在进行了一次出栈操作,可以看出第一个输出的元素为“D",完全验证了栈的特点。

    • 队列—Queue

           队列是一种用于存储数据的数据结构(与链表和栈类似),数据到达的次序是队列的关键;在日常生活中队列是指从序列的开始按照顺序等待服务的一队人或物。
            队列是一种只能在一端插入(队尾),在另一端删除(队首)的有序线性表。队列中第一个插入的元素也是第一个被删除的元素,所以队列是一种先进先出(FIFO,First In First Out)或后进后出(LiLO,Last In Last Out)线性表。
            在队列中插入一个元素,称为入队(EnQueue),从队列中删除一个元素,称为出队(DeQueue);试图对一个空队列执行出队操作称为下溢(underflow),试图对一个满队列执行入队操作称为溢出(overflow);通常认为溢出和下溢是异常。

    在这里插入图片描述
    Queue常用方法:

    • boolean add(E e);将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回 true,如果当前没有可用的空间,则抛出 IllegalStateException。
    • boolean offer(E e);将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
    • E remove();获取并移除此队列的头。
    • E poll();获取并移除此队列的头,如果此队列为空,则返回 null。
    • E element();获取,但是不移除此队列的头。
    • E peek();获取但不移除此队列的头;如果此队列为空,则返回 null。

    代码示例:

     		  Queue<String> queue=new LinkedList<>();
    		  queue.offer("one");
    		  queue.offer("two");
    		  queue.offer("three");
    		  queue.offer("four");
    		  System.out.println(queue);
    		  queue.add("1");
    		  System.out.println(queue);
    		  //返回队首的元素,但不进行删除
    		  queue.element();
    		  System.out.println(queue);
    		  //将元素从队列的队首删除。
    		  queue.remove();
    		  //从队首取出元素并删除
    	      String poll = queue.poll();
    	      System.out.println(poll);
    	      
    	      //从队首取出元素但是不删除
    	      String peek = queue.peek();
    	      System.out.println(peek);
    	      System.out.println(queue);
    
    	      //遍历队列,这里要注意,每次取完元素后都会删除,整个
    	      //队列会变短,所以只需要判断队列的大小即可
    	      while(queue.size() > 0) {
                System.out.println(queue.poll());
    	      }
    

    输出结果:

    [one, two, three, four]
    [one, two, three, four, 1]
    [one, two, three, four, 1]
    two
    three
    [three, four, 1]
    three
    four
    1
    
    
    • Deque接口(双向队列)
      Deque接口,是Queue接口的子接口,是指队列两端的元素,既能入队(offer)也能出队。
      如果将Deque限制为只能从一端进行入队,和出队,就是栈的数据结构的实现。对于栈而言,有入栈(push)和出栈(pop),遵循先进后出的规则。
      Deque与支持从数据结构的任一端添加或删除元素的双端队列相关,它可以用作队列(先进先出/ FIFO)或堆栈(LIFO)。这些比Stack和LinkedList更快。
      在这里插入图片描述

    几个重要特性是

    • 它提供可调整大小的阵列的支持,并有助于无限制容量,因此根据用途增长阵列。
    • Array deques禁止使用Null元素,不接受任何此类元素。
    • 不支持多线程的任何并发访问。
    • 在没有外部同步的情况下,Deque不是线程安全的。

    API文档:

    • add(element):向尾部添加元素。
    • addFirst(element):向头部添加元素。
    • addLast(element):向尾部添加元素。
    • offer(element):向尾部添加一个元素并返回一个布尔值来解释插入是否成功。
    • offerFirst(element):向头部添加一个元素并返回一个布尔值来解释插入是否成功。
    • offerLast(element):向尾部添加一个元素并返回一个布尔值来解释插入是否成功。
    • iterator():返回此双端队列的迭代器。
    • descendingIterator():返回一个迭代器,该迭代器具有此双端队列的相反顺序。
    • push(element):向头部添加元素。
    • pop(element):从头部移除一个元素并返回它。
    • removeFirst():删除头部的元素。
    • removeLast():删除尾部的元素。
    • poll():检索并删除此双端队列表示的队列的头部(换句话说,此双端队列的第一个元素),如果此双端队列为空,则返回null。
    • pollFirst():检索并删除此双端队列的第一个元素,如果此双端队列为空,则返回null。
    • pollLast():检索并删除此双端队列的最后一个元素,如果此双端队列为空,则返回null。
    • peek():检索但不删除此双端队列表示的队列的头部(换句话说,此双端队列的第一个元素),如果此双端队列为空,则返回null。
    • peekFirst():检索但不删除此双端队列的第一个元素,如果此双端队列为空,则返回null。
    • peekLast():检索但不删除此双端队列的最后一个元素,如果此双端队列为空,则返回null。

    代码示例:

    	Deque<String> deque = new LinkedList<String>();
            deque.add("Element 1 (Tail)"); // add to tail
            deque.addFirst("Element 2 (Head)");
            deque.addLast("Element 3 (Tail)");
            deque.push("Element 4 (Head)"); //add to head
            deque.offer("Element 5 (Tail)");
            deque.offerFirst("Element 6 (Head)");
            deque.offerLast("Element 7 (Tail)");
     
            System.out.println(deque + "\n");
     
     
            System.out.println("Standard Iterator");
            Iterator iterator = deque.iterator();
            while (iterator.hasNext())
                System.out.println("\t" + iterator.next());
            Iterator reverse = deque.descendingIterator();
            
            System.out.println("Reverse Iterator");
            while (reverse.hasNext())
                System.out.println("\t" + reverse.next());
            System.out.println("Peek " + deque.peek());
            System.out.println("After peek: " + deque);
    
            System.out.println("Pop " + deque.pop());
            System.out.println("After pop: " + deque);
     
            System.out.println("Contains element 3: " +
                            deque.contains("Element 3 (Tail)"));
     
            deque.removeFirst();
            deque.removeLast();
            System.out.println("Deque after removing " +
                                "first and last: " + deque);
     
        }
    

    输出结果:

    [Element 6 (Head), Element 4 (Head), Element 2 (Head), Element 1 (Tail), Element 3 (Tail), Element 5 (Tail), Element 7 (Tail)]
    
    Standard Iterator
    	Element 6 (Head)
    	Element 4 (Head)
    	Element 2 (Head)
    	Element 1 (Tail)
    	Element 3 (Tail)
    	Element 5 (Tail)
    	Element 7 (Tail)
    Reverse Iterator
    	Element 7 (Tail)
    	Element 5 (Tail)
    	Element 3 (Tail)
    	Element 1 (Tail)
    	Element 2 (Head)
    	Element 4 (Head)
    	Element 6 (Head)
    Peek Element 6 (Head)
    After peek: [Element 6 (Head), Element 4 (Head), Element 2 (Head), Element 1 (Tail), Element 3 (Tail), Element 5 (Tail), Element 7 (Tail)]
    Pop Element 6 (Head)
    After pop: [Element 4 (Head), Element 2 (Head), Element 1 (Tail), Element 3 (Tail), Element 5 (Tail), Element 7 (Tail)]
    Contains element 3: true
    Deque after removing first and last: [Element 2 (Head), Element 1 (Tail), Element 3 (Tail), Element 5 (Tail)]
    
    
    展开全文
  • 在通常情况下由操作系统(OS)和语言的运行时(runtime)控制吗?它们的作用范围什么?它们的大小由什么决定?哪个更快?...通常用后进先出(LIFO)的方式预留空间;因此最近的保留块(reserved bloc
    1. 在通常情况下由操作系统(OS)和语言的运行时(runtime)控制吗?
    2. 它们的作用范围是什么?
    3. 它们的大小由什么决定?
    4. 哪个更快?

    答案一

    栈是为执行线程留出的内存空间。当函数被调用的时候,栈顶为局部变量和一些 bookkeeping 数据预留块。当函数执行完毕,块就没有用了,可能在下次的函数调用的时候再被使用。栈通常用后进先出(LIFO)的方式预留空间;因此最近的保留块(reserved block)通常最先被释放。这么做可以使跟踪堆栈变的简单;从栈中释放块(free block)只不过是指针的偏移而已。

    堆(heap)是为动态分配预留的内存空间。和栈不一样,从堆上分配和重新分配块没有固定模式;你可以在任何时候分配和释放它。这样使得跟踪哪部分堆已经被分配和被释放变的异常复杂;有许多定制的堆分配策略用来为不同的使用模式下调整堆的性能。

    每一个线程都有一个栈,但是每一个应用程序通常都只有一个堆(尽管为不同类型分配内存使用多个堆的情况也是有的)。

    直接回答你的问题: 1. 当线程创建的时候,操作系统(OS)为每一个系统级(system-level)的线程分配栈。通常情况下,操作系统通过调用语言的运行时(runtime)去为应用程序分配堆。 2. 栈附属于线程,因此当线程结束时栈被回收。堆通常通过运行时在应用程序启动时被分配,当应用程序(进程)退出时被回收。 3. 当线程被创建的时候,设置栈的大小。在应用程序启动的时候,设置堆的大小,但是可以在需要的时候扩展(分配器向操作系统申请更多的内存)。 4. 栈比堆要快,因为它存取模式使它可以轻松的分配和重新分配内存(指针/整型只是进行简单的递增或者递减运算),然而堆在分配和释放的时候有更多的复杂的 bookkeeping 参与。另外,在栈上的每个字节频繁的被复用也就意味着它可能映射到处理器缓存中,所以很快(译者注:局部性原理)。

    答案二

    Stack:

    1. 和堆一样存储在计算机 RAM 中。
    2. 在栈上创建变量的时候会扩展,并且会自动回收。
    3. 相比堆而言在栈上分配要快的多。
    4. 用数据结构中的栈实现。
    5. 存储局部数据,返回地址,用做参数传递。
    6. 当用栈过多时可导致栈溢出(无穷次(大量的)的递归调用,或者大量的内存分配)。
    7. 在栈上的数据可以直接访问(不是非要使用指针访问)。
    8. 如果你在编译之前精确的知道你需要分配数据的大小并且不是太大的时候,可以使用栈。
    9. 当你程序启动时决定栈的容量上限。

    Heap:

    1. 和栈一样存储在计算机RAM。
    2. 在堆上的变量必须要手动释放,不存在作用域的问题。数据可用 delete, delete[] 或者 free 来释放。
    3. 相比在栈上分配内存要慢。
    4. 通过程序按需分配。
    5. 大量的分配和释放可造成内存碎片。
    6. 在 C++ 中,在堆上创建数的据使用指针访问,用 new 或者 malloc 分配内存。
    7. 如果申请的缓冲区过大的话,可能申请失败。
    8. 在运行期间你不知道会需要多大的数据或者你需要分配大量的内存的时候,建议你使用堆。
    9. 可能造成内存泄露。



    int foo()
    {
        char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
        bool b = true; // Allocated on the stack.
        if(b)
        {
            //Create 500 bytes on the stack
            char buffer[500];
     
            //Create 500 bytes on the heap
            pBuffer = new char[500];
     
        }//<-- buffer is deallocated here, pBuffer is not
    }//<--- oops there's a memory leak, I should have called delete[] pBuffer;

    什么是堆和栈,它们在哪儿?

    问题描述

    编程语言书籍中经常解释值类型被创建在栈上,引用类型被创建在堆上,但是并没有本质上解释这堆和栈是什么。我仅有高级语言编程经验,没有看过对此更清晰的解释。我的意思是我理解什么是栈,但是它们到底是什么,在哪儿呢(站在实际的计算机物理内存的角度上看)?

    1. 在通常情况下由操作系统(OS)和语言的运行时(runtime)控制吗?
    2. 它们的作用范围是什么?
    3. 它们的大小由什么决定?
    4. 哪个更快?

    答案一

    栈是为执行线程留出的内存空间。当函数被调用的时候,栈顶为局部变量和一些 bookkeeping 数据预留块。当函数执行完毕,块就没有用了,可能在下次的函数调用的时候再被使用。栈通常用后进先出(LIFO)的方式预留空间;因此最近的保留块(reserved block)通常最先被释放。这么做可以使跟踪堆栈变的简单;从栈中释放块(free block)只不过是指针的偏移而已。

    堆(heap)是为动态分配预留的内存空间。和栈不一样,从堆上分配和重新分配块没有固定模式;你可以在任何时候分配和释放它。这样使得跟踪哪部分堆已经被分配和被释放变的异常复杂;有许多定制的堆分配策略用来为不同的使用模式下调整堆的性能。

    每一个线程都有一个栈,但是每一个应用程序通常都只有一个堆(尽管为不同类型分配内存使用多个堆的情况也是有的)。

    直接回答你的问题: 1. 当线程创建的时候,操作系统(OS)为每一个系统级(system-level)的线程分配栈。通常情况下,操作系统通过调用语言的运行时(runtime)去为应用程序分配堆。 2. 栈附属于线程,因此当线程结束时栈被回收。堆通常通过运行时在应用程序启动时被分配,当应用程序(进程)退出时被回收。 3. 当线程被创建的时候,设置栈的大小。在应用程序启动的时候,设置堆的大小,但是可以在需要的时候扩展(分配器向操作系统申请更多的内存)。 4. 栈比堆要快,因为它存取模式使它可以轻松的分配和重新分配内存(指针/整型只是进行简单的递增或者递减运算),然而堆在分配和释放的时候有更多的复杂的 bookkeeping 参与。另外,在栈上的每个字节频繁的被复用也就意味着它可能映射到处理器缓存中,所以很快(译者注:局部性原理)。

    答案二

    Stack:

    1. 和堆一样存储在计算机 RAM 中。
    2. 在栈上创建变量的时候会扩展,并且会自动回收。
    3. 相比堆而言在栈上分配要快的多。
    4. 用数据结构中的栈实现。
    5. 存储局部数据,返回地址,用做参数传递。
    6. 当用栈过多时可导致栈溢出(无穷次(大量的)的递归调用,或者大量的内存分配)。
    7. 在栈上的数据可以直接访问(不是非要使用指针访问)。
    8. 如果你在编译之前精确的知道你需要分配数据的大小并且不是太大的时候,可以使用栈。
    9. 当你程序启动时决定栈的容量上限。

    Heap:

    1. 和栈一样存储在计算机RAM。
    2. 在堆上的变量必须要手动释放,不存在作用域的问题。数据可用 delete, delete[] 或者 free 来释放。
    3. 相比在栈上分配内存要慢。
    4. 通过程序按需分配。
    5. 大量的分配和释放可造成内存碎片。
    6. 在 C++ 中,在堆上创建数的据使用指针访问,用 new 或者 malloc 分配内存。
    7. 如果申请的缓冲区过大的话,可能申请失败。
    8. 在运行期间你不知道会需要多大的数据或者你需要分配大量的内存的时候,建议你使用堆。
    9. 可能造成内存泄露。

    举例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int foo()
    {
        char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
        bool b = true; // Allocated on the stack.
        if(b)
        {
            //Create 500 bytes on the stack
            char buffer[500];
     
            //Create 500 bytes on the heap
            pBuffer = new char[500];
     
        }//<-- buffer is deallocated here, pBuffer is not
    }//<--- oops there's a memory leak, I should have called delete[] pBuffer;

    答案三

    堆和栈是两种内存分配的两个统称。可能有很多种不同的实现方式,但是实现要符合几个基本的概念:

    1.对栈而言,栈中的新加数据项放在其他数据的顶部,移除时你也只能移除最顶部的数据(不能越位获取)。

    khqDF

     

    2.对堆而言,数据项位置没有固定的顺序。你可以以任何顺序插入和删除,因为他们没有“顶部”数据这一概念。

    E5QTV

     

    上面上个图片很好的描述了堆和栈分配内存的方式。

    在通常情况下由操作系统(OS)和语言的运行时(runtime)控制吗?

    如前所述,堆和栈是一个统称,可以有很多的实现方式。计算机程序通常有一个栈叫做调用栈,用来存储当前函数调用相关的信息(比如:主调函数的地址,局部变量),因为函数调用之后需要返回给主调函数。栈通过扩展和收缩来承载信息。实际上,程序不是由运行时来控制的,它由编程语言、操作系统甚至是系统架构来决定。

    堆是在任何内存中动态和随机分配的(内存的)统称;也就是无序的。内存通常由操作系统分配,通过应用程序调用 API 接口去实现分配。在管理动态分配内存上会有一些额外的开销,不过这由操作系统来处理。

    它们的作用范围是什么?

    调用栈是一个低层次的概念,就程序而言,它和“作用范围”没什么关系。如果你反汇编一些代码,你就会看到指针引用堆栈部分。就高级语言而言,语言有它自己的范围规则。一旦函数返回,函数中的局部变量会直接直接释放。你的编程语言就是依据这个工作的。

    在堆中,也很难去定义。作用范围是由操作系统限定的,但是你的编程语言可能增加它自己的一些规则,去限定堆在应用程序中的范围。体系架构和操作系统是使用虚拟地址的,然后由处理器翻译到实际的物理地址中,还有页面错误等等。它们记录那个页面属于那个应用程序。不过你不用关心这些,因为你仅仅在你的编程语言中分配和释放内存,和一些错误检查(出现分配失败和释放失败的原因)。

    它们的大小由什么决定?

    依旧,依赖于语言,编译器,操作系统和架构。栈通常提前分配好了,因为栈必须是连续的内存块。语言的编译器或者操作系统决定它的大小。不要在栈上存储大块数据,这样可以保证有足够的空间不会溢出,除非出现了无限递归的情况(额,栈溢出了)或者其它不常见了编程决议。

    堆是任何可以动态分配的内存的统称。这要看你怎么看待它了,它的大小是变动的。在现代处理器中和操作系统的工作方式是高度抽象的,因此你在正常情况下不需要担心它实际的大小,除非你必须要使用你还没有分配的内存或者已经释放了的内存。

    哪个更快一些?

    栈更快因为所有的空闲内存都是连续的,因此不需要对空闲内存块通过列表来维护。只是一个简单的指向当前栈顶的指针。编译器通常用一个专门的、快速的寄存器来实现。更重要的一点事是,随后的栈上操作通常集中在一个内存块的附近,这样的话有利于处理器的高速访问(译者注:局部性原理)。

    答案四

    你问题的答案是依赖于实现的,根据不同的编译器和处理器架构而不同。下面简单的解释一下:

    1. 栈和堆都是用来从底层操作系统中获取内存的。
    2. 在多线程环境下每一个线程都可以有他自己完全的独立的栈,但是他们共享堆。并行存取被堆控制而不是栈。

    堆:

    1. 堆包含一个链表来维护已用和空闲的内存块。在堆上新分配(用 new 或者 malloc)内存是从空闲的内存块中找到一些满足要求的合适块。这个操作会更新堆中的块链表。这些元信息也存储在堆上,经常在每个块的头部一个很小区域。
    2. 堆的增加新快通常从地地址向高地址扩展。因此你可以认为堆随着内存分配而不断的增加大小。如果申请的内存大小很小的话,通常从底层操作系统中得到比申请大小要多的内存。
    3. 申请和释放许多小的块可能会产生如下状态:在已用块之间存在很多小的空闲块。进而申请大块内存失败,虽然空闲块的总和足够,但是空闲的小块是零散的,不能满足申请的大小,。这叫做“堆碎片”。
    4. 当旁边有空闲块的已用块被释放时,新的空闲块可能会与相邻的空闲块合并为一个大的空闲块,这样可以有效的减少“堆碎片”的产生。

    0Obi0

     

    栈:

    1. 栈经常与 sp 寄存器(译者注:”stack pointer”,了解汇编的朋友应该都知道)一起工作,最初 sp 指向栈顶(栈的高地址)。
    2. CPU 用 push 指令来将数据压栈,用 pop 指令来弹栈。当用 push 压栈时,sp 值减少(向低地址扩展)。当用 pop 弹栈时,sp 值增大。存储和获取数据都是 CPU 寄存器的值。
    3. 当函数被调用时,CPU使用特定的指令把当前的 IP (译者注:“instruction pointer”,是一个寄存器,用来记录 CPU 指令的位置)压栈。即执行代码的地址。CPU 接下来将调用函数地址赋给 IP ,进行调用。当函数返回时,旧的 IP 被弹栈,CPU 继续去函数调用之前的代码。
    4. 当进入函数时,sp 向下扩展,扩展到确保为函数的局部变量留足够大小的空间。如果函数中有一个 32-bit 的局部变量会在栈中留够四字节的空间。当函数返回时,sp 通过返回原来的位置来释放空间。
    5. 如果函数有参数的话,在函数调用之前,会将参数压栈。函数中的代码通过 sp 的当前位置来定位参数并访问它们。
    6. 函数嵌套调用和使用魔法一样,每一次新调用的函数都会分配函数参数,返回值地址、局部变量空间、嵌套调用的活动记录都要被压入栈中。函数返回时,按照正确方式的撤销。
    7. 栈要受到内存块的限制,不断的函数嵌套/为局部变量分配太多的空间,可能会导致栈溢出。当栈中的内存区域都已经被使用完之后继续向下写(低地址),会触发一个 CPU 异常。这个异常接下会通过语言的运行时转成各种类型的栈溢出异常。(译者注:“不同语言的异常提示不同,因此通过语言运行时来转换”我想他表达的是这个含义)

    9UshP

     

    *函数的分配可以用堆来代替栈吗?

    不可以的,函数的活动记录(即局部或者自动变量)被分配在栈上, 这样做不但存储了这些变量,而且可以用来嵌套函数的追踪。

    堆的管理依赖于运行时环境,C 使用 malloc ,C++ 使用 new ,但是很多语言有垃圾回收机制。

    栈是更低层次的特性与处理器架构紧密的结合到一起。当堆不够时可以扩展空间,这不难做到,因为可以有库函数可以调用。但是,扩展栈通常来说是不可能的,因为在栈溢出的时候,执行线程就被操作系统关闭了,这已经太晚了。

    译者注

    关于堆栈的这个帖子,对我来说,收获非常多。我之前看过一些资料,自己写代码的时候也常常思考。就这方面,也和祥子(我的大学舍友,现在北京邮电读研,技术牛人)探讨过多次了。但是终究是一个一个的知识点,这个帖子看完之后,豁然开朗,把知识点终于连接成了一个网。这种感觉,经历过的一定懂得,期间的兴奋不言而喻。

    这个帖子跟帖者不少,我选了评分最高的四个。这四个之间也有一些是重复的观点。个人钟爱第四个回答者,我看的时候,瞬间高潮了,有木有?不过需要一些汇编语言、操作系统、计算机组成原理的的基础,知道那几个寄存器是干什么的,要知道计算机的流水线指令工作机制,保护/恢复现场等概念。三个回复者都涉及到了操作系统中虚拟内存;在比较速度的时候,大家一定要在脑中对“局部性原理”和计算机高速缓存有一个概念。

    如果你把这篇文章看懂了,我相信你收获的不只是堆和栈,你会理解的更多!

    兴奋之余,有几点还是要强调的,翻译没有逐字逐词翻译,大部分是通过我个人的知识积累和对回帖者的意图揣测而来的。请大家不要咬文嚼字,逐个推敲,我们的目的在于技术交流,不是么?达到这一目的就够了。

    下面是一些不确定点:

    1. 我没有听过 bookkeeping data 这种说法,故没有翻译。从上下文理解来看,可以想成是用来寄存器值?函数参数?返回地址?如果有了解具体含义的朋友,烦请告知。
    2. 栈和堆栈是一回事,英文表达是 stack,堆是 heap。
    3. 调用栈的概念,我是第一次听说,不太熟悉。大家可以去查查资料研究一下。

    展开全文
  • js执行啥意思

    2021-03-01 22:10:42
    名字叫的都 "先进后出,后进先出" 那么这个"先进后出,后进先出"到底指的什么呢 这个 可以看到代码确实自上而下执行的,先打印的bar1,再打印的foo,那这不就是先调用的先执行吗, "先进后出,后进先出...

    名字叫栈的都是 "先进后出,后进先出"

    那么这个 "先进后出,后进先出"到底指的是什么呢

    是这个

    可以看到代码确实是自上而下执行的,先打印的bar1,再打印的foo,那这不就是先调用的先执行吗, 

    "先进后出,后进先出"到底指的是什么呢   它指的是执行完,可以看到,如果foo不执行完,bar2是打印不出来的,所以foo虽然是后调用,但是它要先执行完,才返回回bar函数去打印bar2

    不论多少层都是这样"先进后出,后进先出"

     

    突然发现js这个语言是函数驱动的,除了声明.表达式.就基本全是函数了,你看哪个地方没有小括号()的,console.log()就是个函数

    所以js执行栈才叫js函数执行栈,开始还不理解为什么就叫函数,原来js就是都是函数

     

     

    展开全文
  • 和队列的互相实现

    2021-02-18 16:46:57
    后进先出的数据结构 队列:先进先出的数据结构 如图所示: 那么以C++为例,自己使用的编程语言里和队列什么样的呢。可以思考以下几个方面: C++中的 stack 容器吗? 我们使用的stack属于哪个版本的...
  • 函数调用浅析

    2017-03-17 17:00:00
    以前面试的时候,碰到过一个问题。函数的调用过程是怎样的? 听到问题的时候有点懵,这算是...函数调用栈是程序运行时一段连续的内存区域,栈是后进先出的数据结构。 内存的生长方向是从低地址向高地址,而栈是相...
  • 本文目录一、JavaScript栈数据结构二、一个基于数组的栈①创建一个基于数组的栈②向栈添加元素③从栈移除元素④查看栈顶元素⑤检查栈是否为空...栈是一种遵从后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保
  • 为实习准备的数据结构(3)-- 详解

    千次阅读 多人点赞 2020-12-21 09:23:14
    文章目录后进先出的叫②API设计③顺序实现④双端实现多端⑤动态⑥汉诺塔⑦单调性质:波兰式与逆波兰式什么波兰表达式中缀表达式转逆波兰表达式后缀表达式运算流程放码过去队列消息队列 想当一...
  • (1)栈是一种后进先出(LIFO)last in first out原则的有序集合;只能从后边添加元素和从开头删除元素 (2)新添加或待删除的元素都保存在栈的同一端,为栈顶(push( 数组中末位置添加元素)数组中的pop(删除数组中...
  • 其实,我们不一定非要用来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用这种数据结构来实现,最顺理成章的选择。 从调用函数进入被调用函数,对于数据来说,变化的什么呢?作用域。所以...
  • 与队列

    2020-03-03 11:50:26
    后进先出,先进者后出,这就是典型的“栈”结构 从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据 可能有人会觉得,相比链表,栈带给我的只有限制,并没有任何优势。那我直接...
  • 浅析数据结构中与C实现

    千次阅读 2016-01-12 22:04:01
    今天放松一下,我们来看看数据结构中的,这节的知识点可以说是数据结构中最容易上手的知识点了,其实比起链表,其实链表也有和队列的模型,链表的头插其实就是后进先出,链表的尾插其实就是先进先出,这不就是...
  • 的简单理解

    2019-09-25 19:36:35
    stack一种LIFO(后进先出)或者说FILO(先进后出)的结构,可以想象成一叠摆放好的餐盘,最上面的餐盘最后放上去的但是要最先拿出来。 提问:最先入栈的一定最后出栈吗? 让1 2 3三个数字按照大小顺序入栈,则...
  • 之所以称之为,就是因为的特点是后进先出,就像一个货栈,先放进去东西总是放在里面,后放进去的东西放到门口,所以往外拿出来的时候,就先拿出来门口的。 如何表示 我们把线性表看为从上到下的一个一维结构,...
  • 引导 今天我们开始学习的内容,我觉得并不难,所以篇幅也就不会那么多...其实,我们可以这样定义,满足先进后出,后进先出操作特性的就是。因此没有固定的存储形式,比如数据需要存储地址连续,链表存储地...
  • 那就是后进先出,先进者后出。 为什么栈结构受限制,功能少,还这么受欢迎? 从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。 我第一次接触这种数据结构的时候,就对它...
  • Java中的Stack

    2015-08-11 14:43:42
    1.(Stack)实现了一个后进先出(LIFO)的数据结构。只能在一端进行插入(称为"压栈") 或删除 (称为"出栈")数据的操作。当你从中取元素的时候,就从栈顶取一个元素。也就是,最后进栈的元素最先被取出。不是...
  • 极客算法04 |

    2019-03-07 14:26:11
    先进后出,后进先出是它的最大特点。 为什么需要这种操作受限的线性表?直接使用数组或者链表不好吗? 理由,数组和链表确实可以代替完成我们需要的功能,但是我们要知道,特定的数据结构对特定场景的抽象,...
  • 栈是后进先出,堆是随便进出。---------------------都是一种数据结构,用于管理存储空间, 栈用于局部变量分配空间, 容量比较小 堆用于管理大块数据, 容量跟系统资源有关----------------------只从数据结构的方面说...
  • 1.理论介绍 上一篇中我们介绍了数据结构中的堆,常言道堆栈不分家,... 的特殊要求就是LIFO(Last In First Out),对,后进先出。只有栈顶的元素允许访问。还记得上一篇讲的堆吗?从本质上来讲堆也只有顶部的...
  • 后进先出,先进后出,这就是典型的“栈”结构。其实,计算机世界的思想并非石头缝里蹦出来的,现实世界都有它们的影子。 从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。相比...
  • 题目描述 ...的特性:先进后出、后进先出。 链表节点全部进栈后再依次出栈,这不就是逆序结果了吗? 吧,可以好好利用 的特性 解决这题。 题解代码 /** * Definition for singly-linked list. *
  • 数据结构(c++)(2)--的应用

    千次阅读 2017-04-22 23:40:02
    在看到的的这个特性后进先出的性质时,第一感觉就是这样做有什么用呢?把一个表的操作限制成这个样子,不是在削减吗?然而,在实际的应用中,这些存在于中的少数的操作却非常的强大和重要。下面给出三个的...
  • 概念 撤回,即 Ctrl+Z,我们最常见的操作之一,大多数应用都会...中的元素采用 LIFO (Last In First Out),即后进先出。 下图的有 3 个元素,3 在最上面,因此它会被第一个移除: 的基本操作 Push...
  • 后进先出,先进者后出,这就是典型的“栈”结构。 从栈的操作特性上来看,栈是一种“操作受限”的线性表, 只允许在一端插入和删除数据。 那直接使用数组或者链表不就好了吗?为什么还要用这个“操作受限”的“栈...
  • 后进先出,先进者后出,这就是典型的“栈”结构。 从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。 我第一次接触这种数据结构的时候,就对它存在的意义产生了很大的疑惑。因为...
  • (这里“堆栈”的“堆”动词,就是把数据往里面放,放进去的被压在下面,后进的在上面,所以先进后。)堆,一棵二叉树,始终满足下面的值比上面的大。头重脚轻不算堆,要上面小下面大才算一个堆。堆还有一...

空空如也

空空如也

1 2 3 4
收藏数 61
精华内容 24
关键字:

栈是后进先出吗