使用两个栈实现一个队列/使用两个队列实现一个栈/空格替换

使用两个栈实现一个队列

class MyQueue {
public:
stack<int> stack1;
stack<int> stack2;
    MyQueue() {
// do intialization if necessary
    }

void push(int element) {
// write your code here
        stack1.push(element);
    }

int pop() {
// write your code here
if(stack2.empty()&&stack1.empty())
        {
return -1;
        }
else
        {
if(stack2.empty())
            {
while(!stack1.empty())
                {
                    stack2.push(stack1.top());
                    stack1.pop();
                }
            }
int top=stack2.top();
                stack2.pop();
return top;
        }
    }

int top() {
// write your code here
if(stack2.empty())
            {
while(!stack1.empty())
                {
                    stack2.push(stack1.top());
                    stack1.pop();
                }
            }
int top=stack2.top();
return top;
    }
};

使用两个队列实现一个栈

class MYStack{
public:
void push(const int val)
    {
if (queue2.empty())
            queue1.push(val);
else
            queue2.push(val);
    }
int Swap(queue<int>& q1, queue<int>& q2)
    {
while (q1.size()!=1)
        {
            q2.push(q1.front());
            q1.pop();
        }
    }
int pop()
    {
if (!queue1.empty())
        {
            Swap(queue1, queue2);
int top = queue1.front();
            queue1.pop();
return top;
        }
else
        {
            Swap(queue2, queue1);
int top = queue2.front();
            queue2.pop();
return top;
        }
    }
int top()
    {
if (!queue1.empty())
        {
            Swap(queue1, queue2);
int top = queue1.front();
return top;
        }
else
        {
            Swap(queue2, queue1);
int top = queue2.front();
return top;
        }
    }
private:
queue<int> queue1;
queue<int> queue2;
};

空格替换（要求时间复杂度为O(N) ）

class Solution {
public:
    /**
     * @param string: An array of Char
     * @param length: The true length of the string
     * @return: The true length of new string
     */
int replaceBlank(char string[], int length) {
// Write your code herehttp://www.lintcode.com/zh-cn/problem/space-replacement/#
int count=0;
for(int i=0;i<length;i++)
        {
if(string[i]==' ')
            {
                ++count;
            }
        }
int len=length+2*count-1;
for(int i=length-1;i>=0;i--)
{
if(string[i]==' ')
            {
string[len--]='0';
string[len--]='2';
string[len--]='%';
            }
else
            {
string[len--]=string[i];
            }
       }
return length+2*count;
    }
};