189 8069 5689

堆栈模拟队列(封装版).C++-创新互联

设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。

成都创新互联专注于企业成都全网营销推广、网站重做改版、江阴网站定制设计、自适应品牌网站建设、H5场景定制、成都做商城网站、集团公司官网建设、成都外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为江阴等各大城市提供网站开发制作服务。

所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:

  • int IsFull（Stack S）：判断堆栈S是否已满，返回1或0;
  • int IsEmpty （Stack S ）：判断堆栈S是否为空，返回1或0;
  • void Push（Stack S， ElementType item ）：将元素item压入堆栈S;
  • ElementType Pop（Stack S ）：删除并返回S的栈顶元素。

实现队列的操作，即入队void AddQ（ElementType item）和出队ElementType DeleteQ（）。

输入说明

输入首先给出两个正整数N1和N2，表示堆栈S1和S2的大容量。随后给出一系列的队列操作：A item表示将item入列（这里假设item为整型数字）;D表示出队操作;T表示输入结束。

输出说明

对输入中的每个D操作，输出相应出队的数字，或者错误信息ERROR：Empty。如果入队操作无法执行，也需要输出ERROR：Full。每个输出占1行。

示例输入

3 2
A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T

示例输出

ERROR:Full
1
ERROR:Full
2
3
4
7
8
ERROR:Empty

类MyStack：

MyStack.h

#pragma once
class MyStack
{
public:
	MyStack(int N);//构造函数；
	~MyStack();//析构函数；
public://主要是函数成员与数据成员
	bool IsFull();//是可以在声明文件中实现，通常在实现文件实现
	bool IsEmpty();
	void Push(int item);
	int pop();
private:
	const int m_N;
	int       m_top;
	int   *   m_data;
};

MyStack.cpp

#include "MyStack.h"
#include "iostream"
using namespace std;

MyStack::MyStack(int N)
	:m_N(N)//初始化;
{
	//cout<< "调用MyStack的构造函数"<< endl;
	m_top = m_N;
	m_data = new int[m_N];
}
MyStack::~MyStack(void)//析构函数，不能重载;
{
	//cout<< "调用MyStack的析构函数"<< endl;
	delete[] m_data;
}
bool MyStack::IsFull()
{
	return m_top == 0;
}
bool MyStack::IsEmpty()
{
	return m_top == m_N;
}
void MyStack::Push(int item)
{
	m_data[--m_top] = item;//压入堆栈
}
int MyStack::pop()
{
	return m_data[m_top++];//挪出堆栈
}

类 MyQueue：

MyQueue.h

#pragma once
#include"MyStack.h"
class MyQueue
{
public:
	MyQueue(int sizeOut,int sizeIn);
	~MyQueue(void);
public:
	bool IsEmpty();
	bool IsFull();
	void push(int data);
	int  pop();
private:
	MyStack m_out;
	MyStack m_in;
};

MyQueue.cpp

#include "MyQueue.h"
#include"iostream"
using namespace std;
MyQueue::MyQueue(int sizeOut, int sizeIn)
	:m_out(sizeOut),m_in(sizeIn)
{

}
MyQueue::~MyQueue(void)
{

}
bool MyQueue::IsEmpty()
{
	return m_out.IsEmpty() && m_in.IsEmpty();
}
bool MyQueue::IsFull()
{
	return m_in.IsFull() && !m_out.IsEmpty();
}
void MyQueue::push(int data)
{
	if (!m_in.IsFull())
	{
		m_in.Push(data);
	}
	else
	{
		if (m_out.IsEmpty())//前提为空
		{
			while (!m_in.IsEmpty())//入栈非空时循环进行
			{
				if (!m_out.IsFull())//出栈是否为满
				{
					m_out.Push(m_in.pop());//没满进行入栈导出到出栈
				}
				else
				{
					cout<< "ERROR:Full"<< endl;//提示已满
					break;
				}
			}
			m_in.Push(data);
		}
	}
}
int MyQueue::pop()
{
	if (!m_out.IsEmpty())//如果出栈不为空
	{
		return m_out.pop();//直接返回
	}
	else
	{
		while (!m_in.IsEmpty())//入栈不为空，将入栈导入出栈
		{
			m_out.Push(m_in.pop());
		}
		return m_out.pop();//返回出栈的值
	}
}

main函数：

#include"iostream"
#include"MyStack.h"//引用封装的头文件
#include"MyQueue.h"
using namespace std;

int main()
{
	int sizeOut;
	int sizeIn;
	cout<< "请输入输出栈的大小"<< endl;
	cin >>sizeOut;
	cout<< "请输入输入栈的大小"<< endl;
	cin >>sizeIn;//输入结束的换行符会影响后续的输入,导致getline读入为空
	cin.ignore();//忽略掉换行符，以后面读入
	if (sizeOut<= sizeIn)
	{
		cout<< "输出栈的大小一定要大于输入栈的大小，程序终止"<< endl;
		return 0;
	}
	MyQueue myQueue(sizeOut, sizeIn);
	char buf[200];
	cout<< "请输入你要执行的操作比如A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T，其中A是入列，D是出列，T是结束"<< endl;
	cin.getline(buf,200);//读入buf
	char* pbuf = buf;
	while (*pbuf != 'T')
	{
		if (*pbuf == 'A')
		{
			pbuf++;
			while (*pbuf< '0' || *pbuf >'9')//整数域
			{
				if (*pbuf == 'T')
				{
					return 0;
				}
				pbuf++;
			}
			if (!myQueue.IsFull())//判断是否已满
			{
				myQueue.push(*pbuf - '0');//没满则压入元素
			}
			else
			{
				cout<< "ERROR:Full"<< endl;//已满提示
			}
			pbuf++;
		}
		else if (*pbuf == 'D')
		{
			if (!myQueue.IsEmpty())//判断是否为空
			{
				cout<< myQueue.pop()<< endl;//非空进行输出
			}
			else
			{
				cout<< "ERROR:Empty"<< endl;//已空提示
			}
			pbuf++;
		}
		else
		{
			pbuf++;
		}
	}
	return 0;
}

使用编译器vs.2022

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


本文标题：堆栈模拟队列(封装版).C++-创新互联
URL网址：http://jkwzsj.com/article/dochei.html

其他资讯