제3장 자료구조

1. 제3장 자료구조
   1. 3.7 스택
   2. 문서에 대하여

3.7 스택

설명

3.7.1 순차자료구조 방식을 이용한 스택의 예

import java.util.Arrays;
import java.util.EmptyStackException;

public class ArrayStack {

	private Object Elements[] = null;
	private int size = 0;
	private static final int DEFAULT_INITIAL_CAPACITY = 16;
	
	
	public ArrayStack() {
		Elements = new Object[DEFAULT_INITIAL_CAPACITY];
	}
	
	public void push(Object e) {
		upgradeCapacity();
		this.Elements[size++] = e;
	}
	
	public Object pop(){
		if(size == 0)
			throw new EmptyStackException();
		
		Object rtnObj = Elements[--size];
		Elements[size] = null;
		return rtnObj;
		
	}
	
	private void upgradeCapacity() {
		if(Elements.length == size){
			Elements = Arrays.copyOf(Elements, size * 2);
		}
	}
	
}

3.7.2 연결자료구조 방식을 이용한 스택의 예

public interface Stack {

	boolean isEmpty();
	void push(String s);
	String pop();
	void delete();
	
}


public class StackNode {

	public String data =  null;
	public StackNode link = null;
	
	public StackNode (){
		this.data = null;
	}
	
	public StackNode (String data){
		this.data = data;
	}
	
}

public class LinkedListStack implements Stack {

	private StackNode head = null;
	private StackNode tail = null;
	public	int length = 0;
	
	public void delete() {

		
		pop();
	}

	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return (this.length < 1);
	}

	public String pop() {
		// TODO Auto-generated method stub
		StackNode rntval = null;
		
		if (isEmpty()){
			throw new NullPointerException("스택이 비었습니다.");
//			return "데이터가 없습니다.";
		}else{
			System.out.println(tail.data);			
			rntval= tail;
			
			// 연결을 끊자.
			StackNode temp = this.head; 

			for(int i=0; i < length -2; i++) {
				temp = temp.link;
			}
/*
			try {
			    while (temp.link.link != null)
				temp = temp.link;	
			} catch (Exception e) {
				// TODO: handle exception
			}
*/


			temp.link = null;
			tail = temp;			
			length--;
			
		}
			
		return rntval.data;
		
	}

	public void push(String s) {
		// TODO Auto-generated method stub
		StackNode newStackNode = new StackNode(s);
		if(isEmpty()){
			this.head = newStackNode;
		}else{
			this.tail.link = newStackNode;
		}
		
		System.out.println(s + "가들었습니다.");
		this.tail = newStackNode;
			++length;
	}	
	
	public static void main(String[] args) {
		
		LinkedListStack lls = new LinkedListStack();
		for (int i = 1; i < 10; i++) {
			lls.push("" + i);
		}
		
		for (int i = 1; i < 15; i++) {
			lls.pop();
		}		
		
	}
}

public class LinkedListStackMain {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		LinkedListStack lls = new LinkedListStack();
		lls.pop();
		
		for(int i=1 ; i < 10; i ++){
			lls.push(" " + i);
		}
		
		while (lls.length > 0) {
			lls.pop();
		}
		
	}
}

문서에 대하여

• 이 문서의 내용은 C로 배우는 알고리즘 (1) 교재를 스터디 하면서 정리한 내용 입니다.
• 최초작성자 : 허용운
• 최초작성일 : 2009년 2월 25일
• 이 문서는 오라클클럽 자바 웹개발자 스터디 모임에서 작성하였습니다.
• 이 문서를 다른 블로그나 홈페이지에 퍼가실 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^\^