1

如何将以下伪代码转换为数组而不是堆栈。该算法旨在在给定特定输入的情况下构造一个有向图：

  1. 在堆栈上从右到左扫描公式调用符号，直到顶部出现 2 个连续的节点符号。
  2. 弹出这 2 个节点符号和堆栈上它们正下方的“*”。从第一个符号到第二个符号绘制一条边。
  3. 将第一个符号压入堆栈。
  4. 继续执行步骤 1-3，直到公式处理完毕。

这是一个示例输入和输出：

输入：

***ABCD

输出：

*AB, *AC, *AD

'*' 代表一条边

所有输入都将使用扫描仪完成。

4

2 回答 2

2

可以使用数组和“堆栈索引”的索引来对有限大小的堆栈进行建模。

从 开始堆栈索引-1。在 push 操作中，增加堆栈索引，并将值存储在数组的相应索引处。在弹出操作中，使用堆栈索引处的值，并在获取值后递减索引。要访问堆栈的顶部，请读取堆栈索引处的项目。

于 2012-11-08T16:27:37.300 回答
1

您基本上必须使用 FIFO 属性对数组执行操作。

public ArrayStack( )
{
    theArray = new String[InitialSize];
    topOfStack = -1;
}

每次将元素添加到数组 ( push ) 时，您都会topOfStack++;将元素插入到"topOfStack"数组的位置。通过这样做topOfStack++，您可以跟踪成为堆栈新顶部的数组位置。

当你这样做时，pop你必须检查数组是否不为空，返回元素array[topOfStack]并执行topOfStack--;。因为顶部现在是数组上的先前位置。

如果您的数组需要更多空间，因为堆栈已满(topOfStack == InitialSize)，您必须创建另一个具有更多空间的数组，例如：

private void doubleArray( )
{
        String [] newArray = new String[ theArray.length * 2 ];
        for( int i = 0; i < theArray.length; i++ )
            newArray[ i ] = theArray[ i ];
        theArray = newArray;
 }

为了说明，这大致是您需要寻找的，自然还有更多细节需要研究。不过，请自己尝试一下，当您有疑问时，请寻找诸如此类的资源。

于 2012-11-08T16:34:52.527 回答