[점적 학습 - 데이터 구조 - 스 택 & 대기 열] 두 스 택 으로 하나의 대기 열 을 모 의 합 니 다.

본문 과 전재.
원본 주소:http://blog.csdn.net/zhuimengzh/article/details/6806553
@zhuimengzh
#include "stdafx.h"
#include <iostream>
using namespace std;
//      
class Data{
public:
	Data():data(0),next(NULL){}
	Data(int i):data(i),next(NULL){}
	int data;
	Data *next;
};
class Stack{
public:
	Stack():Top(NULL){}
	void Push(Data i);
	void Pop(Data &d);
	bool IsEmpty();
	void Print();
private:
	Data *Top;
};

//  
void Stack::Push(Data d){
	Data *p=new Data(d.data);
	if (IsEmpty()){ //     
		Top=p;
	}else{ //         
		p->next=Top;
		Top=p;
	}
}
//  
void Stack::Pop(Data &s){
	if (IsEmpty()){//     
		cout<<"Stack Empty!"<<endl;
		getchar();
		exit(1);
	}else{
		s.data=Top->data;
		Top=Top->next;
	}
}
//      
bool Stack::IsEmpty(){
	if (Top==NULL){
		return 1;
	}
	else
		return 0;
}
//  
void Stack::Print(){
	Data *p=Top;
	while (p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}

class Queue{
public:
	void enqueue(Data d); //  
	void dequeue(Data &d); //  
	bool IsEmpty();//    
private:
	Stack s1;//    
	Stack s2;//    
};
//  
void Queue::enqueue(Data d){
	s1.Push(d);//  s1      
}
//  
void Queue::dequeue(Data &d){
	Data temp(0);//    ,      
	if (s2.IsEmpty())//  s2  , s1     push s2 
		while (!s1.IsEmpty()){
		  s1.Pop(temp); //  s1   
		  s2.Push(temp);//  s2 
		 }
	 if(!s2.IsEmpty()){ //  s2   
			//    s2   ,  s2     
			s2.Pop(d);
		}
		
}
//    
bool Queue::IsEmpty(){
	//        ,   1,    0
	if (s1.IsEmpty() && s2.IsEmpty()){
		return 1;
	}
	else
		return 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
	Data data(0);//      
	Queue q;
	q.enqueue(Data(1));
	q.enqueue(Data(2));
	q.enqueue(Data(3));

	q.dequeue(data);
	cout<<"dequeue "<<data.data<<endl;
	q.enqueue(Data(4));
	q.dequeue(data);
	cout<<"dequeue "<<data.data<<endl;
	q.dequeue(data);
	cout<<"dequeue "<<data.data<<endl;
	cout<<"IsEmpty "<<q.IsEmpty()<<endl;
	q.dequeue(data);
	cout<<"dequeue "<<data.data<<endl;
	cout<<"IsEmpty "<<q.IsEmpty()<<endl;
    system("pause");
	return 0;
}

좋은 웹페이지 즐겨찾기