기본 데이터 구조의 설명 (2)

2. 스 택 과 대기 열
스 택 이란 최소 두 개의 기본 작업 을 포함 하 는 추상 적 인 데이터 형식 입 니 다. 새로운 요 소 를 삽입 합 니 다.최근 시간 에 삽 입 된 요 소 를 삭제 합 니 다. FILO (First in, last out, 선진 후 출) 의 원칙 을 따른다.
대기 열 이란 최소 두 개의 기본 동작 을 포함 하 는 추상 적 인 데이터 형식 이기 도 합 니 다. 새로운 요 소 를 삽입 합 니 다.가장 오래 삽 입 된 요 소 를 삭제 합 니 다. FIFO (First in, first out, 선진 선 출) 의 원칙 을 따른다.
창고 와 대열 의 구체 적 인 실현 에 대해 우 리 는 수조 에 의존 할 수도 있 고 체인 테이블 로 실현 할 수도 있다.
1) 스 택 의 배열 구현 방식

public class MyStack<E> {
	public int count;
	public Object [] items;
	
	public boolean isEmpty(){
		return count==0;
	}
	
	public MyStack (){

		items=new Object[20];
		count=0;
	}
	
	public MyStack (int len){

		items=new Object[len];
		count=0;
	}
	
	/**
	         
	**/
	private void resize(int size){
		Object [] newItems=new Object[size];
		for(int i=0;i<count;i++){
			newItems[i]=items[i];
		}
		items=newItems;
	}
	
	public void push(E e){
		if(count==items.length) resize(2*items.length);
		
		items[count++]=e;
	}
	
	public E pop(){
		if(count==0) return null;
		E item=(E)items[count-1];
		items[count-1]=null;
		count--;
		if(count>0&&count<=items.length/4) resize(items.length/2);
		return item;
	}
	
	public E peek(){
		if(count==0) return null;
		
		E item=(E)items[count-1];
		
		return item;
	}
}

2) 창고 의 체인 실현 방식

public class MyStack<E> {
	private class Node{
		E item;
		Node next;
	}
	
	Node head;
	
	public boolean isEmpty(){
		return head==null;
	}
	
	public void push(E t){
		Node node=new Node();
		node.item=t;
		node.next=head;
		head=node;
	}
	
	public E pop(){
		
		if(head==null)
			return null;
		E t=head.item;
		head=head.next;
		
		return t;
	}
	
	public E peek(){
		if(head==null)
			return null;
		else
			return head.item;
	}
}

3) 대기 열의 배열 구현

public class ArrayQueue<E> {
	private int front;
	private int rear;
	private int count;
	private int capacity;
	private int capacityIncrement;
	
	
	private Object[] itemArray;
	
	public ArrayQueue(){
		front=0;
		rear=0;
		count=0;
		capacity=10;
		capacityIncrement=5;
		itemArray=new Object[capacity];
	}
	
	public boolean empty(){
		return count==0;
	}
	
	public void insert(E e){
		if(count==capacity){
			capacity+=capacityIncrement;
			Object [] newArray=new Object[capacity];
//			for(int i=0;i<count;i++){
//				newArray[i]=itemArray[i];
//			}
			if(front<rear){
				//      itemArray[front:rear-1] 
				for(int i=front;i<rear;i++){
					newArray[i]=itemArray[i];
				}
			}else{
				//  ，         
				//  1：itemArray[0:rear-1]
				for(int i=0;i<rear;i++){
					newArray[i]=itemArray[i];
				}
				//  2：itemArray[front:count-1]
				for(int i=front;i<count;i++){
					newArray[i]=itemArray[i];
				}
				
				front+=capacityIncrement;//  ， front        
			}
			itemArray=newArray;
		}
		itemArray[rear]=e;
		rear=(rear+1)%capacity;
		count++;
	}
	
	public E remove(){
		if(count==0){
			return null;
		}
		else{
			E temp=(E) itemArray[front];
			itemArray[front]=null;
			front=(front+1)%capacity;
			count--;
			
			return temp;
		}
	}
}

배열 의 또 다른 간단 한 실현 방식:

import java.util.NoSuchElementException;

public class ArrayQueue {
	protected Object [] data;
	protected int size,
					head,
					tail;
	public ArrayQueue(){
		final int INITIAL_LENGTH=100;
		data=new Object[INITIAL_LENGTH];
		size=0;
		head=0;
		tail=-1;
	}
	
	public int size(){
		return size;
	}
	
	public boolean isEmpty(){
		return size==0;
	}
	
	public Object front(){
		if(size==0)
			throw new NoSuchElementException();
		return data[head];
	}
	
	public void enqueue(Object element){
		if(size==data.length){
			//double the length of data
			Object [] oldData=data;
			data=new Object[data.length*2];
			
			//copy oldData[head...OldData.length-1]
			//to  data[0... OldData.length-1-head] 
			System.arraycopy(oldData, head,data , 0, oldData.length-head);
			
			if(head>0)
				//copy oldData[0...tail] to data [head+1 .. oldlenght-1]
				System.arraycopy(oldData, 0, data, head+1, tail+1);
			head=0;
			tail=oldData.length-1;
		}
		
		tail=(tail+1)%data.length;
		size++;
		data[tail]=element;
	}
	
	public Object dequeue(){
		if(size--==0){
			throw new NoSuchElementException();
		}
		Object element=data[head];
		head=(head+1)%data.length;
		
		return element;
	}
					
}

4) 대기 열의 체인 실현 방식

public class ListQueue<E> {
	private class Node<E>{
		E item;
		Node<E> link;
	}
	
	private Node<E> front,rear;
	private int count;
	
	public boolean empty(){
		return count==0;
	}
	
	public void insert(E e){
		//      
		Node<E> newNode=new Node<E>();
		newNode.item=e;
		
		if(rear==null){
			front=rear=newNode;
		}else{
			rear.link=newNode;
			rear=newNode;
		}
		count++;
	}
	
	public E remove(){
		if(count==0){
			return null;
		}else{
			E e=front.item;
			front=front.link;
			if(front==null){
				rear=null;
			}
			
			count--;
			
			return e;
		}
	}
	
	public ListQueue<E> clone(){
		ListQueue<E> Q=new ListQueue<E>();
		
		for(Node<E> t=front;t!=null;t=t.link)
			Q.insert(t.item);
		return Q;
	}
}