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;
}