JAVA实现栈(stack)与堆(heap)

Java实现 栈(stack)与堆(heap)

上次写过一个的，下次记得把代码贴上来

待续...

HeapUtil

import java.util.EmptyStackException;
import java.util.Vector;

/**
 * 
 * 模拟 堆，先进先出
 * 
 * @author 
 * @date 2012-6-27 上午02:19:06
 * 
 * @version 1.0
 */
public class HeapUtil<E> extends Vector<E>
{
    /**
     * Creates an empty Stack.
     */
    public HeapUtil()
    {
    }

    /**
     * Pushes an item onto the top of this stack. This has exactly the same
     * effect as: <blockquote>
     * 
     * <pre>
     * addElement(item)
     * </pre>
     * 
     * </blockquote>
     * 
     * @param item
     *            the item to be pushed onto this stack.
     * @return the <code>item</code> argument.
     * @see java.util.Vector#addElement
     */
    public E push(E item)
    {
        addElement(item);

        return item;
    }

    /**
     * Removes the object at the top of this stack and returns that object as
     * the value of this function.
     * 
     * @return The object at the top of this stack (the last item of the
     *         <tt>Vector</tt> object).
     * @exception EmptyStackException
     *                if this stack is empty.
     */
    public synchronized E pop()
    {
        if (empty())
        {
            return null;
        }
        E obj;
        int len = size();

        obj = peek();
        removeElementAt(0);

        return obj;
    }

    /**
     * Looks at the object at the top of this stack without removing it from the
     * stack.
     * 
     * @return the object at the top of this stack (the last item of the
     *         <tt>Vector</tt> object).
     * @exception EmptyStackException
     *                if this stack is empty.
     */
    public synchronized E peek()
    {
        int len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(0);
    }

    /**
     * Tests if this stack is empty.
     * 
     * @return <code>true</code> if and only if this stack contains no items;
     *         <code>false</code> otherwise.
     */
    public boolean empty()
    {
        return size() == 0;
    }

