正文

<<编程之美>> -- 队列中取最大值操作的问题

IP云
IP云V管理员/2 阅读
10/01
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

不得不说编程之美是一本好书，虽然很多题目在做acm中的过程中遇到过，不过还是有很多值得思考的地方

这是今天在编程之美上看到的一个问题，对于栈转化成队列的一个思考

平时都太过依赖c++内函数库中的栈和队列，但是对于他们的扩展我们还是应该自己进行手写栈和队列来实现更简单的算法

题目大意：

假设有这样一个拥有3个操作的队列:

1. EnQueue(v) : 将 v 加入队列

2. DeQueue: 使队列中队首元素删除并返回此元素

3.MaxElement: 返回队列中的最大元素

设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能地低

首先来思考这样一个问题：

对于前面已知的一段序列，我们加入一个元素x，得到当前序列的最大值会特别容易

maxVal[i] = max(maxVal[i-1] , x);

那么我们删掉第 i 个元素，得到的序列中的最大值也特别容易就是maxVal[i-1]

换个角度想想此时的第 i 个元素可理解为栈顶元素

也就是说这道题目改成拥有3个栈操作的队列那么我们直接就可以在单位时间内得到MaxElement

而保存这些数也就是把所有数扫一遍，O(N)就解决了

但是这里是队列，队列总是删去最前面也就是下标为 0 的元素，这样我们无法利用maxVal[i]来表示当前队列元素中的最大值

那我们可以考虑，既然栈如此方便，如何将队列用栈来表示

首先我们需要两个栈，把数据放入一个栈s2，那么这些数据其实是倒着保存的 ， 那么我们要删去队列的首元素，也就是删除栈底的元素，

那么我们可以利用另一个栈s1，将前一个栈s2中的元素再倒一遍进入另一个栈s1,那么此时s1的栈顶也就是队列的栈顶

也就是说只要s1中有元素，那么s1中的栈顶始终是队列首元素

只有当s1中元素都不存在时，才将s2中的元素一次性全倒入s1

int DeQueue()
    {
        if(s1.empty() && s2.empty()) return -INF; //队列中值不存在
        if(s1.empty()){
            while(!s2.empty()){
                s1.push(s2.pop());
            }
        }
        return s1.pop();
    }

那么队列中的所有元素总是分布在s1和s2中，那么最大元素既可能在s1,也可能在s2中，所以返回 return max(s1.Max() , s2.Max());

这样这个程序总的复杂度就能够达到O(N)的线性复杂度了

接下来是自己手写的一个测试过的没有问题的程序

#include <cstdio>
#include <cstring>
#include <exception>
using namespace std;
#define max(a,b) a>b?a:b
const int MAXN = ;
const int INF = 0x3fffffff;
struct Stack{
int top , a[MAXN] , maxVal[MAXN];
//a[]保存栈中的元素，maxVal[i]保存i以及前方的最大值，top为栈顶指针，初始为-1
Stack(){
top = -;
memset(maxVal , - , sizeof(maxVal));
}
void push(int x)
{
if(top>=MAXN) throw exception();
a[++top] = x;
if(top == ) maxVal[top]=x;
else maxVal[top] = max(maxVal[top-] , x);
}
bool empty(){return top == -;}
int Max()
{
if(empty()) return -INF;
return maxVal[top];
}
int pop()
{
if(top<) return -;
int ret = a[top--];
return ret;
}
}; struct Queue{
Stack s1 , s2;
Queue()
{
s1 = Stack();
s2 = Stack();
}
void EnQueue(int x)
{
s2.push(x);
}
int DeQueue()
{
if(s1.empty() && s2.empty()) return -INF; //队列中值不存在
if(s1.empty()){
while(!s2.empty()){
s1.push(s2.pop());
}
}
return s1.pop();
}
int MaxElement()
{
return max(s1.Max() , s2.Max());
}
bool empty()
{
return s1.empty()&&s2.empty();
}
}; int main()
{
// freopen("a.in" , "r" , stdin);
Queue q; q = Queue();
// int num[10] = {5 , 7 , 6 , 3 , 2 , 4 , 9 , 15 , 13 , 11};
q.EnQueue();
int op , x;
while(!q.empty())
{
printf("输入操作类型：");
scanf("%d" , &op);
if(op == ){
printf("输入一个数入队列：");
scanf("%d" , &x);
q.EnQueue(x);
}
else if(op == ){
printf("队列首元素 %d 从队列中退出\n" , q.DeQueue());
}
else{
printf("当前队列最大元素为 %d\n" , q.MaxElement());
} //下方每次用来检测队列中两个栈的数据保存情况
/*
printf("输出栈1中的元素\n");
for(int i=q.s1.top ; i>=0 ; i--){
printf("%d " , q.s1.a[i]);
}
puts(""); printf("输出栈2中的元素\n");
for(int i=q.s2.top ; i>=0 ; i--){
printf("%d " , q.s2.a[i]);
}
puts("");
*/
}
return ;
}

