java实现链栈与队列

2015/05/20 30590

java实现链栈与顺序表队列。链栈的实现没有什么难点，跟单链表差不多，只是所有的操作只在表头进行，并且没有头节点，使用top标记。关键的操作是push与pop。

当进行push操作时，通过push方法传入一个object，构建一个新节点node，将node.next设置为原来的top，再将top设置为node即可。

代码如下：

public void push(Object x) {
Node node = new Node(x);
node.setNext(top);
top = node;
 }

当进行pop操作时，首先检查stack是否为空，不为空则将top的数据传出来，并将top.next设置为top

代码如下：

public Object pop() throws Exception {
    if (top == null) {
        throw new Exception("堆栈为空");
    }
    else {
        Object object = top.getElement();
        top = top.getNext();
        return object;
        }
}

队列一般使用循环队列，这样可以避免假溢出，对于顺序表的循环队列代码的实现没有太大的意义，关键是几个判断点需要理解。循环队列有两个指针，分别为front与rear，还有一个记录队列长度的maxsize。front指向当前队列第一个元素所在位置，rear指向最后一个元素后一个位置，通过 front与rear可以对队列的状态进行判断

判断队列为空。当front==rear时，队列为空。
判断队列已满。当（rear+1）%maxsize ==front时，队列已满。
求出队列中的元素个数。number=（rear-front+maxsize）%maxsize。

代码片段