C# · 12月 20, 2021

程序员面试一百题-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();

}