olive_lv: 面试题7：用两个栈实现队列

星期三, 二月 17, 2016

栈的应用：如操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。

栈的特点后进先出，是一个不考虑排序的数据结构。

队列先进先出。

面试题7：用两个栈实现队列

//题目描述

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

#include<stack>

using namespace std;

class Solution

{

public:

void push(int node) {

stack1.push(node);

}

int pop() {

while(!stack1.empty()){

stack2.push(stack1.top());

stack1.pop();

}

int res=stack2.top();

stack2.pop();

while(!stack2.empty()){

stack1.push(stack2.top());

stack2.pop();

}

return res;

}

private:

stack<int> stack1;

stack<int> stack2;

};

删除一个元素时：

当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，若stack2为空时，则把stack1中的元素逐个弹出并压入stack2中。

插入一个元素时：直接将元素压入stack1中

已使用 Microsoft OneNote 2010 创建
一个用于存放所有笔记和信息的位置

olive_lv