精华内容
下载资源
问答
  • 获取栈中任意位置的元素

    千次阅读 2018-07-14 19:49:59
    public int getElement(Stack<Integer> stack, int position) { int result = stack.pop(); if (stack.size() == position) { // stack.push(result); re...
    public int getElement(Stack<Integer> stack, int position)
        {
            int result = stack.pop();
            if (stack.size() == position)
            {
    //            stack.push(result);
                return result;
            }else {
                int element = getElement(stack, position);
                stack.push(element);
                return element;
            }
        }
    展开全文
  • 实现一个特殊的,实现的基本功能的基础上,再实现返回栈中最小元素的操作。 要求: pop、push、getMin操作的时间复杂度都是O(1)O(1)O(1)。 设计的类型可以使用现成的结构。 2. 思路 用两个来实现,...

    1. 题目

    实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。

    要求:

    1. pop、push、getMin操作的时间复杂度都是 O ( 1 ) O(1) O(1)
    2. 设计的栈类型可以使用现成的栈结构。

    2. 思路

    1. 用两个栈来实现,栈sData存放入栈元素,栈sMin存放最小值。
    2. 按照元素入栈顺序,将要入栈的第一个元素,同时压入两个栈中。后续每个元素入栈时,与sMin栈中栈顶元素比较大小,若入栈元素data 小于sMin栈顶元素,则把data同时压入两个栈中,若data大于sMin栈中栈顶元素,则只压入栈sData中。出栈时,判断两个栈顶元素是否相等,若相等则两个栈同时执行出栈操作,不相等则,只有栈sData执行出栈操作。

    3. 代码

    #include <iostream>
    #include <exception>
    #include <stack>
    
    template<class T> class MinStack {
     public:
         void push(const T& num);
         T pop();
         T getMin() const;
     private:
        std::stack<T> sData;    // 数据栈
        std::stack<T> sMin;     // 最小栈
    };
    template<typename T>
    T MinStack<T>::getMin() const{
        if (sMin.empty()) {
            throw std::runtime_error("min stack is empty");
        } else {
            return sMin.top();  // top是获取栈顶元素
        }
    }
    template<class T>
    void MinStack<T>::push(const T& num) {
        if (sData.empty()) {    // 如果当前数据栈为空
            sData.push(num);
            sMin.push(num);
        } else if (num < getMin()){ // 如果当前数小于sMin栈的元素
            sData.push(num);
            sMin.push(num);
        } else {
            sData.push(num);
        }
    }
    template<class T>
    T MinStack<T>::pop() {
        if (sData.top() == sMin.top()) {    // 如果sData栈顶元素等于sMin栈顶元素
            sData.pop();
            sMin.pop();
        } else {
            sData.pop();
        }
    }
    
    int main() {
        MinStack<int> s;
    	s.push(5);
    	s.push(3);
    	s.push(2);
    	s.push(4);
    	s.push(6);
    	s.push(3);
    	s.push(1);
    	std::cout << s.getMin() << std::endl;
    	s.pop();
    	std::cout << s.getMin() << std::endl;
    	s.pop();
    	std::cout << s.getMin() << std::endl;
    	s.pop();
    	std::cout << s.getMin() << std::endl;
    	s.pop();
    	std::cout << s.getMin() << std::endl;
    	s.pop();
    	std::cout << s.getMin() << std::endl;
    	s.pop();
    
        return 0;
    }
    
    

    在这里插入图片描述

    4. 参考文章

    1. 【面试题】实现一个栈要求Push,Pop,Min(返回栈中最小值的操作)的时间复杂度为O(1)
    2. 实现带有返回栈中最小元素功能的栈结构
    3. C++ 类模板和模板类
    展开全文
  • 实现链表查找

    2014-09-26 22:30:05
    /* *实现算法查找单链表的倒数第N个元素 *
  •  实现一个具有特殊功能的,首先要具有所要具备的功能,再实现此执行后能够返回栈中最小值的操作。其中pop、push、getMin的操作复杂度都是O(l)。有必要时可以使用现成的站结构操作来设计类型。(pop:弹出...

    功能需求:

            实现一个具有特殊功能的栈,首先要具有栈所要具备的功能,再实现此栈执行后能够返回栈中最小值的操作。其中pop、push、getMin的操作复杂度都是O(l)。有必要时可以使用现成的站结构操作来设计栈类型。(pop:弹出栈顶元素、push:压栈、getMin获取最小栈元素)

    详细解析:

            由于要操作一组数据,并且存入栈中,那么我们首先考虑到的是栈就需要分块,或者我们可以使用两个栈来存储,相比较操作复杂度,我们选用两个栈来操作,这样操作简便。其中一个栈用来保存当前栈中的元素,其 作用就是用来保存数据压栈处理,所以第一个栈可以记作stackData;另一个栈用来保存每弹出一个元素后获取到的最小值保存的栈,所以可以记为stackMin。首先我们可以选择一种复杂但是理解简单的方法来实现。

           【方法一】压栈数据规则:假设当前存储栈弹出的栈元素为newNum,将其压入stackData,然后判断第二个保存栈stackMin是否为空:1.如果为空,将当前的newNum也压入stackMin;2.如果不为空,则比较newNum和stackMin中的栈顶元素哪一个更小;3如果newNum更小或者两个相等,则将newNum也压入stackMin;4.如果stackMin栈顶元素小,则stackMin不压入任何内容。

       例如:我们可以压入一组数据4,5,6,4,2,3,2的过程,其操作如下图:

        数据弹出规则:现在stackData中弹出栈顶元素,记作value。然后比较当前stackMin的栈顶元素和value值哪一个小。通过上面所说的压栈规则可以得出stackMin中存在的最小元素是从栈底到栈顶逐渐变小的,stackMin栈顶元素既是stackMin中的最小值也是当前stackMin中的最小值。所以不会出现value比stackMin的栈顶元素更小的状况,value只可能大于或者等于stackMin中栈顶元素。当value等于stackMin的栈顶元素时,stackMin弹出栈顶元素;当value大于stackMin的栈顶元素时,stackMin不弹出栈顶元素,返回value元素。这与栈的压入与弹出规则是对应的。

        查询当前栈中元素最小值操作: 由压入数据规则和弹出站数据规则,stackMin始终记录这stackData中最小值,所以stackMin中的栈顶始终保存着当前stackData中的最小值。

           【方法二】压入数据规则:假设当前数据为newNum,先将其压入stackData,然后判断stackMin中是否为空,如果为空,则newNum也将压入stackMin;如果不为空,则比较stackMin栈顶值和newNum中的哪一个值更小:1.如果newNum更小或者两个数值相等则newNum也压入stackMin,如果stackMin中栈顶元素小,则stackMin中的栈顶元素重复压入stackMin,既在栈顶元素之上再压入一个栈顶元素。还是上面那个例子,压入一组数据4,5,6,4,2,3,2的过程,如图

    代码实现:

         方法一:

    package com.hekaikai666.test1;
    
    import java.util.Stack;
    
    /**
     * 
     * @author hekaikai666
     * @time 2018年8月22日下午8:29:29
     **/
    public class GetMin {
        // 定义两个栈分别表示这两组数据
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;
    
        /**
         * 构造方法
         */
        public GetMin() {
    	this.stackData = new Stack<Integer>();
    	this.stackMin = new Stack<Integer>();
        }
    
        /**
         * 压栈的方法
         * 
         * @param newNum
         *            压入的数据
         */
        public void push(int newNum) {
    	// 判断栈中是否为空
    	if (this.stackMin.isEmpty()) {
    	    this.stackMin.push(newNum);
    	} else if (newNum <= this.getMin()) {
    	    this.stackMin.push(newNum);
    	} else {
    	    this.stackData.push(newNum);
    	}
        }
    
        /**
         * 弹出栈的方法
         * 
         * @return int 返回此栈中的最小值
         */
        public int pop() {
    	// 判断栈中是否为空
    	if (this.stackData.isEmpty()) {
    	    throw new RuntimeException("Your Stack is Empty~");
    	}
    	// 获取数据栈中弹出栈顶的数据
    	int value = this.stackData.pop();
    	// 数据如果相等,继续弹出
    	if (value == this.getMin()) {
    	    this.stackMin.pop();
    	}
    	// 返回value
    	return value;
        }
    
        /**
         * 判断空栈的方法并且返回此栈顶值
         * 
         * @return int 栈顶值
         */
        public int getMin() {
    	if (this.stackMin.isEmpty()) {
    	    throw new RuntimeException("Your Stack is Empty~");
    	}
    	// 返回栈顶的值
    	return this.stackMin.peek();
        }
    }
    

         方法二:

     

    package com.hekaikai666.test1;
    
    import java.util.Stack;
    
    /**
     * 
     * @author hekaikai666
     * @time 2018年8月22日下午9:00:51
     **/
    public class GetMin2 {
        // 定义两个栈分别表示这两组数据
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;
    
        /**
         * 构造方法
         */
        public GetMin2() {
    	this.stackData = new Stack<Integer>();
    	this.stackMin = new Stack<Integer>();
        }
    
        /**
         * 压栈存储的方法
         * 
         * @param newNum
         *            压入的数据
         */
        public void push(int newNum) {
    	// 判断存入栈是否为空
    	if (this.stackMin.isEmpty()) {
    	    this.stackMin.push(newNum);
    	} else if (newNum < this.getMin()) {
    	    this.stackMin.push(newNum);
    	} else {
    	    // 获取栈顶数据
    	    int newMin = this.stackMin.peek();
    	    // 再次存入栈顶数据
    	    this.stackMin.push(newMin);
    	}
    	// 数据栈弹出栈顶数据
    	this.stackData.push(newNum);
        }
    
        /**
         * 弹出栈的方法
         * 
         * @return
         */
        public int pop() {
    	// 判断数据栈是否还有数据
    	if (this.stackData.isEmpty()) {
    	    throw new RuntimeException("Your Stack is Empty~");
    	}
    	// 存入栈弹出
    	this.stackMin.pop();
    	// 返回弹出的数据
    	return this.stackData.pop();
        }
    
        /**
         * 判断空栈的方法并且返回此栈顶值
         * 
         * @return int 栈顶值
         */
        public int getMin() {
    	// 判断存入栈是否为空
    	if (this.stackMin.isEmpty()) {
    	    throw new RuntimeException("Your Stack is Empty~");
    	}
    	// 返回栈顶的值
    	return this.stackMin.peek();
        }
    }

    总结分析:

            两种方法都是用了两个栈来整理存储数据,方案二比方案一的好在存入栈中数据和数据栈中的数据基本保持一致,把不合法的数据全部保持如合适的数据。都是用stackMin栈保存着stackData每一步的最小值。共同点是操作的复杂度相同都相当于一次遍历O(l),时间复杂度也都为O(n)方案一压栈省空间,但是弹出耗时间,方案二压栈费空间,但是弹出操作省时间。

    完成.......hekaikai666@163.com

    展开全文
  • JVM以方法作为最基本的执行单元,栈帧则是用于支持虚拟机进行方法调用与方法执行背后的数据结构,同样它也是JVM运行时数据区的虚拟机栈元素

    简介

    JVM以方法作为最基本的执行单元,栈帧则是用于支持JVM进行方法调用与方法执行背后的数据结构,同样它也是JVM运行时数据区中的虚拟机栈的栈元素。

    1. 运行时栈帧结构

    每个方法从调用开始到执行结束,都对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。

    栈帧存放了哪些信息?这些信息都存放在哪?
    每个栈帧都包括了局部变量表、操作数栈、动态连接、方法返回地址和一些额外附加信息。在编译Java程序源码时,栈帧需要多大的局部变量表、多深的操作数栈就已经被分析计算出来并写入到方法表的Code属性中。

    方法调用的时候哪个栈帧才是“当前栈帧”?
    假如一个线程的方法调用链很长,同一时刻同一线程中,在调用堆栈的所有方法同时处于执行状态。在执行引擎的角度来说,在活动线程中,只有位于栈顶的方法才是运行的,只有位于栈顶的栈帧才是生效的,被称为当前栈帧,与之关联的方法称为当前方法,执行引擎所运行的所有字节码指令都只针对当前栈帧进行操作。

    下图是虚拟机栈与栈帧的总体结构,接下来我们来一起学习栈帧中的局部变量表、操作数栈、动态连接、方法返回地址等各部分的作用和数据结构。

    栈帧的概念结构

    1.1 局部变量表

    局部变量表是一组变量值的存储空间,用于存放方法参数和方法内部定义的局部变量。

    方法体里面的代码经过javac编译器处理之后,最终变为字节码指令存储在Code属性内,Code属性出现在方法表的属性集合中(接口或抽象类中的方法不存在Code属性),在Code属性max_locals数据项中确定了该方法所需分配的局部变量表的最大容量。

    如下列举了方法表结构及属性表中Code属性的结构:

    方法表结构
    类型名称数量
    u2access_flags(访问标志位)1
    u2name_index(字段简单名称)1
    u2descriptor_index(描述符)1
    u2attributes_count(属性表存在个数)1
    attribute_info(属性表)attributesattributes_count
    属性表结构
    类型名称数量
    u2attribute_name_index1
    u4attribute_length1
    u1infoattribute_length
    Code属性表结构
    类型名称数量
    u2attribute_name_index
    固定“Code”
    1
    u4attribute_length
    属性表长度
    1
    u2max_stack
    操作数栈最大深度
    1
    u2max_locals
    局部变量表所需存储空间
    1
    u4code_length
    字节码长度
    1
    u1code
    存储字节码指令的字节流
    code_length
    u2exception_table_length1
    exception_infoexception_tableexception_table_length
    u2attributes_count1
    attribute_infoattributesattributes_count

    局部变量表的容量max_locals以变量槽(Slot)为最小单位,对于对于bytecharfloatintshortbooleanreturnAddress等长度不超过32位的数据类型,每个局部变量占用一个变量槽,而doublelong这两种64位的数据类型则需要两个变量槽来存放,最后一种为reference类型。

    局部变量表是线程安全?
    局部变量表是建立在线程堆栈中的,属于线程私有的数据。

    reference数据类型用于存储什么?有什么作用?
    reference表示对一个对象实例的引用,《Java虚拟机规范》没有规定其长度也为明确应该是什么数据结构。虚拟机主要通过reference做两件事:

    1. 根据引用直接或间接地查找对象在Java堆中数据存放的起始地址或索引。
    2. 根据引用直接或间接地查找到对象所属数据类型在方法区中的存储的类型信息。

    局部变量表具体存放哪些信息呢?
    方法参数(包括实例方法中的隐式参数this)、显示异常处理参数(try-catch()中定义的异常)、方法体中定义的局部变量。

    方法调用时局部变量表的工作过程:
    方法被调用时,JVM会使用局部变量表来完成参数值到参数变量列表的传递过程,即实参到形参的传递:如果执行的是实例方法(没有static修饰的方法),局部变量表中第0位索引的变量槽默认是用于传递方法所属对象实例的引用,其余参数按照参数表顺序排列,占用从1开始的局部变量槽,参数表分配完毕之后,再根据方法内部定义的变量顺序和作用域分配其余的变量槽。

    max_locals的值是方法中的局部变量所占变量槽数之和吗?
    答案是否定的,操作数栈和局部变量表直接决定该方法的栈帧耗费的内存,不必要的操作数栈深度和变量槽数量会造成内存浪费。JVM的做法是将局部变量表中的变量槽进行重用,当代码执行超出一个局部变量的作用域时,这个局部变量所占的变量槽可以被其他局部变量所使用,Javac编译器会根据变量的作用域来分配变量槽给各个变量使用,根据同时生存的最大局部变量数量和类型计算出max_locals的大小。

    1.2 操作数栈

    也称为操作栈,它是一个后入先出(LIFO)栈。

    操作数栈的最大深度在编译时写入到Code属性的max_stacks数据项之中。操作数栈的每一个元素都可以是包括long和double在内的任意Java数据类型。Javac编译器的数据流分析工作保证了在方法执行时,操作数栈的深度都不会超过在max_stacks数据项中设定的最大值。

    方法调用时操作数栈的工作过程:
    方法开始执行时,该方法的操作数栈是空的,执行过程中,字节码指令向操作数栈中写入和提取内容,即出栈和入栈操作。 例如字节码指令iadd,在运行时要求操作数栈中最接近栈顶的两个元素已经存入了两个int型的数值,当执行这个指令时,两个int值出栈并相加,然后将相加的结果重新入栈。

    1.3 动态连接

    Class文件的常量池中存有大量的符号引用,字节码中的方法调用指令就以常量池里指向方法的符号引用作为参数。这些符号引用一部分会在类加载阶段或者第一次使用的时候就被转化为直接引用,这种转化被称为静态解析。另外一部分将在每一次运行期间都转化为直接引用,这部分就称为动态连接

    每个栈帧都包含一个指向运行时常量池中该栈帧所属方法的引用,持有这个引用是为了支持方法调用过程中的动态连接。

    1.4 方法返回地址

    当方法开始执行后,只有两种方式退出这个方法:

    1. 当执行引擎遇到任意方法返回的字节码指令,称为“正常调用完成” 。
    2. 在方法执行的过程中遇到异常且异常没有在方法体内得到妥善处理,称为“异常调用完成 ”。

    方法退出后,都必须返回到方法被调用时的位置,方法返回时可能需要在栈帧中保存一些信息,用来帮助恢复它的上层主调方法的执行状态。一般情况下,方法正常调动完成,调用者的PC计数器的值就可以作为返回地址,栈帧中很可能会保存这个计数器值。 方法异常调用完成, 则反之。

    参考

    《深入理Java虚拟机》周志明

    展开全文
  • (5)、获取栈中元素个数 (6)、判空 (7)、扩容 (8)、销毁 代码如下: #include"stack.h" #include<assert.h> #include<malloc.h> #include<stdio.h> //初始化 void StackInit(Stack* ps) ...
  • 构造一个结构,其中需要实现一个方法,该方法 getmin,返回栈中的最小的元素。要求: 时间复杂度为o(1)。分析: 之前我写过了用python写一个数据结构,代码这里: 队列和的Python实现这里,需要以...
  • 已知一个int 类型结构stack<int > s 要求删除栈中第position(从0开始)位置的值,并返回该值。
  • O(1)时间求栈中最小(大)元素

    千次阅读 2014-09-06 09:53:28
    难点在于怎么维持stack的最小(大)值,一切排序和查找都不可能实现O(1)的时间复杂度找到最小值。 思路:如下图所示,以空间换取时间。通过增加一个最小值来存储上一个最小值,以维持目前的最小值。 1、 ...
  • 进栈时,若当前的元素小于之前的最小元素,则把当前元素记录进该元素的最小元素中,并输出更改最小元素的信息。 出栈时,若当前的最小元素小于出栈后中的最小元素,则输出更改最小元素的信息。 代码如下: ...
  • 常数时间内查找栈中最小的元素

    千次阅读 2018-06-09 10:49:17
    import java.util.Stack;... * @Description 栈中最小的元素 */ public class MinStack &lt;E extends Integer&gt;{ private Stack&lt;E&gt; minStack=new Stack&lt;E&gt;(); ...
  • 查找栈中最小值

    2018-07-20 13:45:34
     定义的数据结构,请该类型实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。 二、解题思路   三、注意事项   四、代码实现  见我的github:查找栈中最小值...
  • 2250: 查找最小的k个元素和队列)   题目描述 题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4 输入 输入: 8 4 1 2 3 4 5 6 7 8 输出...
  • 的最小值查找(O1)

    千次阅读 2017-01-05 00:57:17
    增加一个获取最小值的方法(getMin),要求, 时间复杂度为O(1)。 错误的解决思路 定义一个minIndex,存储最小值的下标。 每次push的时候比较大小, 如果小于最小值,则minIndex修改为当前下标, 否则不...
  • 相关算法

    千次阅读 2018-11-02 20:29:52
    设计一个支持 push,pop,top 操作,并能常数时间内检索到最小元素。 push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。 ...
  • c++中栈stack的几个常用函数

    千次阅读 2021-02-03 22:26:13
    是一种只能后入先出的容器,因此只有通过top来访问栈顶元素 1、top() 代码示例: #include <iostream> #include <string> #include<algorithm> #include<bits/stdc++.h> #include<...
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    一个集合代表一组对象,这些对象即为它的元素。Java 平台不提供这个接口任何直接的实现。 Set ,是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。 List ,是一个有序...
  • 本文主要介绍了如下的基本操作 初学者可参考 包括构造 销毁 置为空栈 初始 查找栈顶元素 删除栈顶元素底到栈顶依次访问栈中每个元素
  • 和队列java的实现

    千次阅读 2013-10-29 08:26:27
    和队列java的实现
  • 遍历一遍这个,这样肯定超了,面试完回来之后,我思考了一段时间,网上了解了一下,得出一个解题思路 想要找出最大的数,且时间复杂度为O(1),那么就一定要知道这个最大的数哪放着,那么我们就可以一次性的...
  • 2021年前端面试题及答案

    万次阅读 多人点赞 2020-02-11 19:29:34
    前端面试汇总(2020年) 一 大纲 1、前言 2、前端工程化 3、前端设计模式 ...9、前端技术问题 ...由于新冠肺炎疫情,现在成天呆家里,加上也要准备面试,就家里看面试题...
  • js面试题

    千次阅读 多人点赞 2019-04-09 19:42:32
    e.getAttribute(),是标准 DOM 操作文档元素属性的方法,具有通用性可任意文档上使用,返回元素在源文件设置的属性 e.propName 通常是 HTML 文档访问特定元素的特性,浏览器解析元素后生成对应对象(如 a ...
  • 集合

    千次阅读 多人点赞 2019-04-28 20:25:50
    集合1 集合概念2 集合特点3 集合的功能4 集合的遍历5 1 集合概念 2 集合特点 3 集合的功能 集合的增删查包含 ...//清空集合所有的元素 boolean remove();//删除一个元素 boolean removeAll();...
  • 与队列 -- 增、查、改、删操作

    千次阅读 2018-10-01 16:10:37
    顺序1) 定义2) 初始化3) 判断空4) 进栈5) 出栈6) 简化操作02、 链栈1) 链栈结点定义2) 初始化链栈3) 判断空4) 进栈(头插法)5) 出栈3. 队列01. 顺序队列假溢出问题:解决办法:1) 初始化队列2) 判断队空3)...
  • 【前言】学习Java编程一段时间,对于一些涉及业务逻辑的案例没有太多的机会接触;闲的时候添加了很多群,里面有很多涉及...言归正传,昨晚看到一个有关出栈入栈并获取栈中最小值的案例,机会难得,用java代码实现了下。
  • 什么是数据结构?

    千次阅读 2019-06-19 20:25:39
    什么是数据结构?数据结构是什么? 数据结构是计算机存储、组织数据的方式...数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合数据元素之间的关系组成。也就是说,数组结构指的是数据集合及...
  • 数据结构

    千次阅读 多人点赞 2018-10-06 17:40:36
    数据结构是指相互之间存在一种或者多种特定关系的数据元素集合。通常情况下,精心选择的数据结构可以带来更高效的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 数据结构是ADT(抽象数据类型)的...
  • Java 集合深入理解(13):Stack

    千次阅读 2016-10-23 13:25:32
    数据结构数据结构是一种线性数据结构,遵从 LIFO(后进先出)的操作顺序,所有操作都是顶部进行有点像羽毛球筒:通常有三种操作: push 入栈 pop 栈顶元素出栈,并返回 peek 获取栈顶元素,并不...
  • C++ STL 知识点总结

    千次阅读 多人点赞 2019-01-13 18:22:29
    简单介绍:C++ STL(标准模板库)是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列、等。 STL的一个重要特点就是数据结构...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 122,682
精华内容 49,072
关键字:

如何在栈中查找元素