    /**
     * Returns the 1-based position where an object is on this stack. If the
     * object <tt>o</tt> occurs as an item in this stack, this method returns
     * the distance from the top of the stack of the occurrence nearest the top
     * of the stack; the topmost item on the stack is considered to be at
     * distance <tt>1</tt>. The <tt>equals</tt> method is used to compare
     * <tt>o</tt> to the items in this stack.
     * 
     * @param o
     *            the desired object.
     * @return the 1-based position from the top of the stack where the object
     *         is located; the return value <code>-1</code> indicates that the
     *         object is not on the stack.
     */
    public synchronized int search(Object o)
    {
        int i = lastIndexOf(o);

        if (i >= 0)
        {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

StackUtil

/**
 * 
 * 栈 先进后出
 * 
 * @author 
 * @date 2012-6-27 上午08:36:52
 * 
 * @param <E>
 * @version 1.0
 */
public class StackUtil<E> extends Vector<E>
{
    /**
     * Creates an empty Stack.
     */
    public StackUtil()
    {
    }

    /**
     * Pushes an item onto the top of this stack. This has exactly the same
     * effect as: <blockquote>
     * 
     * <pre>
     * addElement(item)
     * </pre>
     * 
     * </blockquote>
     * 
     * @param item
     *            the item to be pushed onto this stack.
     * @return the <code>item</code> argument.
     * @see java.util.Vector#addElement
     */
    public E push(E item)
    {
        
        addElement(item);

        return item;
    }

    /**
     * Removes the object at the top of this stack and returns that object as
     * the value of this function.
     * 
     * @return The object at the top of this stack (the last item of the
     *         <tt>Vector</tt> object).
     * @exception EmptyStackException
     *                if this stack is empty.
     */
    public synchronized E pop()
    {
        if (empty())
        {
            return null;
        }
        E obj;
        int len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * Looks at the object at the top of this stack without removing it from the
     * stack.
     * 
     * @return the object at the top of this stack (the last item of the
     *         <tt>Vector</tt> object).
     * @exception EmptyStackException
     *                if this stack is empty.
     */
    public synchronized E peek()
    {
        int len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * Tests if this stack is empty.
     * 
     * @return <code>true</code> if and only if this stack contains no items;
     *         <code>false</code> otherwise.
     */
    public boolean empty()
    {
        return size() == 0;
    }

    /**
     * Returns the 1-based position where an object is on this stack. If the
     * object <tt>o</tt> occurs as an item in this stack, this method returns
     * the distance from the top of the stack of the occurrence nearest the top
     * of the stack; the topmost item on the stack is considered to be at
     * distance <tt>1</tt>. The <tt>equals</tt> method is used to compare
     * <tt>o</tt> to the items in this stack.
     * 
     * @param o
     *            the desired object.
     * @return the 1-based position from the top of the stack where the object
     *         is located; the return value <code>-1</code> indicates that the
     *         object is not on the stack.
     */
    public synchronized int search(Object o)
    {
        int i = lastIndexOf(o);

        if (i >= 0)
        {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

Test

import java.util.Arrays;

public class Test
{
    public static void main(String[] args)
    {

        MyVec<Integer> m = new MyVec<Integer>(5);
        m.push(1);
        m.push(2);
        m.push(3);
        m.push(4);
        m.push(5);

        System.out.println(Arrays.asList(m.get()));
        System.out.println(Arrays.asList(m.get()));
        System.out.println(Arrays.asList(m.get()));
        System.out.println(Arrays.asList(m.get()));
        System.out.println(Arrays.asList(m.get()));
        m.push(6);
        m.push(7);
        m.push(8);
        System.out.println(Arrays.asList(m.get()));
        m.push(9);
        m.push(10);
        System.out.println(Arrays.asList(m.get()));
        System.out.println(Arrays.asList(m.get()));
        System.out.println(Arrays.asList(m.get()));
        System.out.println(Arrays.asList(m.get()));
        // while (!m.empty())
        // {
        // System.out.println(m.pop());
        // }
    }

    public static void main1(String[] args)
    {
        System.out.println("StackUtil......");
        StackUtil<String> s = new StackUtil<String>();
        s.push("1");
        s.push("2");
        s.push("3");

        while (!s.empty())
        {
            System.out.println(s.pop());
        }

        System.out.println("HeapUtil......");
        HeapUtil<String> h = new HeapUtil<String>();
        h.push("1");
        h.push("2");
        h.push("3");
        while (!h.empty())
        {
            System.out.println(h.pop());
        }

        System.out.println("QueueUtil......");
        QueueUtil<String> q = new QueueUtil<String>();

        q.add("1");
        q.add("2");
        q.add("3");

        for (int i = 0; i < 10; i++)
        {
            System.out.println(q.next());
        }

    }
}

MyVec 是我写的另外一个例子

特殊的缓存列表 首先有500的缓存大小用来入数据， 10缓存的大小用来读取数据, 读完后指针及指向后面了

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
import java.util.Vector;

/**
 * 
 * 特殊的缓存列表 首先有500的缓存大小用来入数据， 10缓存的大小用来读取数据, 读完后指针及指向后面了,
 * 
 * @author bdk197431
 * @date 2013-1-14 上午12:41:00
 * 
 * @version 1.0
 */
public class MyVec<E> extends Vector<E>
{
    /**
     * 总大小，缓存的申请大小,如500
     */
    private int maxSize;

    /**
     * 读取缓存的大小，如10，这个值要小于maxSize
     */
    private int readBuffMaxSize = 2;

    /**
     * 指针的指向的id
     */
    private int startIndex;

    /**
     * 指针的指向的endId
     */
    private int endIndex;

    public MyVec()
    {

    }

    public MyVec(int maxSize)
    {
        this.maxSize = maxSize;
    }

    public void debug(String s)
    {

        // System.out.println(s);
    }

    public String toString()
    {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size(); i++)
        {
            sb.append(elementAt(i));
            if (i != size() - 1)
            {
                sb.append(",");
            }
        }

        sb.append("]");
        return sb.toString();
    }

    public List<E> get()
    {
        debug("get");
        List<E> list = new ArrayList<E>();

        for (int i = startIndex; i < endIndex; i++)
        {

            list.add(get(i));
        }

        if (startIndex + readBuffMaxSize > endIndex)
        {
            startIndex = endIndex;
        } else
        {
            startIndex += readBuffMaxSize;
            endIndex += readBuffMaxSize;
        }

        if (endIndex >= maxSize)
        {
            endIndex = maxSize;
        }
        // readBuffSize = 0;
        debug("start:" + startIndex + " end:" + endIndex);
        debug(this.toString());
        return list;
    }

    public E get(int index)
    {
        if (index >= this.maxSize && index <= endIndex)
        {
            index = index % this.maxSize;
        }

        return elementAt(index);
    }

    /**
     * 
     * 增加 读取缓存的大小
     * 
     * @author
     * @date 2013-1-14 上午03:22:11
     */
    private void addReadBuffSize()
    {
        endIndex++;

        if (endIndex - startIndex > readBuffMaxSize)
        {
            endIndex = startIndex + readBuffMaxSize;
        }

        if (startIndex > 0)
        {
            moveIndex(-1);
        }
    }

    private void moveIndex(int num)
    {
        startIndex += num;
        endIndex += num;
        if (endIndex > maxSize)
        {
            moveIndex(-1);
        }
    }

    /**
     * Pushes an item onto the top of this stack. This has exactly the same
     * effect as: <blockquote>
     * 
     * <pre>
     * addElement(item)
     * </pre>
     * 
     * </blockquote>
     * 
     * @param item
     *            the item to be pushed onto this stack.
     * @return the <code>item</code> argument.
     * @see java.util.Vector#addElement
     */
    public E push(E item)
    {

        debug("push");
        addElement(item);
        if (this.size() > maxSize)
        {
            removeElementAt(0);
            // 指针整体移动一位
            moveIndex(1);

        }
        addReadBuffSize();
        debug("start:" + startIndex + " end:" + endIndex);
        return item;
    }

    /**
     * Removes the object at the top of this stack and returns that object as
     * the value of this function.
     * 
     * @return The object at the top of this stack (the last item of the
     *         <tt>Vector</tt> object).
     * @exception EmptyStackException
     *                if this stack is empty.
     */
    public synchronized E pop()
    {
        if (empty())
        {
            return null;
        }
        E obj;
        int len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * Looks at the object at the top of this stack without removing it from the
     * stack.
     * 
     * @return the object at the top of this stack (the last item of the
     *         <tt>Vector</tt> object).
     * @exception EmptyStackException
     *                if this stack is empty.
     */
    public synchronized E peek()
    {
        int len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    /**
     * Tests if this stack is empty.
     * 
     * @return <code>true</code> if and only if this stack contains no items;
     *         <code>false</code> otherwise.
     */
    public boolean empty()
    {
        return size() == 0;
    }

    /**
     * Returns the 1-based position where an object is on this stack. If the
     * object <tt>o</tt> occurs as an item in this stack, this method returns
     * the distance from the top of the stack of the occurrence nearest the top
     * of the stack; the topmost item on the stack is considered to be at
     * distance <tt>1</tt>. The <tt>equals</tt> method is used to compare
     * <tt>o</tt> to the items in this stack.
     * 
     * @param o
     *            the desired object.
     * @return the 1-based position from the top of the stack where the object
     *         is located; the return value <code>-1</code> indicates that the
     *         object is not on the stack.
     */
    public synchronized int search(Object o)
    {
        int i = lastIndexOf(o);

        if (i >= 0)
        {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}