栈、队列、堆随笔

1/ Leetcode 225 使用队列实现栈

1. 队列的初始化: Queue是接口,队列由链表实现 : Queue<> q = new LinkedList<>();

2.Queue的基本使用方法:

  • offer        添加一个元素并返回true        如果队列已满,则返回false   
  • poll          移除并返问队列头部的元素    如果队列为空,则返回null   
  • peek        返回队列头部的元素              如果队列为空,则返回null
class MyStack {
    private Queue<Integer> a;
    private Queue<Integer> b;

    /** Initialize your data structure here. */
    public MyStack() {
        a = new LinkedList<Integer>();
        b = new LinkedList<Integer>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        b.offer(x);
        while(!a.isEmpty())
        {
            b.offer(a.poll());
        }

        Queue<Integer> temp;
        temp = b;
        b = a;
        a = temp;

   }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return a.poll();
    }

    /** Get the top element. */
    public int top() {
        return a.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return a.isEmpty();

    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

2/Leetcode 232用栈实现队列

1.Stackh是类 直接初始化

2.基本操作

* push : 把项压入堆栈顶部 ,并作为此函数的值返回该对象
* pop : 移除堆栈顶部的对象,并作为此函数的值返回该对象
* peek : 查看堆栈顶部的对象,,并作为此函数的值返回该对象,但不从堆栈中移除它
* empty : 测试堆栈是否为空

class MyQueue {

    private Stack<Integer> stack;
    private Stack<Integer> a;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack = new Stack<>();
        a = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        while(!stack.empty())
        {
            a.push(stack.pop());
        }
        stack.push(x);
        while(!a.empty())
        {
            stack.push(a.pop());
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack.pop();
    }

    /** Get the front element. */
    public int peek() {
        return stack.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

3/Leetcode 255 设计最小栈

思路:设计一个同步的对照栈,记录栈所有状态下的最小值。

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> stackmin;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
        stackmin = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(!stackmin.empty())
        {
            if(stackmin.peek()<x)
            {
                stackmin.push(stackmin.peek());
            }
            else
            {
                stackmin.push(x);
            }
        }
        else
        {
            stackmin.push(x);
        }
    }

    public void pop() {
        stack.pop();
        stackmin.pop();

    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return stackmin.peek();

    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

4/Leetcode 946 验证栈序列

1. 构造辅助栈。将pushed序列推入栈中,比较栈顶元素与popped数组。相同时弹出

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> s = new Stack<>();
        int index = 0;
        for(int i=0;i<pushed.length;i++)
        {
            s.push(pushed[i]);
            while(!s.empty()&&s.peek()==popped[index])
            {
                index++;
                s.pop();
            }
        }
        if(s.empty())
        {
            return true;
        }
        else return false;
    }
}

4/Leetcode 224 基本计算器 经典的栈应用

。。。。。好难md

5/Leetcode 215  数组中第K个最大元素

快排

原文地址:https://www.cnblogs.com/luiyuying/p/12702415.html

时间: 04-14

栈、队列、堆随笔的相关文章

栈&amp;队列&amp;堆

栈:一种只能在一端进行插入和删除的特殊线性表,按照先进后出的方式组织数据,先进入的数据被压入栈底,最后的数据被压入栈顶,需要读取数据时从栈顶开始弹出数据 队列:一种只能在一端进行数据的插入及另一端进行数据的删除的特殊线性表,按照先进先出的方式组织数据 堆:N个元素{k1, k2, k3, k4, k5, k6 ... kn}组成的集合,若满足下列关系之一则可称之为堆: ki <= k2i 且 ki <= k2i+1, (i = 1, 2, 3 ... n/2) ki >= k2i 且 k

理解 &quot;栈&quot; &quot;队列&quot;,&quot;堆&quot;(后进先出)

[栈] ??函数调用形成了一个栈帧 function foo(b) { var a = 10; return a + b + 11; } function bar(x) { var y = 3; return foo(x * y); } console.log(bar(7)); 当调用bar时,创建了第一个帧 ,帧中包含了bar的参数和局部变量.当bar调用foo时,第二个帧就被创建,并被压到第一个帧之上,帧中包含了foo的参数和局部变量.当foo返回时,最上层的帧就被弹出栈(剩下bar函数的调

【C/C++学院】0828-STL入门与简介/STL容器概念/容器迭代器仿函数算法STL概念例子/栈队列双端队列优先队列/数据结构堆的概念/红黑树容器

STL入门与简介 #include<iostream> #include <vector>//容器 #include<array>//数组 #include <algorithm>//算法 using namespace std; //实现一个类模板,专门实现打印的功能 template<class T> //类模板实现了方法 class myvectorprint { public: void operator ()(const T &

栈和队列的区别,栈和堆的区别

栈和队列的区别: 栈的插入和删除操作都是在一端进行的,而队列的操作却是在两端进行的. 栈是先进后出,队列是先进先出. 栈只允许在表尾一端进行插入和删除,队列只允许在表尾一端进行插入,在表头一端进行删除. 栈和堆的区别: 栈区:由编辑器自动分配释放,存放函数的参数值,局部变量的值等(基本类型值). 堆区:由程序员分配释放,若程序员不释放,程序结束时可能有OS回收(引用类型值). 栈(数据结构):一种先进后出的数据结构. 堆(数据结构):堆可以被看成是一棵树,如:堆排序. 原文地址:https://

前端进击的巨人(二):栈、堆、队列、内存空间

面试经常遇到的深浅拷贝,事件轮询,函数调用栈,闭包等容易出错的题目,究其原因,都是跟JavaScript基础知识不牢固有关,下层地基没打好,上层就是豆腐渣工程,新人小白,踏实踩土才是关键. 打地基第二篇:本篇我们将对JavaScript数据结构的知识点详解一二. JavaScript中有三种数据结构: 栈(stack) .堆(heap). 队列(queue). 栈(stack) 栈的特点是"LIFO,即后进先出(Last in, first out)".数据存储时只能从顶部逐个存入,取

数据结构学习笔记-排序/队/栈/链/堆/查找树/红黑树

排序: 插入排序:每次从剩余数据中选取一个最小的,插入已经排序完成的序列中 合并排序:将数据分成左右两组分别排序,然后合并,对每组数据的排序递归处理. 冒泡排序:重复交换两个相邻元素,从a[1]开始向a[0]方向冒泡,然后a[2]...当a[i]无法继续往前挤的时候说明前面的更小了,而且越往前越小(挤得越往前) 堆排序:构造最大堆,每次取走根结点(自然是最大的),再调用MAX-HEAPIFY算法(见后文的堆)恢复最大堆的性质,重复取走根结点 快速排序(对A[r]-A[n]进行排序): 1.从序列

.Net栈和堆详解

什么是栈堆 在计算机领域,堆栈是一个不容忽视的概念,栈堆是两种数据结构.堆栈都是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除.要点:堆,队列优先,先进先出(FIFO—first in first out):栈,先进后出(FILO—First-In/Last-Out). 堆栈是一个在计算机科学中经常使用的抽象数据类型.堆栈中的物体具有一个特性: 最后一个放入堆栈中的物体总是被最先拿出来, 这个特性通常称为后进先出(LIFO)队列. 栈和堆的区别 堆栈空间分配

浅谈“栈和堆”

对于一些新人可能会不理解栈和堆是什么,在这里我简单介绍一下: 程序运行时,它的数据必须存储在内存中.一个数据项需要多大的内存.存储在什么地方.以及如何存储都依赖与该数据项的类型. 运行中的程序使用两个内存区域来存储数据:栈和堆. 首先,什么是“栈”? 栈是一个内存数组,是一个LIFO(last-in  first-out,后进先出)的数据结构.栈存储几种类型的数据: 某些类型变量的值 程序当前的执行环境 传递给方法的参数 栈的特征: 栈有如下几个普遍特征: 数据只能从栈的顶端插入和删除 把数据放

成员变量,局部变量,栈,堆的关系

变量主要有类变量.成员变量.局部变量三种. 变量主要有类变量.成员变量.局部变量三种. 类变量的的格式如下 class ClassA: static int age; 也就是说,类变量是定义在类中(而不是方法中)并且有static 修饰的变量. 成员变量的格式如下: class ClassB: int age; 也就是说,成员变量是定义在类中,但是没有static 修饰的变量. 局部变量呢,则是定义在方法中的(注意:JAVA中不怎么用函数这种说法的).比如最常见的. class ClassC:

JAVA中的栈和堆

JAVA在程序运行时,在内存中划分5片空间进行数据的存储.分别是:1:寄存器.2:本地方法区.3:方法区.4:栈.5:堆. 基本,栈stack和堆heap这两个概念很重要,不了解清楚,后面就不用学了. 以下是这几天栈和堆的学习记录和心得.得些记录下来.以后有学到新的,会慢慢补充. 一.先说一下最基本的要点 基本数据类型.局部变量都是存放在栈内存中的,用完就消失.new创建的实例化对象及数组,是存放在堆内存中的,用完之后不定期自动消除. 二.先明确以上两点,以下示例就比较好理解了 示例1 main