线性结构：栈和队列

两个栈实现一个队列和两个队列实现一个栈

目录

1.mian.cpp

2.Stack.h

3.Stack.cpp

4.Queue.h

5.queue.cpp

1.mian.cpp

#include "Stack.h"
#include "Queue.h"

//两个队列实现栈

void StackPush(Queue& q1, Queue& q2, int n)
{
	//找到一个非空队列 将元素入队
	if (q1.size != 0)
	{
		q1.Push(n);
	}
	else
	{
		q2.Push(n);
	}

}
int StackPop(Queue& q1, Queue& q2)
{
	//找到一个非空队列  将该队列中除队尾元素外的所有元素入队到另一个队中 将该队尾元素返回
	if (q1.size == 0 && q2.size == 0)
	{
		cout << "栈中无元素" << endl;
		return -1;
	}
	int value;
	if (q1.size != 0)
	{
		while (q1.size > 1)
		{
			q2.Push(q1.Pop());
		}
		value = q1.Pop();
	}
	else
	{
		while (q2.size > 1)
		{
			q1.Push(q2.Pop());
		}
		value = q2.Pop();
	}
	return value;
}
//------------------------------------------------------------------------------------

//两个栈实现一个队列

void QueuePush(Stack& SPush, Stack& SPop, int n)
{
	//将出队栈的元素全部倒入入队栈中  将新元素入到入队栈中
	/*while (SPop.size > 0)
	{
		SPush.Push(SPop.Pop());
	}*/
	//SPush.Push(n);
}
int QueuePop(Stack& SPush, Stack& SPop)
{
	if (SPush.size == 0 && SPop.size == 0)
	{
		cout << "队列中无元素" << endl; 
		return -1;
	}
	//将入队中元素全部倒入到出队栈中 将出队栈栈顶弹出
	if (SPop.size == 0)
	{
		while (SPush.size > 0)
		{
			SPop.Push(SPush.Pop());
		}
	}
	
	return SPop.Pop();
}
int main()
{
	Stack SPush;
	Stack SPop;
						  
	QueuePush(SPush , SPop,1);
	QueuePush(SPush , SPop,2);
	QueuePush(SPush , SPop,3);
	QueuePush(SPush , SPop,4);

	cout << QueuePop(SPush, SPop) << endl;
	cout << QueuePop(SPush, SPop) << endl;
	cout << QueuePop(SPush, SPop) << endl;
	cout << QueuePop(SPush, SPop) << endl;









//----------------------------------------------------------------------------------

	/*Queue q1;
	Queue q2;

	StackPush(q1, q2, 1);
	StackPush(q1, q2, 2);
	StackPush(q1, q2, 3);

	cout << StackPop(q1, q2) << endl;
	cout << StackPop(q1, q2) << endl;
	StackPush(q1, q2, 5);
	cout << StackPop(q1, q2) << endl;
	cout << StackPop(q1, q2) << endl;*/

--------------------------------------------------------------------


	/*Stack s;
	s.Push(1);
	s.Push(2);
	s.Push(3);
	s.Push(4);

	cout << s.Pop() << endl;
	cout << s.Pop() << endl;
	cout << s.Pop() << endl;
	cout << s.Pop() << endl;
	cout << s.Pop() << endl;

	Queue q;
	q.Push(1);
	q.Push(2);
	q.Push(3);
	q.Push(4);

	cout << q.Pop() << endl;
	cout << q.Pop() << endl;
	cout << q.Pop() << endl;
	cout << q.Pop() << endl;
	cout << q.Pop() << endl;


	return 0;*/
//}

2.Stack.h

#pragma once
#include <iostream>
using namespace std;


class Stack
{
	struct Node
	{
		int value;
		Node* pNext;
	};
public:
	Node* pTop;
	int size;
public:
	Stack();
	~Stack();
public:
	void Push(int n);
	int Pop();
};

3.Stack.cpp

#include "Stack.h"



Stack::Stack()
{
	pTop = NULL;
	size = 0;
}
Stack::~Stack()
{
	while (pTop != NULL)
	{
		Node* pDel = pTop;
		pTop = pTop->pNext;
		delete pDel;
		pDel = NULL;
	}
}
void Stack::Push(int n)
{
	Node* pTemp = new Node;
	pTemp->value = n;
	pTemp->pNext = NULL;
	pTemp->pNext = pTop;
	pTop = pTemp;
	size++;
}
int Stack::Pop()
{
	if (size == 0)
	{
		cout << "栈为空" << endl;
		return -1;
	}
	Node* pDel = pTop;
	int nMark = pTop->value;
	pTop = pTop->pNext;
	delete pDel;
	pDel = NULL;
	size--;

	return nMark;
}

4.Queue.h

#pragma once
#include <iostream>
using namespace std;

class Queue
{
	struct Node
	{
		int value;
		Node* pNext;
	};
public:
	Node* pHead;
	Node* pEnd;
	int size;
public:
	Queue();
	~Queue();
public:
	void Push(int n);
	int Pop();
};

5.queue.cpp

#include "Queue.h"


Queue::Queue()
{
	pHead = NULL;
	pEnd = NULL;
	size = 0;
}
Queue::~Queue()
{
	while (pHead != NULL)
	{
		Node* pDel = pHead;
		delete pDel;
		pDel = NULL;
		pHead = pHead->pNext;
	}
}
void Queue::Push(int n)
{
	Node* pTemp = new Node;
	pTemp->value = n;
	pTemp->pNext = NULL;

	if (!pHead)
	{
		pHead = pTemp;
	}
	else
	{
		pEnd->pNext = pTemp;
	}
	pEnd = pTemp;
	size++;
}
int Queue::Pop()
{
	if (size == 0)
	{
		cout << "队列为空" << endl;
		return -1;
	}
	Node* pDel = pHead;
	int nMark = pHead->value;
	pHead = pHead->pNext;
	delete pDel;
	pDel = NULL;
	size--;
	return nMark;
}