栈(1)-----栈的实现

Stack 表示后进先出（LIFO）的对象堆栈，也是表的一种。

主要有如下几个方法：

public AnyType push(AnyType x);
public AnyType pop();
public boolean isEmpty();
public AnyType peek();
public int search(AnyType x);

 详细介绍看这里。 这里主要看如何实现。打算用四种方法实现： 数组、Node链、ArrayList和LinkedList

 

所以首先先写一个interface,定义好要实现的方法，如下：

package com.matt.stack;

public interface IStack<AnyType> {

	public AnyType push(AnyType x);
	public AnyType pop();
	public boolean isEmpty();
	public AnyType peek();
	public int search(AnyType x);
}

 

然后用第一种方法数组实现：

package com.matt.stack;

public class MyArrayStack<AnyType> implements IStack<AnyType> {
	private static final int DEFAULT_CAPACITY = 2;
	private AnyType[] theItems;
	private int thetopOfStack;

	public MyArrayStack() {
		doClear();
	}

	public void clear() {
		doClear();
	}

	private void doClear() {
		thetopOfStack = -1;
		ensureCapacity(DEFAULT_CAPACITY);
	}

	public AnyType push(AnyType x) {
		if (theItems.length == size())
			ensureCapacity(size() + 1);
		theItems[++thetopOfStack] = x;
		return x;
	}

	public AnyType pop() {
		if (thetopOfStack == -1)
			throw new ArrayIndexOutOfBoundsException();
		return theItems[thetopOfStack--];
	}

	public AnyType peek() {
		return theItems[thetopOfStack];
	}

	@Override
	public int search(AnyType x) {
		if (x == null) {
			for (int i = 0; i < theItems.length; i++)
				if (theItems[i] == null)
					return size() - i;
		} else
			for (int i = 0; i < theItems.length; i++)
				if (theItems[i].equals(x))
					return size() - i;

		return -1;

	}

	private void ensureCapacity(int newCapacity) {
		AnyType[] old = theItems;
		theItems = (AnyType[]) new Object[newCapacity];
		for (int i = 0; i < size(); i++)
			theItems[i] = old[i];
	}

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

	private int size() {
		return thetopOfStack + 1;
	}

	public String toString() {
		String l = "[";
		for (int i = 0; i < size(); i++) {

			if (i == size() - 1)
				l += theItems[i];
			else
				l += theItems[i] + ",";

		}
		l += "]";
		return l;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyArrayStack<String> stack = new MyArrayStack<String>();
		System.out.println(stack);
		stack.push("1");
		stack.push("2");
		stack.push("3");
		stack.push("4");
		System.out.println(stack.search("1"));
		System.out.println(stack);
		stack.pop();
		stack.pop();

		System.out.println(stack);
		System.out.println(stack.peek());
		stack.clear();
		System.out.println(stack);

	}

}

 

第二种方法Node链：

package com.matt.stack;

public class MyLinkedStack<AnyType> implements IStack<AnyType> {
	private Node<AnyType> beginMarker;
	private int theSize;

	public MyLinkedStack() {
		clear();
	}

	public void clear() {
		theSize = 0;
		beginMarker = new Node<AnyType>(null, null);
	}

	public AnyType pop() {
		AnyType data = peek();
		theSize--;
		return data;
	}

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

	@Override
	public int search(AnyType x) {
		Node<AnyType> p = beginMarker;
		if (x == null) {
			for (int i = 0; i < size(); i++)
				if ((p = p.next).data == null)
					return size() - i;
		} else {
			for (int i = 0; i < size(); i++)
				if ((p = p.next).data.equals(x))
					return size() - i;
		}
		return -1;
	}

	public AnyType peek() {
		return getLastNode().data;
	}

	private Node<AnyType> getLastNode() {
		Node<AnyType> p = beginMarker;
		for (int i = 0; i < size(); i++)
			p = p.next;

		return p;
	}

	public AnyType push(AnyType x) {
		Node<AnyType> last = getLastNode();
		Node<AnyType> newNode = new Node<AnyType>(x, null);
		last.next = newNode;
		theSize++;
		return x;
	}

	private int size() {
		return theSize;
	}

	private static class Node<AnyType> {
		public AnyType data;
		public Node<AnyType> next;

		public Node(AnyType d, Node<AnyType> n) {
			this.data = d;
			this.next = n;
		}

	}

	public String toString() {
		String l = "[";
		Node<AnyType> p = beginMarker;
		for (int i = 0; i < size(); i++) {

			p = p.next;
			if (i == size() - 1)
				l += p.data;
			else
				l += p.data + ",";

		}
		l += "]";
		return l;
	}

	public static void main(String[] args) {
		MyLinkedStack<String> stack = new MyLinkedStack<String>();
		System.out.println(stack);
		stack.push("1");
		stack.push("2");
		stack.push("3");
		stack.push("4");
		System.out.println(stack.search("3"));
		System.out.println(stack);
		stack.pop();
		stack.pop();

		System.out.println(stack);
		System.out.println(stack.peek());
		stack.clear();
		System.out.println(stack);
	}

}

 

第三种 ArrayList

package com.matt.stack;

import java.util.*;

import com.matt.MyArrayList;

public class MyArrayListStack<AnyType> implements IStack<AnyType> {
	private List<AnyType> theItems = new ArrayList<AnyType>();

	public MyArrayListStack() {

	}

	public AnyType push(AnyType x) {
		theItems.add(x);
		return x;
	}

	public AnyType pop() {
		return theItems.remove(theItems.size() - 1);
	}

	public AnyType peek() {
		return theItems.get(theItems.size() - 1);
	}

	public void clear() {
		theItems = new ArrayList<AnyType>();
	}

	@Override
	public boolean isEmpty() {
		return theItems.size() == 0;
	}

	@Override
	public int search(AnyType x) {
		if (x == null) {
			for (int i = 0; i < size(); i++)
				if (theItems.get(i) == null)
					return size() - i;
		} else
			for (int i = 0; i < size(); i++)
				if (theItems.get(i).equals(x))
					return size() - i;

		return -1;
	}

	private int size() {
		return theItems.size();
	}

	public String toString() {
		String l = "[";

		for (int i = 0; i < theItems.size(); i++) {
			if (i == theItems.size() - 1)
				l += theItems.get(i);
			else
				l += theItems.get(i) + ",";

		}
		l += "]";
		return l;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MyArrayListStack<String> stack = new MyArrayListStack<String>();
		System.out.println(stack);
		stack.push("1");
		stack.push("2");
		stack.push("3");
		stack.push("4");
		System.out.println(stack.search("1"));
		System.out.println(stack);
		stack.pop();
		stack.pop();

		System.out.println(stack);
		System.out.println(stack.peek());
		stack.clear();
		System.out.println(stack);
	}
}

 写第三种的时候发现几乎和第一种差不多，所以第4种有了前面几种的示范应该很简单，特别是第二种，这里就不实现了。

 

下一节主要以一个四则运行表达式转逆波兰式来总结一下stack的运用。