창고(1)-----창고의 실현

Stack은 후진선출(LIFO)의 대상 창고를 나타내는 것도 표의 일종이다.
주로 다음과 같은 몇 가지 방법이 있다.

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

자세히 소개여기..여기서는 주로 어떻게 실현하는가에 달려 있다.네 가지 방법으로 실현할 계획이다: 그룹, 노드 체인, Array List, Linked List
 
그래서 먼저 인터페이스 하나를 쓰고 실현할 방법을 정의한다. 다음과 같다.

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);
	}
}

세 번째를 썼을 때 첫 번째와 거의 차이가 나지 않았기 때문에 네 번째는 앞의 몇 가지 시범이 있으면 간단할 것이다. 특히 두 번째는 여기서 실현되지 않을 것이다.
 
다음 절은 주로 네 가지 운행 표현식의 역폴란드식으로 Stack의 운용을 정리한다.