데이터 구조 - 창고 의 선형 표 실현

스 택 은 선형 표를 통 해 실현 할 수 있 고 순서 저장 구조 실현 과 체인 저장 구조 로 나 눌 수 있다.
순서 구 조 는 다음 과 같다.
package stack_and_queue;

import java.util.Arrays;

public class ArrayStack {
	
	private final int DEFAULT_VALUE = 10; 
	private Object[] elementData;//         
	private int size=0;//         
	
	
	public ArrayStack(){//       
		elementData=new Object[DEFAULT_VALUE];
	}
	
	public ArrayStack(int initSize){//          
		elementData=new Object[initSize];
	}
	
	public void ensureSize(int minSize){//         
		int capacity=elementData.length;
		while (minSize>capacity){
			capacity<<=1;
		}
		elementData=Arrays.copyOf(elementData, capacity);
	}
	
	public void push(T element){//  
		ensureSize(size+1);
		elementData[size++]=element;
	}
	
	public T pop(){//  
		if(elementData[0]!=null){
			T value=(T)elementData[size-1];
			elementData[size-1]=null;
			size--;
			return value;
		}
		else
			return null;
	}
	
	
	public String toString(){
		if (size ==0){
			return "[]";
		}
		else{
			StringBuilder sb =new StringBuilder("[");
			for(int i=size-1;i>-1;i--){
				sb.append(elementData[i].toString()+",");
			}
			int len=sb.length();
			return sb.delete(len-1, len).append("]").toString();	
		}
	}
	
	public static void main (String[] args){//  
		ArrayStack as =new ArrayStack(16);
		as.push("String");
		as.push(" ");
		as.push("haha");
		System.out.println(as);
		as.pop();
		System.out.println(as);
		as.pop();
		System.out.println(as);
	}
}

체인 구 조 는 다음 과 같다.
package stack_and_queue;

class Node{
	public Node next;
	public T data;
	
	public Node(){
		this.next=null;
		this.data=null;
	}
	public Node(T data,Node next){
		this.next=next;
		this.data=data;
	}
}
public class LinkStack {
	private Node head;
	private int size=0;
	
	public LinkStack(){
		head = null;
	}
	
	public LinkStack(T element){
		head=new Node(element,null);
		size++;
	}
	
	public void push(T element){//        
		Node n=new Node(element,head);
		head=n;
		size++;
	}
	
	public T pop(){//        
		Node returnNode = head;
		head=head.next;
		returnNode.next=null;
		size--;
		return (T) returnNode.data;
		
	}
	
	public String toString(){
		if(size==0){
			return "[]";
		}
		else{
			StringBuilder sb=new StringBuilder("[");
			for(Node i=head;i != null;i=i.next){
				sb.append(i.data.toString()+",");
			}
			int len=sb.length();
			return sb.delete(len-1, len).append("]").toString();
		}
	}
	
	public static void main(String[] args){
		LinkStack ls =new LinkStack("haha");
		ls.push("String");
		ls.push(" ");
		ls.push("xixi");
		System.out.println(ls);
		ls.pop();
		System.out.println(ls);
		ls.pop();
		System.out.println(ls);
		
	}
}

좋은 웹페이지 즐겨찾기