面试题7

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。
队列中的元素为int类型。

输入：

每个输入文件包含一个测试样例。
对于每个测试样例，第一行输入一个n(1<=n<=100000)，代表队列操作的个数。
接下来的n行，每行输入一个队列操作：
1. PUSH X 向队列中push一个整数x(x>=0)
2. POP 从队列中pop一个数。

输出：

对应每个测试案例，打印所有pop操作中从队列pop中的数字。如果执行pop操作时，队列为空，则打印-1。

样例输入：

3
PUSH 10
POP
POP

样例输出：

10
-1

使用两个栈stack1,stack2。当直接输入数据时，直接存入stack1中。由于栈是先入后出。假设此时我们要删除，那么就必须将stack1中的数据全部压入到stack2中，这样顺序就又反过来了。这样stack1栈顶的数据就变成stack2中的栈底，直接输出stack2的栈底（可以看做队列的头）。因此，当直接插入数据时，我们可以直接插入到stack1中。需要弹出队列的数据就弹出stack2中的数据。当stack2为空时，再直接将stack1中的数据压入到stack2即可。
版本一：STL

/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月07日 星期六 19:25:11
File Name     :1512.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
using namespace std;
stack< int >stack1;
stack<int>stack2;
int deleteHead(){
	if( stack2.empty() ){
		while( !stack1.empty()){
			int t = stack1.top();
			stack2.push( t );
			stack1.pop();
		}
	}
	int pos = -1;
	if( !stack2.empty() ){
		pos = stack2.top();
		stack2.pop();
	}
	return pos;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
   	int n, temp;
   	while( cin >> n ){
		while( !stack1.empty() ){
			stack1.pop();
		}
		while( !stack2.empty()){
				stack2.pop();
		}
		for( int i = 0; i < n; ++i ){
			string str;
			cin >> str;
			switch( str[ 1 ] ){
				case 'U':{
					cin >> temp;
					stack1.push( temp );
				};break;
				case 'O':{
					int pos = deleteHead();
					cout << pos << endl;
				};break;
				default:break;
			}
		}
	}		
    return 0;
}

 

版本二：书上

/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月07日 星期六 15:12:35
File Name     :1512.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
using namespace std;

template< class T > 
class CQueue{
	public:
	//	CQueue(void);
	//	~CQueue(void);

		void appendTail(const T& node );
		T deleteHead();

	private:
		stack<T> stack1;
		stack<T> stack2;
};

template< class T >
void CQueue<T>::appendTail( const T&  element){
//	cout << "aaaaaaaaaa" << endl;
	stack1.push( element );
//	cout << stack1.size() << endl;
}

template< class T > 
T CQueue<T>::deleteHead(){
//	cout << stack2.size() << "bbbb" << endl;
	if( stack2.size() <= 0 ){
		while( stack1.size() > 0 ){
		//	cout << stack1.top();
			T& data = stack1.top();
			stack2.push( data );
			stack1.pop();
		}
	}

//	if( stack2.size() == 0 )
	//	throw new exception( "queue is empty" );
	if( stack2.size() == 0 )
		puts( "-1");
	else{
		//cout << stack2.top() << "eee" << endl;
		T& head = stack2.top();
	//	cout << "ccccccc " << endl;
		printf( "%d\n", head );
	//	cout << "ddddd" << stack2.top() << endl;
		stack2.pop();
		return head;
	}
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	CQueue<int> Queue;
    int n, temp;
	while( scanf( "%d", &n ) != EOF ){
		while( n-- ){
			char str[ 10 ];
			scanf( "%s", str );
	//	cin >> str;
		//	cout << str<< endl;	
			/*switch( str[ 1 ] ){
				case 'U':( scanf( "%d", &temp ), Queue.appendTail( temp));break;
				case 'O':Queue.deleteHead();break;
			}*/
			if( str[ 1 ] == 'U' ){
				scanf( "%d", &temp );
				Queue.appendTail( temp );
			}
			else
				Queue.deleteHead();
		}	
	}
    return 0;
}

 

变形。使用两个队列实现一个栈。
原理差不多，还是先了解二者的差别。使用两个队列queue1,queue2.同样假设先连续读入几个数据，直接插入到queue1中。假设此时我们需要将栈中的数据弹出，那么这个数据就位于queue1的尾部。但是队列是先入先出，所以我们只有将queue1中尾部以前的数据全部压入到queue2中去。同理，假设需要再弹出数据时，而此时栈的数据全部存在queue2中，就需要将尾部以前的数据压入queue1中去，反复循环。

/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月07日 星期六 19:41:22
File Name     :1512a.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <queue>

using namespace std;

queue<int> queue1, queue2;
int flag;
int deleteHead(){
	int pos = -1;
	if( queue1.empty() && queue2.empty() ){
		pos = -1;
	}
	else{
		if( flag ){
			while( !queue1.empty() ){
				int t = queue1.front();
				if( queue1.size() > 1 ){
					queue2.push( t );
				}
				else{	
					pos = t;
				}
				queue1.pop();
			}
			flag = !flag;
		}
		else{
			while( !queue2.empty() ){

				int t = queue2.front();
				if( queue2.size() > 1){
					queue1.push( t );
				}
				else{
					pos = t;
				}
				queue2.pop();
			}
			flag = !flag;
		}
	}
	return pos;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
  	int n, temp;
	string str;
	while( cin >> n ){
		while( !queue1.empty() ){
			queue1.pop();
		}
		while( !queue2.empty() ){
			queue2.pop();
		}
		flag = 1;
		while( n-- ){
			cin >> str;
			
			switch( str[ 1 ] ){
				case 'U':{
					 cin >> temp;
					 flag?queue1.push( temp ):queue2.push( temp );
						 };break;
				case 'O':{
					 int pos = deleteHead();
					 cout << pos << endl;
				}
			}
		}
	}					 
    return 0;
}