文档章节

用stack做队列求最大值

颜建海
 颜建海
发布于 2014/04/22 00:20
字数 175
阅读 54
收藏 4
#include<iostream>
#define Type int
#define MAXN 100
#define INF 10000
using namespace std;

class stack{
	public :
	stack(){
		stackTop=-1;
		maxStackItemIndex=-1;
	}
	void Push(Type x){
		stackTop++;
		if(stackTop>=MAXN)
		  cout<<"shuzuyejie";
		else
		{
			StackItem[stackTop]=x;
			if(x>Max()){
				link2NextMaxItem[stackTop]=maxStackItemIndex;
				maxStackItemIndex=stackTop;
			}
			else
			link2NextMaxItem[stackTop]=-1;
		}
	}
	Type Pop(){
		Type ret;
		if(stackTop<0)
		cout<<"程序出错";
		else{
			ret=StackItem[stackTop];
			if(stackTop==maxStackItemIndex){
				maxStackItemIndex=link2NextMaxItem[stackTop];
			}
			stackTop--;
		}
		return ret;
	}
	Type Max(){
		if(maxStackItemIndex>=0)
		 return StackItem[maxStackItemIndex];
		 else
		 return -INF;
	}
	bool Empty(){
		if(stackTop=-1)
		return true;
		else 
		return false;
	}
	private:
	Type StackItem[MAXN];
	int stackTop;
	int link2NextMaxItem[MAXN];
	int maxStackItemIndex;
};

class Queue
{
	public :
	Type MaxValue(Type x,Type y)
	{
		if(x>y)
		return x;
		else 
		return y;
	}
	Type Queue::Max(){
		return MaxValue(stackA.Max(),stackB.Max());
	}
	void EnQueue(Type v){
		stackB.Push(v);
	}
	Type DeQueue(){
		if(stackA.Empty())
		{
			while(!stackB.Empty())
			stackA.Push(stackB.Pop());
		}
		return stackA.Pop();
	}
	private:
	stack stackA;
	stack stackB;
};
int main(){
	Queue a;
	a.EnQueue(15);
	a.EnQueue(3);
	a.EnQueue(50);
	a.EnQueue(2);
	cout<<a.Max();
	return 0;
}


© 著作权归作者所有

颜建海
粉丝 14
博文 141
码字总数 52360
作品 0
厦门
产品经理
私信 提问
用队列实现栈操作

原题   Implement the following operations of a stack using queues.   push(x) – Push element x onto stack.   pop() – Removes the element on top of the stack.   top() –......

一贱书生
2016/12/28
2
0
Sliding Window Maximum

题目 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Ea......

Finley.Hamilton
2015/08/10
16
0
Java 队列详细介绍

参考文档:http://docs.oracle.com/javase/8/docs/api/ Queue队列的所有已知实现类: 该接口继承Iterable,Collection接口.除了继承的接口的方法外,它有自身操作队列的一些公有的方法:offer/po...

最爱肉肉
2016/11/23
32
0
java.util包中集合详解

本文只是集合的概述,介绍集合之间的关系,以及各种集合的异同,不会深入介绍具体的实现,具体实现的介绍,可以参见文中提供的链接。 java集合概述 java集合整体分为collection和map两种,接...

jacksu在简书
2018/01/25
0
0
读书笔记之用JS实现栈和队列

我的理解是,js 语言中其实没有栈和队列这一引用类型(有用数组的基础方法push()和pop()模拟栈,shift()和push()模拟队列,栈和队列更复杂的功能需要自己写),这些概念以及方法都是通过对数...

Anymore
2016/11/08
16
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
10
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0
PHP+Ajax微信手机端九宫格抽奖实例

PHP+Ajax结合lottery.js制作的一款微信手机端九宫格抽奖实例,抽奖完成后有收货地址添加表单出现。支持可以设置中奖概率等。 奖品列表 <div class="lottery_list clearfix" id="lottery"> ......

ymkjs1990
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部