<<编程之美>> -- 队列中取最大值操作的问题的更多相关文章

  1. 编程之美 set 10 队列中取最大值操作问题

    题目 假设有这样一个拥有三个操作的队列 1. Enqueue(v) 2. Dequeue() 3. MaxEle() 请设计一种数据结构和算法, 让 MAXELE 操作的时间复杂度尽可能的低 思路 1 ...

  2. 在含有null值的复杂类的集合&lpar;Collection&rpar;中取最大值

    在日常编程中,经常遇到要在一组复杂类的集合(Collection)中做比较.取最大值或最小值. 举个最简单的例子,我们要在一个如下结构的集合中选取包含最大值的元素: public class Clas ...

  3. Java并发编程：阻塞队列&lpar;转载）

    Java并发编程:阻塞队列 在前面几篇文章中,我们讨论了同步容器(Hashtable.Vector),也讨论了并发容器(ConcurrentHashMap.CopyOnWriteArrayList), ...

  4. 【转】Java并发编程：阻塞队列

    在前面几篇文章中,我们讨论了同步容器(Hashtable.Vector),也讨论了并发容器(ConcurrentHashMap.CopyOnWriteArrayList),这些工具都为我们编写多线程程 ...

  5. Java并发编程：阻塞队列 &lt&semi;转&gt&semi;

    在前面几篇文章中,我们讨论了同步容器(Hashtable.Vector),也讨论了并发容器(ConcurrentHashMap.CopyOnWriteArrayList),这些工具都为我们编写多线程程 ...

  6. 12、Java并发编程：阻塞队列

    Java并发编程:阻塞队列 在前面几篇文章中,我们讨论了同步容器(Hashtable.Vector),也讨论了并发容器(ConcurrentHashMap.CopyOnWriteArrayList), ...

  7. （转）Java并发编程：阻塞队列

    Java并发编程:阻塞队列 在前面几篇文章中,我们讨论了同步容器(Hashtable.Vector),也讨论了并发容器(ConcurrentHashMap.CopyOnWriteArrayList), ...

  8. linux编程之消息队列

    消息队列是内核地址空间中的内部链表,通过linux内核在各个进程之间传递内容,消息顺序地发送到消息队列中,并且以几种不同的方式 从队列中获取,每个消息队列可以用IPC标识符唯一的进行标识,内核中的消息 ...

  9. JUC 并发编程--06&comma; 阻塞队列&lpar;7种&rpar;&comma; 阻塞等待 api的 代码验证

    这些队列的 api ,就是添加队列,出队列,检测对首元素, 由于 add()--remove(), offer()--poll(),太简单这里不做验证, 只验证后二组api: 阻塞等待( put()- ...

随机推荐

  1. Oracle 11g新特性延迟段创建和truncate的增强

    下面测试Oracle 11g开始的新特性truncate的增强和延迟段空间创建. Oracle从11g开始,当用户创建一张空表的时候不会先分配段和空间,只有当对这张表插入第一行数据的时候才分配段和空间 ...

  2. 根据地图上的两个点各自的x&comma;y坐标，计算出2点之间的直线距离。显示为公里、米

    /** * calc_map_distance() , 根据地图上的两个点各自的x,y坐标,计算出2点之间的直线距离 * @param array $point_1 第1个点的x,y坐标 array( ...

  3. JAVA定义接口格式&colon;

    [public]interface 接口名称 [extends父接口名列表] { //静态常量 [public] [static] [final] 数据类型变量名=常量值; //抽象方法 [publi ...

  4. 自动更新开奖数据的excel文件，供大家下载

    自动更新开奖数据的excel文件,供大家下载 2010-03-14 20:22 228492人阅读打印来源:乐彩网 作者:eren 很多人拥有自制excel电子表格,常要更新最基本的开奖信息.如有多期 ...

  5. 做了一个简易的git 代码自动部署脚本

    做了一个简易的git 代码自动部署脚本 http://my.oschina.net/caomenglong/blog/472665 发表于2个月前(2015-06-30 21:08)   阅读(200 ...

  6. Confluent

    Confluent介绍(一)   最开始接触confluent是通过这篇博客,How to Build a Scalable ETL Pipeline with Kafka Connect,对于做大数 ...

  7. VARCHAR2 他们占几个字节&quest; NLS&lowbar;LENGTH&lowbar;SEMANTICS&comma;nls&lowbar;language

    ORACLE初始化参数:NLS_LENGTH_SEMANTICS 初始化參数NLS_LENGTH_SEMANTICS用于指定CHAR列或VARCHAR2列的长度定义方式,默认值为BYTE. 当设置该參 ...

  8. css 绝对居中

    我是一个前端的菜鸟,对于绝对居中前几天也困惑了我不少时间,今天我就把我知道的两个方法写出来,希望能记住也希望帮助到和我一样刚接触前端不久的同学. 第一种是 你需要居中的元素有固定的宽高: 首先给他的父 ...

  9. 全文搜索引擎——Solr

    1.部署solr a.下载并解压Solr b.导入项目(独立项目): 将解压后的 server\solr-webapp 下的 webapp文件夹 拷贝到tomcat的webapps下,并重命名为 so ...

  10. SPOJ 10570 LONGCS - Longest Common Substring

    思路 和SPOJ 1812 LCS2 - Longest Common Substring II一个思路,改成多组数据就有三倍经验了 代码 #include <cstdio> #inclu ...