（一）栈和队列的基本性质栈是先进后出的队列是先进先出的栈和队列在实现结构上可以有数组和链表两种形式数组结构实现较容易用链表结构较复杂，因为牵扯很多指针操作（二）队列和栈的基本操作pop操作（栈尾弹出一个元素）push操作（栈/队列尾加入一个元素）shift操作（队头弹出一个元素）栈和队列的基本操作，都是时间复杂度都为O(1)的操作（三）深度优先遍历（DFS）和宽度优先遍历（BFS）深度优先遍历可以用栈实现宽度优先遍历可以...
一般的dijkstra算法利用贪心的思想，每次找出最短边，然后优化到该点的的距离，我们还采用贪心思路，但在寻找最短边进行优化，之前是双重for循环，现在我们用优先队列来实现。代码解释：//样例程序采用边表储存。 #include<cstdio>#include<queue>#include<cstring>#include<cmath>#include<iostream>using namespace std;int head[100000]={0},next[200000]={0},aa[200000]={0},size,s,tt,m,n;struct bb { int x,y; }a[1000...
单调队列：队列中元素单调递增或递减，可以用双端队列实现（deque），队列的前面和后面都可以入队出队。单调队列优化dp：问题引入：dp[i] = min( a[j] ) ，i-m < j <= i普通的做法是O(nlogn)，但是当n很大是，这个复杂度就不行了，考虑用单调队列优化来达到O(n)。单调队列优化dp时维护的一般都是两个值{ id（下表），value（值）}，且它们都保持单调。对于这个问题，我们维护一个两个值都单调递增的序列。查询：队首不断删除，直到...
下压堆栈(链表实现)：import java.util.Iterator;public class LinkedStack<Item> implements Iterable<Item>
{public class Node{Item item;Node next;}private Node frist;private int N = 0;public boolean isEmpty(){return N == 0;}public int size(){return N;}public void push(Item item){Node oldFrist = frist;frist = new Node();frist.next = oldFrist;frist.item = item;N++;}public Item pop(){Item item = frist.it...
算法：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。《剑指offer》利用栈来进行操作，代码注释写的比较清楚：首先判断两个栈是否是空的：其次当栈二 为空，将栈1中取出来放到栈二，最终返回栈二首部值；主要利用了pop（）方法和push方法：package LG.nowcoder;/*** @Author liguo* @Description 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。* @Data 2018-08-11 21:5...
栈（stack）栈（stack）是一种后进先出（LIFO）的集合类型， 即后来添加的数据会先被删除 可以将其类比于下面文件的取放操作：新到的文件会被先取走，这使得每次取走的文件都是最新的。 栈可以用数组或者队列去实现下面要实现的栈的API如下图所示： 用数组实现栈下面我们通过数组实现一个指定了初始容量，但随着元素的增加能够动态地扩张容量的栈。注意： 因为数组指定大小后不可改变， 所以我们要定义自动扩大栈容量的操作pub...
1.链队列。利用带有头结点的单链表来实现链队列,插入和删除的复杂度都为o(1)代码：#include<stdio.h>
#include<stdlib.h>typedef struct Qnode
{
int data;
Qnode *next;
}Qnode;
typedef struct LinkQueue
{Qnode *front;Qnode *rear;
}LinkQueue;void initialize(LinkQueue *LinkQueue)
{LinkQueue->rear=(Qnode*)malloc(sizeof(Qnode));LinkQueue->front=LinkQueue->rear;LinkQueue->front->next=NULL;
}void ENQUEUE(LinkQue...
一、简介众所周知，线性表是数据结构的基础，通常有两种实现方式：数组和链表。栈和队列是最常用的数据结构，它们基于线性表实现。 二、栈定义：栈是限定仅在表尾进行插入和删除操作的线性表，即FILO。栈被经常类比于弹夹，即先被压如弹夹的子弹最后被打出。根据线性表的实现方式得知，栈的实现方式有两种：数组实现和链表实现。 栈的数组实现：package basic.data_structure.cha01;/*** 栈：先进后出（FILO），只允许在栈顶操作元...
题目链接：https://www.acwing.com/problem/content/description/151/给定长度为n的序列，代表一个单词的出现次数，要求构造k叉哈夫曼树使得总权值最小，并且在权值最小的情况下问最小的高度是多少？我们可以考虑不断取k个数组成一个新的结点放入优先队列，但是根节点可能不满k叉，所以可以考虑在其中不超过k-1个零来上调权值比较大的结点，权值为零的结点肯定在最深层的一个父节点上。也只有这一个父节点是不满k叉的，这个可以通过...
1、堆排序的堆，其实是一个 完全二叉树。既是一个结点要么是叶子结点，要么必定有左右两个子节点的树。2、堆有序：每个结点的值，都必须大于两个子节点。但是两个子结点的大小不作要求。3、一棵大小为N的完全二叉树，高度为lgN（层）。 用数组实现堆，假设数组下标从0开始，下标为k的元素，它的左子树是2k+1，右子树是左子树+1，即2k+2 一：由上至下的有序化（下沉）如果堆的有序状态，因为某个结点比它的两个子结点或者其中之一小...
最小支撑树树--Prim算法，基于优先队列的Prim算法，Kruskal算法，Boruvka算法，“等价类”UnionFind 最小支撑树树前几节中介绍的算法都是针对无权图的，本节将介绍带权图的最小支撑树(minimum spanning tree)算法。给定一个无向图G，并且它的每条边均权值，则MST是一个包括G的所有顶点及边的子集的图，这个子集保证图是连通的，并且子集中所有边的权值之和为所有子集中最小的。本节中介绍三种算法求解图的最小生成树：Prim算法、Kr...
前几天写的。。 1package gh;2 3import java.util.Iterator;4 5/** 6 * 泛型双向队列（双向链表实现）7 * @author ganhang8 *9*/ 10publicclass Deque<T> implements Iterable<T> {11private Node first;12private Node last;13privateint n=0;14public Deque(){15 16 }17//从左边加入 18publicvoid pushLeft(T item) {19if (first == null) {20 first=new Node(item); 21 last=first;22 ...
一、题目：有一个序列u，满足：1. 第一个元素是12. 此后任意一个元素x，2x+1和3x+1也必定在u中现给定整数n，求序列u中的第n个元素是什么？并输出该序列规定：要注意算法的效率二、分析先找几个数计算一下：1[1], 3, 41, [3], 4, 7, 101, 3, [4], 7, 9, 10, 13其中这个9提醒我们，虽然单纯的2x+1或3x+1一定是递增的，但是前一个数的3x+1有可能大于后一个数的2x+1。因此，当要在序列u中取“下一个数”计算它的2x+1和3x+1时，如何选取...
2269: minval
时间限制: 3 Sec 内存限制: 256 MB提交: 638 解决: 65[提交][状态][讨论版][命题人:外部导入]题目描述有两个长度为N的序列A和B，在A和B中各任取一个数相加可以得到N2个和，求这N2个和中最小的N个。
输入第一行输入一个正整数N（1<=N<=100000）；
第二行N个整数Ai且Ai<=109；第三行N个整数Bi且Bi<=109。
输出输出仅一行，包含n个整数，从小到大输出这n个最小的和，相邻数字之间用空格隔开。
样例输入5
1 3 2 4 5
...
课本源码部分第3章 栈和队列 - 迷宫寻路——《数据结构》-严蔚敏.吴伟民版 源码使用说明 链接??? 《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明 课本源码合辑 链接??? 《数据结构》课本源码合辑 习题集全解析 链接??? 《数据结构题集》习题解析合辑 本源码引入的文件 链接? Status.h、SequenceStack.c 相关测试数据下载 链接? 无数据 文档中源码及测试数据存放...