queue for max elem, pop, push

个人信息:就读于燕大本科软件工程专业 目前大三;

本人博客:google搜索“cqs_2012”即可;

个人爱好:酷爱数据结构和算法,希望将来从事算法工作为人民作出自己的贡献;

博客内容:queue for max elem, pop, push;

博客时间:2014-4-15;

编程语言:C++ ;

编程坏境:Windows 7 专业版 x64;

编程工具:vs2008 32位编译器;

制图工具:office 2010 ppt;

硬件信息:7G-3 笔记本;

my words

Don‘t let shorts beat you, because it doesn‘t worth.

problem

make a queue for max elem, pop and push.(problem from beauty from programming)

require fast for getting max elem

my solution

two stacks can make true a queue.

sub-problem

getting max elem for the stack is so easy with dp.

my solution for my stack with max elem follows

name of type for elem is int

class Stack_mine
{
	// assume: the data length is not so long, its length <= the max number of int
	int * data ;
	int length;
	int * table;

public:

	// constructor function
	Stack_mine()
	{
		length = 0;
		data = new int[LENGTH];
		table = new int[LENGTH];
	}

	// function: pop
	int _pop()
	{
		if( ! _empty() )
		{
			length--;
			return data[length];
		}
		else
		{
			cout<<"pop error"<<endl;
			return -1;
		}
	}

	// function: return length
	int _length( )
	{
		return length;
	}

	// function: push
	void _push(int a)
	{
		int * p1,*p2;
		if(length >= LENGTH)
		{
			p1 = (int *)realloc(data,LONGLENGTH * sizeof(int));
			p2 = (int *)realloc(table,LONGLENGTH * sizeof(int));
			data = p1;
			table = p2;
		}
		data[length] = a;
		if( length == 0 || data[ table[length-1] ] < a )
			table[length] = length;
		else table[length] = table[length-1];
		length ++;
	}

	// function: empty
	bool _empty()
	{
		if(length>0)
			return false;
		else return true;
	}

	// function: max
	int _max()
	{
		if(! _empty())
			return data[ table[ length-1 ] ];
		cout<<"error: empty stack for _max"<<endl;
		return -1;
	}
};

ok, my solution for queue max elem follows

class Queue_mine
{
	Stack_mine s1;
	Stack_mine s2;
public:
	Queue_mine(){};

	// function: push
	void _push(int a)
	{
		s1._push(a);
	};

	// function: pop
	int _pop()
	{
		if(s2._empty())
		{
			while(!s1._empty())
			{
				s2._push(s1._pop());
			}
		}
		return s2._pop();
	}

	// function: length
	int _length()
	{
		return s1._length() + s2._length();
	}

	bool _empty()
	{
		if( s1._empty() && s2._empty() )
		{
			return true ;
		}
		else return false ;
	}

	int _max()
	{
		if(! s1._empty() && ! s2._empty())
			return ( s1._max() > s2._max() ? s1._max() : s2._max() );
		else if( ! s1._empty() && s2._empty())
			return s1._max();
		else if( s1._empty() && ! s2._empty() )
			return s2._max();
		else {
			cout<<"empty for queue"<<endl;
			return -1;
		}
	}

};

queue for max elem, pop, push,布布扣,bubuko.com

时间: 05-02

queue for max elem, pop, push的相关文章

js array filter pop push shift unshift方法

JavaScript Array filter() 方法  JavaScript Array 对象 实例 返回数组 ages 中所有元素都大于 18 的元素: var ages = [32, 33, 16, 40]; function checkAdult(age) {    return age >= 18;} function myFunction() {    document.getElementById("demo").innerHTML = ages.filter(c

大根堆pop push详细注释

//大根堆procedure push(x:longint);//元素x入堆 O(log t)var  tx,i:longint;begin  inc(t);//堆顶top加1  a[t]:=x;//将x放入堆的最后一个节点  i:=t;  while (i>1)and(a[i>>1]<a[i]) do//将元素x一层一层向上传递直到 到达根或上一层大于本身<=>找到x应在的位置    begin    tx:=a[i>>1];     a[i>>

栈 pop push show

栈(stack)是限定仅在表尾进行插入和删除操作的线性表,允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈. 栈又称为后进先出(LastIn First Out)的线性表,简称LIFO结构. 栈元素具有线性关系,即前驱后继关系.只不过它是一种特殊的线性表而已.定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底. 堆叠数据结构使用两种基本操作:推入(push)和弹出(pop): 推入:将数据放入堆叠的顶端(阵列形式或串列形式

JS中some()和every()和join()和concat()和pop(),push(),shift(),unshfit()和map()和filter()

一.Array 1.some()和every() some()是对数组中每一项运行指定函数,如果该函数对任一项返回true,则返回true. every()是对数组中的每一项运行给定函数,如果该函数对每一项返回true,则返回true. var array = [1,3,5,7,9,11,13,15,17] undefined array.some(function(item,index){ return item>9 }) //true 返回 true var array = [1,3,5,7

堆栈 pop push

1.什么是堆栈 1.1堆栈 堆栈可以看作程序的心脏 所有重要的数据都会在这个里面体现(比如运算一道算术题,虽然还没算出最终答案,但是你在算出最终结果前的一些过程值可以放进堆栈) 堆栈这块内存比较特殊,他是由大地址往小地址用 1.2栈指针寄存器ESP 假设现在程序的堆栈用到0018FF8C 当我们想使用一个程序停止之后的堆栈空间, 可以使用指令:mov dword ptr ds:[18FF88] ,1   mov dword ptr ds:[18FF84] ,2 但是 因为程序可能接着会执行,所以

ios8以后,使用UIAlertViw时pop/push页面后,键盘闪一下的问题

代码为 UIAlertView *alert = [[UIAlertView alloc]initWithTitle:@"" message:@"感谢你对我们提出的意见或建议,你的支持就是我们进步的动力!" delegate:self cancelButtonTitle:@"我知道了" otherButtonTitles:nil, nil]; [alert show]; -(void)alertView:(UIAlertView *)alertV

下拉弹窗 pop push动画实现

- (void)popTitleView:(UIButton *)btn { if (popView.superview ==self.view) { CATransition *animation =[CATransition animation]; animation.delegate=self; animation.duration=0.3; animation.timingFunction=[CAMediaTimingFunction functionWithName:kCAMediaT

2_STL容器

STL算法的精髓在于  算法的  返回值!!! String: string是STL的字符串类型,通常用来表示字符串:C语言中一般用char* char*字符指针;string是类封装了char*,管理这个字符串,是一个char*型的容器: string不用考虑内存释放和越界,string管理char*所分配的内存. string提供了一系列字符串操作函数(find,copy,erase,replace,insert)初始化 : string s1 = "abcd"; //重载oper

第29题:判断一个序列是否是另一个push序列的pop序列

github:https://github.com/frank-cq/MyTest 第29题:输入两个整数序列,其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序.为了简单起见,我们假设push序列的任意两个整数都是不相等的.比如输入的push序列是 1.2.3.4.5,那么4.5.3.2.1 就有可能是一个pop序列,因为可以有如下的push和pop序列:push 1, push 2, push 3, push 4,pop, push 5, pop, pop, pop