温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

两个栈实现一个队列

发布时间:2020-06-18 00:36:25 来源:网络 阅读:247 作者:小止1995 栏目:编程语言

栈的特点:先进后出

队列特点:先进先出

//实现两个栈实现一个队列
//每次都push到_s1中,pop从_s2,提高效率(每次不用互相倒栈)
#pragma once
#include<iostream>
#include<stack>
#include<queue>
#include<assert.h>
using namespace std;
template<class T>
class Queue
{
public:
	void Push(const T& x)
	{
		_s1.push(x);
	}
	void Pop()
	{
		if (_s2.empty())
		{
			while (!_s1.empty())
			{
				_s2.push(_s1.top());
				_s1.pop();
			}
		}
		//断言当_s2为空时,不执行 (库中实现_s2.pop()也已断言,实不实现都行!!!)防止自己实现的栈出错
		assert(!_s2.empty());
		_s2.pop();
	}
	bool Empty()
	{
		return _s1.empty() && _s2.empty();
	}
	int Size()
	{
		return _s1.size() + _s2.size();
	}
	T& Front()
	{
		if (_s2.empty())
		{
			while (!_s1.empty())
			{
				_s2.push(_s1.top());
				_s1.pop();
			}
		}
		assert(!_s2.empty());
		return _s2.top();
	}
	T& Back()
	{
		if (_s1.empty())
		{
			while (!_s2.empty())
			{
				_s1.push(_s2.top());
				_s2.pop();
			}
		}
		assert(_s1.empty());
		return _s1.top();
	}
protected:
	stack<T> _s1;
	stack<T> _s2;
};
void Test1()
{
	Queue<int> q1;
	q1.Push(1);
	q1.Push(2);
	q1.Push(3);
	q1.Push(4);
	q1.Push(5);
	q1.Push(6);
	q1.Pop();
	q1.Pop();
	q1.Pop();
	q1.Pop();
	q1.Pop();
	q1.Pop();
	//q1.Pop();
	//cout << q1.Front() << endl;
	//cout << q1.Back() << endl;
	//cout << q1.Empty() << endl;
	cout << q1.Size() << endl;
}


向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI