程序员面试一百题-18-用两个栈实现队列

1-题目 :

用两个栈实现队列。

2-思路 :

2.1-删除元素的步骤 : 当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以pop出去；如果stack2为空时，把stack1中的元素逐个pop出来并push进入stack2，由于先进入队列的元素被压到stack1的底端，经过pop和push之后就处于stack2的顶端了，又可以直接pop出去。

2.2-插入元素的步骤 : 直接放入stack1。

操作

栈1

栈2

append a

{a}

{}

append b

{a,b}

{}

append c

{a,b,c}

{}

delete head

{}

{b,c}

delete head

{}

{c}

append d

{d}

{c}

delete head

{d}

{}

3-代码 :

//插入元素的步骤

template void CQueue::appendTail(const T &element)

{

//直接push进stack1

stack1.push(element);

}

//删除元素的步骤

template void CQueue::deleteHead()

{

//如果stack2为空,则将stack1元素反向压入stack

if (stack2.size() <= 0)

{

while (stack1.size() > 0)

{

T &data = stack1.top();

stack1.pop();

stack2.push(data);

}

}

//删除stack2栈顶元素

stack2 assert(stack2.size() > 0);

stack2.pop();

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!