设计一个堆叠中也能出队在O（1）摊销的时间？ [英] Design a stack that can also dequeue in O(1) amortized time?

问题描述

我有可以被看作是存储从左到右的列表，具有以下可能操作的抽象数据类型： 推：新项目添加到列表中的左端 流行：删除就行了的左端的项目 拉：去掉就行了。

右端的项目

实现此使用三个栈和不断的额外内存，从而使分期时间任何PUSH，POP，或拉的操作是不变的。该堆有基本的操作，的isEmpty，推送和流行音乐。

分期时间的意思是如果我花这段时间内，我可以用它的另一块并将其存储在时间银行供以后使用。像每一个推送操作，花费一定的时间三部分，因此对于每一个元素推，你有固定的时间2个额外的块。

解决方案

做了一些假设：

1. 这是本文的功课
2. ，本款的任务的一部分

  

采用三栈实现这一点，   恒额外的内存，从而使   的分期时间任何PUSH，POP，   或拉的操作是不变的。该   堆栈有基本的操作，的isEmpty，   推送和流行音乐。

然后我的第一个建议是无视你说话的人对链表。诚然，这是任何理智的人会如何实现它的三无堆叠的要求，的，但在作业的关键因素是，不要做它的方式理性的人都会，而是如何你的老师要你

建议我的第二位将得到一些块，一副扑克牌，或一堆泡沫塑料杯和指定三个栈（如使用杯垫或东西）。开始摆弄当你一个堆栈的内容转移到另一个会发生什么，这应该给你一个想法。

I have an abstract data type that can be viewed as a list stored left to right, with the following possible operations: Push: add a new item to the left end of the list Pop: remove the item on the left end of the list Pull: remove the item on the right end of the list

Implement this using three stacks and constant additional memory, so that the amortized time for any push, pop, or pull operation is constant. The stacks have basic operations, isEmpty, Push, and Pop.

Amortized time means "If I spend this amount of time, I can spend another block of it and store it in a bank of time to be used later." like for each push operation, spend three blocks of constant time, so for every element pushed, you have 2 extra blocks of constant time.

解决方案

Making a few assumptions:

1. That this is homework
2. That this paragraph is part of the assignment

Implement this using three stacks and constant additional memory, so that the amortized time for any push, pop, or pull operation is constant. The stacks have basic operations, isEmpty, Push, and Pop.

Then my first advice would be to ignore the people talking to you about linked lists. True, that's how any reasonable person would implement it without the three stack requirement, but the key factor in homework isn't to do it the way a reasonable person would, but rather how your instructor wants you to.

My second bit of advice would be to get some blocks, a deck of cards, or a bunch of styrofoam cups and designate three stacks (e.g. with coasters or something). Start playing around with what happens when you transfer the contents of one stack to another, and that should give you an idea.

这篇关于设计一个堆叠中也能出队在O（1）摊销的时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！