假设我们有两个堆栈，没有其他临时变量。
是否有可能“构造”一个队列数据结构只使用两个堆栈?
当前回答
// Two stacks s1 Original and s2 as Temp one
private Stack<Integer> s1 = new Stack<Integer>();
private Stack<Integer> s2 = new Stack<Integer>();
/*
* Here we insert the data into the stack and if data all ready exist on
* stack than we copy the entire stack s1 to s2 recursively and push the new
* element data onto s1 and than again recursively call the s2 to pop on s1.
*
* Note here we can use either way ie We can keep pushing on s1 and than
* while popping we can remove the first element from s2 by copying
* recursively the data and removing the first index element.
*/
public void insert( int data )
{
if( s1.size() == 0 )
{
s1.push( data );
}
else
{
while( !s1.isEmpty() )
{
s2.push( s1.pop() );
}
s1.push( data );
while( !s2.isEmpty() )
{
s1.push( s2.pop() );
}
}
}
public void remove()
{
if( s1.isEmpty() )
{
System.out.println( "Empty" );
}
else
{
s1.pop();
}
}
其他回答
不过，时间的复杂性会更糟。一个好的队列实现在常数时间内完成所有事情。
Edit
不知道为什么我的答案在这里被否决了。如果我们编程，我们会关心时间复杂度，使用两个标准堆栈来创建队列是低效的。这是一个非常有效和相关的观点。如果有人觉得有必要再投反对票，我很想知道为什么。
更详细一点:关于为什么使用两个堆栈比使用一个队列更糟糕:如果您使用两个堆栈，并且有人在发件箱为空时调用dequeue，则需要线性时间才能到达收件箱的底部(正如您可以在Dave的代码中看到的那样)。
您可以将队列实现为单链表(每个元素指向下一个插入的元素)，保留一个额外的指针指向最后一个插入的元素进行推操作(或使其成为循环列表)。在此数据结构上实现队列和出队列非常容易，只需常数时间即可完成。这是最坏情况的常数时间，不是平摊。而且，正如注释中要求澄清的那样，最坏情况下常数时间严格来说比平摊常数时间要好。
// Two stacks s1 Original and s2 as Temp one
private Stack<Integer> s1 = new Stack<Integer>();
private Stack<Integer> s2 = new Stack<Integer>();
/*
* Here we insert the data into the stack and if data all ready exist on
* stack than we copy the entire stack s1 to s2 recursively and push the new
* element data onto s1 and than again recursively call the s2 to pop on s1.
*
* Note here we can use either way ie We can keep pushing on s1 and than
* while popping we can remove the first element from s2 by copying
* recursively the data and removing the first index element.
*/
public void insert( int data )
{
if( s1.size() == 0 )
{
s1.push( data );
}
else
{
while( !s1.isEmpty() )
{
s2.push( s1.pop() );
}
s1.push( data );
while( !s2.isEmpty() )
{
s1.push( s2.pop() );
}
}
}
public void remove()
{
if( s1.isEmpty() )
{
System.out.println( "Empty" );
}
else
{
s1.pop();
}
}
在Swift中使用两个堆栈的队列实现:
struct Stack<Element> {
var items = [Element]()
var count : Int {
return items.count
}
mutating func push(_ item: Element) {
items.append(item)
}
mutating func pop() -> Element? {
return items.removeLast()
}
func peek() -> Element? {
return items.last
}
}
struct Queue<Element> {
var inStack = Stack<Element>()
var outStack = Stack<Element>()
mutating func enqueue(_ item: Element) {
inStack.push(item)
}
mutating func dequeue() -> Element? {
fillOutStack()
return outStack.pop()
}
mutating func peek() -> Element? {
fillOutStack()
return outStack.peek()
}
private mutating func fillOutStack() {
if outStack.count == 0 {
while inStack.count != 0 {
outStack.push(inStack.pop()!)
}
}
}
}
我将在Go中回答这个问题，因为Go在其标准库中没有丰富的集合。
由于堆栈真的很容易实现，我想我应该尝试使用两个堆栈来完成一个双端队列。为了更好地理解我是如何得到我的答案的，我将实现分为两部分，第一部分希望更容易理解，但它是不完整的。
type IntQueue struct {
front []int
back []int
}
func (q *IntQueue) PushFront(v int) {
q.front = append(q.front, v)
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[0]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
q.back = q.back[1:]
}
}
func (q *IntQueue) PushBack(v int) {
q.back = append(q.back, v)
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[0]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
q.front = q.front[1:]
}
}
它基本上是两个堆栈，我们允许堆栈的底部相互操纵。我还使用了STL命名约定，其中堆栈的传统push、pop、peek操作都有一个front/back前缀，无论它们是指队列的前面还是后面。
上面代码的问题是它没有非常有效地使用内存。事实上，它会不断增长，直到空间耗尽。这太糟糕了。解决这个问题的方法是尽可能重用堆栈空间的底部。我们必须引入一个偏移量来跟踪这一点，因为围棋中的切片一旦收缩就不能在前面生长。
type IntQueue struct {
front []int
frontOffset int
back []int
backOffset int
}
func (q *IntQueue) PushFront(v int) {
if q.backOffset > 0 {
i := q.backOffset - 1
q.back[i] = v
q.backOffset = i
} else {
q.front = append(q.front, v)
}
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[q.backOffset]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
if len(q.back) > 0 {
q.backOffset++
} else {
panic("Cannot pop front of empty queue.")
}
}
}
func (q *IntQueue) PushBack(v int) {
if q.frontOffset > 0 {
i := q.frontOffset - 1
q.front[i] = v
q.frontOffset = i
} else {
q.back = append(q.back, v)
}
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[q.frontOffset]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
if len(q.front) > 0 {
q.frontOffset++
} else {
panic("Cannot pop back of empty queue.")
}
}
}
有很多小函数，但6个函数中有3个只是另一个的镜像。
您必须从第一个堆栈中取出所有元素来获取底部元素。然后在每次“出队列”操作时将它们都放回第二个堆栈。
推荐文章
- 段树、区间树、二叉索引树和范围树之间有什么区别?
- 给定一个数字，找出下一个与原始数字具有完全相同的数字集的更高的数字
- HSL到RGB的颜色转换
- 使用Java在原语数组中查找最大/最小值
- 好的Java图算法库?
- 为什么我应该使用Deque而不是Stack?
- 什么时候我应该使用Kruskal而不是Prim(反之亦然)?
- .Net中的优先级队列
- 取一个集中在中心的随机数
- 为什么java.util.Set没有get(int index)?
- 什么是栈展开?
- 如何计算圆周长上的一点?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下，您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
