普林斯顿算法课第二周:stack

在日常工作中，我们经常会需要用到集合，但是一个有一个必须要考虑的问题是，集合中的元素应该怎么置入和移除，stack和queue就是这个问题的描述，本文根据课程内容，给出了stack的两种实现方法。

基础知识回顾

stack

stack是常用的一种数据结构，简单来说，stack是一种后进先出的数据结构。通常包含如下几个方法：

• pop: 移除stack最近增加的一个元素

• push：增加一个元素到stack

• isEmpy: 是否为空

• size： 可选，返回包含的元素个数

代码实现

使用链表实现stack：

使用链表实现的stack，操作起来比较方便，但是每次都需要创建新的对象，开销比较大。

package com.andy.stack;

public class LinkedStackOfString {
    /*
     * 使用链表的形式实现stack
     * stack的特点，后进先出
     * */

    private Node first = null;
    private int size = 0;

    private class Node{
        /*
         * 链表的单个节点
         * item为当前值
         * next为下一个节点
         * */
        String item;
        Node next;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public String pop(){
        /*
         * 出栈操作：去掉最第一个（栈顶）元素
         * 下一个元素成为第一个（栈顶）元素
         * */
        String item = first.item;
        first = first.next;
        --size;
        return item;
    }

    public void push(String item){
        /*
         * 入栈操作：增加一个元素，成为第一个（栈顶）元素
         * 先前的栈顶元素，变为第二个
         * */
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        ++size;
    }

    public int size(){
        return size;
    }
}

使用数组实现stack

使用数组实现stack可以实现比较快速的置入和移除操作,但在数组尺寸不足是需要线性时间去扩充数组.同样的,当数组过大时,还需要限行时间去缩小数组,以节约空间.

package com.andy.stack;

import java.lang.reflect.Array;

public class ResizingArrayStackOfString {

    /*
    * stack使用数组来实现
    * 当前栈顶元素下表为N
    * push操作时 设置N+1为要插入的元素 N自增
    * pop操作时 设置N为null N减小1
    * push操作中，如果数组越界，则扩充数组到原来的两倍大小
    * pop操作中，如果当前stack的大小为数组长度的1/4，则调整数组长度为原来的一半
    * */

    private String[] s;
    private int N = 0;

    public ResizingArrayStackOfString(){
        s = new String[1];
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public void push(String item){
        //如果数组不够用啦，扩充一倍
        if ( N == s.length ){
            resize(s.length * 2);
        }
        s[N++] = item;
    }

    public String pop(){
        //pop操作，设当前N位置的元素为null
        String item = s[N];
        s[N] = null;
        N--;
        //如果当前stack只占数组的1/4，则舍弃数组后一半
        if ( N > 0 && N == s.length/4)
            resize(s.length/2);
        return item;
    }

    public void resize(int capacity){
        //调整数组空间
        String[] copy = new String[capacity];
        for( int i = 0; i < s.length; i++)
            copy[i] = s[i];
        s = copy;
    }

}