* 스택은 배열 혹은 링크드 리스트 두개다 작성이 가능하다.

* Java Stack API를 확인해보니 배열기반으로 작성되어있음

* 그래서 나도 한번 배열로 작성해 보았다

* 이번 테스트는 Main에서 진행



Stack 클래스 
package algo.stack;

public class MyStack<E> {

	private int top;
	private int initialCapacity;
	private int capacity;
	private Object[] arr;

	public MyStack() {
		
		top = -1;
		initialCapacity = 1;
		capacity = initialCapacity;
		arr = new Object[initialCapacity];
		
	}

	public E push(E item){
		
		if(isFull())
			reAllocate();
		
		top++;
		
		arr[top] = item;
		
		return (E)item;
	}

	private void reAllocate() {
		
		Object[] newArr = new Object[capacity * 2];
		for (int i = 0; i < arr.length; i++) {
			newArr[i] = arr[i]; 
		}
		arr = newArr;
		capacity = capacity * 2;
	}

	public E pop() {

		if (isEmpty())
			return null;

		Object item = arr[top];
		arr[top] = null;
		top--;

		return (E)item;
	}
	
	public E peek() {
		
		if(isEmpty())
			return null;
		
		return (E)arr[top];
		
	}
	
	private boolean isFull() {
		return top == capacity - 1;
	}
	
	public boolean isEmpty() {
		return top == -1;
	}

	@Override
	public String toString() {
		
		StringBuilder builder = new StringBuilder();
		builder.append("Current Capacity : " + capacity);
		builder.append("\tCurrent Top : " + top);
		builder.append(", ");
		builder.append("[");
		for (int i = 0; i < arr.length; i++) {
			if(i == arr.length - 1)
				builder.append(arr[i]);
			else
				builder.append(arr[i] + ",");
				
		}
		builder.append("]");
		
		return builder.toString();
	}
	
}
테스트 
import algo.stack.MyStack;

public class Main {

	public static void main(String[] args) {
		
		MyStack<String> stack = new MyStack<>();
		
		System.out.println(" * PUSH : " + stack.push("01"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("02"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("03"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("04"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("05"));
		System.out.println(stack);
		System.out.println(" * PEEK : " + stack.peek());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		
		System.out.println(" * PUSH : " + stack.push("06"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("07"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("08"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("09"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("10"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("11"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("12"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("13"));
		System.out.println(stack);
		System.out.println(" * PUSH : " + stack.push("14"));
		System.out.println(stack);
		
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		System.out.println(" * POP : " + stack.pop());
		System.out.println(stack);
		
	}
}
결과 
 * PUSH : 01
Current Capacity : 1	Current Top : 0, [01]
 * PUSH : 02
Current Capacity : 2	Current Top : 1, [01,02]
 * PUSH : 03
Current Capacity : 4	Current Top : 2, [01,02,03,null]
 * PUSH : 04
Current Capacity : 4	Current Top : 3, [01,02,03,04]
 * PUSH : 05
Current Capacity : 8	Current Top : 4, [01,02,03,04,05,null,null,null]
 * PEEK : 05
Current Capacity : 8	Current Top : 4, [01,02,03,04,05,null,null,null]
 * POP : 05
Current Capacity : 8	Current Top : 3, [01,02,03,04,null,null,null,null]
 * POP : 04
Current Capacity : 8	Current Top : 2, [01,02,03,null,null,null,null,null]
 * POP : 03
Current Capacity : 8	Current Top : 1, [01,02,null,null,null,null,null,null]
 * PUSH : 06
Current Capacity : 8	Current Top : 2, [01,02,06,null,null,null,null,null]
 * PUSH : 07
Current Capacity : 8	Current Top : 3, [01,02,06,07,null,null,null,null]
 * PUSH : 08
Current Capacity : 8	Current Top : 4, [01,02,06,07,08,null,null,null]
 * PUSH : 09
Current Capacity : 8	Current Top : 5, [01,02,06,07,08,09,null,null]
 * PUSH : 10
Current Capacity : 8	Current Top : 6, [01,02,06,07,08,09,10,null]
 * PUSH : 11
Current Capacity : 8	Current Top : 7, [01,02,06,07,08,09,10,11]
 * PUSH : 12
Current Capacity : 16	Current Top : 8, [01,02,06,07,08,09,10,11,12,null,null,null,null,null,null,null]
 * PUSH : 13
Current Capacity : 16	Current Top : 9, [01,02,06,07,08,09,10,11,12,13,null,null,null,null,null,null]
 * PUSH : 14
Current Capacity : 16	Current Top : 10, [01,02,06,07,08,09,10,11,12,13,14,null,null,null,null,null]
 * POP : 14
Current Capacity : 16	Current Top : 9, [01,02,06,07,08,09,10,11,12,13,null,null,null,null,null,null]
 * POP : 13
Current Capacity : 16	Current Top : 8, [01,02,06,07,08,09,10,11,12,null,null,null,null,null,null,null]
 * POP : 12
Current Capacity : 16	Current Top : 7, [01,02,06,07,08,09,10,11,null,null,null,null,null,null,null,null]
저작자표시 비영리 변경금지 (새창열림)

'Data Structure - Using java' 카테고리의 다른 글

Queue - Created as LinkedList  (0) 2018.05.24
Doubly Linked List  (0) 2018.05.23
Linked List  (0) 2018.05.22

1. 양방향 링크드 리스트

2. 람다식 가볍게 실습

3. 단위테스트 실습 (일부 기능만 테스트)

4. Required Lib : Jjunit-4.12.jar, hamcrest-core-1.3.jar


* Node 클래스

public class MyDoublyLinkedNode<E> {

	private E item;
	private MyDoublyLinkedNode<E> next;
	private MyDoublyLinkedNode<E> prev;
	
	public MyDoublyLinkedNode(E item) {
		super();
		this.item = item;
	}

	public E getItem() {
		return item;
	}

	public void setItem(E item) {
		this.item = item;
	}

	public MyDoublyLinkedNode<E> getNext() {
		return next;
	}

	public void setNext(MyDoublyLinkedNode<E> next) {
		this.next = next;
	}

	public MyDoublyLinkedNode<E> getPrev() {
		return prev;
	}

	public void setPrev(MyDoublyLinkedNode<E> prev) {
		this.prev = prev;
	}

	@Override
	public String toString() {
		String nextStr = next == null ? "null" : next.item.toString();
		String prevStr = prev == null ? "null" : prev.item.toString();
		return String.format("MyDoublyLinkedNode [item=%s, next=%s, prev=%s]", item, nextStr, prevStr);
	}
}

* Container 클래스

import java.util.function.Consumer;

public class MyDoublyLinkedList<E> {


	private MyDoublyLinkedNode<E> head;
	private MyDoublyLinkedNode<E> tail;
	private int size;

	public MyDoublyLinkedList() {
		super();
	}

	
	public MyDoublyLinkedNode<E> getHead() {
		return head;
	}

	public MyDoublyLinkedNode<E> getTail() {
		return tail;
	}

	public int getSize() {
		return size;
	}
	
	public E find(E newItem) {
		MyDoublyLinkedNode<E> item = findWrap(newItem);
		return item != null ? item.getItem() : null;
	}
	
	public E findByIdx(int index) {
		MyDoublyLinkedNode<E> item = findWrapByIdx(index);
		return item != null ? item.getItem() : null;
	}
	
	public MyDoublyLinkedNode<E> findWrap(E newItem){
	
		if(newItem == null)
			return null;
		
		if(head == null)
			return null;
		
		MyDoublyLinkedNode<E> search = head;
		while (search != null) {
			
			if (search.getItem().equals(newItem)) {
				break;
			}
			search = search.getNext();
		}
		
		return search;
	}
	
	public MyDoublyLinkedNode<E> findWrapByIdx(int index){
		
		if (index < 0)
			return null;
		
		if(index >= size)
			return null;
		
		if(size <= 0)
			return null;

		MyDoublyLinkedNode<E> search = null;
		
		//앞 , 뒤  검색할 시작지점 선택
		if(index > size / 2) {
			
			//tail 시작
			search = tail;
			for (int i = size - 1; i > index; i--) {
				search = search.getPrev();
				if (search == null) break;
			}
			
		}else {
			
			//head 시작
			search = head;
			for (int i = 0; i < index; i++) {
				search = search.getNext();
				if (search == null) break;
			}
			
		}

		return search;
	}
	
	
	public void add(E newItem) {

		if(head == null && tail == null) {
			//비어있는 경우
			addFirst(newItem);
		}else {
			//아이템이 하나 이상, 마지막에 추가해준다. 
			addLast(newItem);
		}
		
	}
	
	private void addEnds(Consumer<MyDoublyLinkedNode<E>> consumer, MyDoublyLinkedNode<E> newItemWrap) {
		
		
		if(head == null && tail == null) {
			//비어있는 경우
			head = newItemWrap;
			tail = newItemWrap;
			
		}else {
			consumer.accept(newItemWrap);
		}

	}
	
	public void addFirst(E newItem) {
		
		MyDoublyLinkedNode<E> newItemWrap = new MyDoublyLinkedNode<>(newItem);
		addEnds(T -> {
			newItemWrap.setNext(head);
			newItemWrap.setPrev(null);
			head.setPrev(T);
			head = T;
		}, newItemWrap);
		
		size++;
	}
	
	public void addLast(E newItem) {
		
		MyDoublyLinkedNode<E> newItemWrap = new MyDoublyLinkedNode<>(newItem);
		addEnds(T -> {
			newItemWrap.setNext(null);
			newItemWrap.setPrev(tail);
			tail.setNext(T);
			tail = T;
		}, newItemWrap);
		
		size++;
	}
	
	public void addBefore(E before, E newItem) {
		
		if(before == null || newItem == null)
			return;
		
		MyDoublyLinkedNode<E> beforeWrap = findWrap(before);
		
		if(beforeWrap == null)
			return;
		
		if(head == tail){
			//한개만 존재
			addFirst(newItem);
			
		}else if(head != tail && head == beforeWrap){
			//두개 이상 존재, before가 head인 경우
			addFirst(newItem);
			
		}else if(head != tail && head != beforeWrap) {
			//두개 이상 존재, before가 head가 아닌 경우
			
			MyDoublyLinkedNode<E> newItemWrap = new MyDoublyLinkedNode<>(newItem);
			newItemWrap.setNext(beforeWrap);
			newItemWrap.setPrev(beforeWrap.getPrev());
			
			beforeWrap.getPrev().setNext(newItemWrap);
			beforeWrap.setPrev(newItemWrap);
			
			size++;
			
		}else {
			
			throw new RuntimeException("Catch addBefore bug");
			
		}

	}

	public void addAfter(E after, E newItem) {
	
		if(after == null || newItem == null)
			return;
		
		MyDoublyLinkedNode<E> afterWrap = findWrap(after);
		
		if(afterWrap == null)
			return;
		
		if(head == tail){
			//한개만 존재
			addLast(newItem);
			
		}else if(head != tail && tail == afterWrap){
			//두개 이상 존재, after가 tail인 경우
			addLast(newItem);
			
		}else if(head != tail && tail != afterWrap) {
			//두개 이상 존재, after가 tail이 아닌 경우
			
			MyDoublyLinkedNode<E> newItemWrap = new MyDoublyLinkedNode<>(newItem);
			newItemWrap.setNext(afterWrap.getNext());
			newItemWrap.setPrev(afterWrap);
			
			afterWrap.getNext().setPrev(newItemWrap);
			afterWrap.setNext(newItemWrap);
			
			size++;
			
		}else {
			
			throw new RuntimeException("Catch addAfter bug");
			
		}
	}
	
	public void addByIdx(int index, E newItem) {
		
		if(index < 0)
			return;
		
		if(index >= size)
			return;
		
		if(index == 0)
			addFirst(newItem);
		else
			addBefore(findByIdx(index), newItem);
		
	}
	
	private void remove(MyDoublyLinkedNode<E> targetWrap) {
		
		if(targetWrap == null)
			return;
		
		if(head == tail){
			//전체 아이템이 한개인 경우
			clear();
			return;
			
		}else if(head != tail && targetWrap == head) {
			//전체 아이템 두개 이상, head인 경우
			head = targetWrap.getNext();
			targetWrap.getNext().setPrev(null);
			targetWrap.setNext(null);
			targetWrap.setPrev(null);
			
		}else if(head != tail && targetWrap == tail) {
			//전체 아이템 두개 이상, tail인 경우
			tail = targetWrap.getPrev();
			targetWrap.getPrev().setNext(null);
			targetWrap.setNext(null);
			targetWrap.setPrev(null);
			
		}else {
			//나머지 경우
			targetWrap.getPrev().setNext(targetWrap.getNext());
			targetWrap.getNext().setPrev(targetWrap.getPrev());
			targetWrap.setNext(null);
			targetWrap.setPrev(null);
		}
		
		size--;
		
	}
	
	public void remove(E targetItem) {
		
		MyDoublyLinkedNode<E> targetWrap = findWrap(targetItem);
		remove(targetWrap);
		
	}
	
	public void removeFirst() {
		
		if(head != null)
			remove(head);
		
	}
	
	public void removeLast() {
		
		if(tail != null)
			remove(tail);
		
	}
	
	public void removeByIdx(int index) {
		remove(findWrapByIdx(index));
	}
	
	
	public void removeBefore(E beforeItem) {
		
		MyDoublyLinkedNode<E> beforeWrap = findWrap(beforeItem);
		remove(beforeWrap.getPrev());
		
	}
	
	public void removeAfter(E afterItem) {
		
		MyDoublyLinkedNode<E> afterWrap = findWrap(afterItem);
		remove(afterWrap.getNext());
		
	}
	
	public void clear() {
		
        for (MyDoublyLinkedNode<E> x = head; x != null; ) {
        	MyDoublyLinkedNode<E> next = x.getNext();
            x.setItem(null);
            x.setNext(null);
            x.setPrev(null);
            x = next;
        }
        head = tail = null;
        size = 0;
        
	}
	
	
	@Override
	public String toString() {

		StringBuilder builder = new StringBuilder();

		if(head != null)
			builder.append("HEAD : " + head + "\nTAIL : " + tail + "\n");
		
		MyDoublyLinkedNode<E> search = head;
		while (search != null) {
			builder.append(search.toString());
			builder.append("\n");
			search = search.getNext();
		}

		builder.append("total size = " + size);

		return builder.toString();
	}	
}

* 단위테스트

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotEquals;
import static org.junit.Assert.assertNull;

import org.junit.Test;

public class TestMyDoublyLinkedList {

	private MyDoublyLinkedList<String> list = new MyDoublyLinkedList<>();
	
	@Test
	public void testAdd() {
		
		list.add("11");
		assertEquals("11", list.find("11"));
		assertEquals(list.getHead(), list.findWrap("11"));
		assertEquals(list.getTail(), list.findWrap("11"));
		
		list.add("22");
		
		assertNotEquals("11", list.find("22"));
		assertEquals("22", list.find("22"));
		assertEquals(list.getHead(), list.findWrap("11"));
		assertEquals(list.getTail(), list.findWrap("22"));
		assertEquals(list.findWrap("11").getNext(), list.findWrap("22"));
		assertEquals(list.findWrap("22").getPrev(), list.findWrap("11"));
		assertNull(list.findWrap("11").getPrev());
		assertNull(list.findWrap("22").getNext());
		
	}
	
	@Test
	public void testAddAfter() {
		
		list.add("11");
		list.addAfter("11", "22");
		
		//1개만 존재 테스트
		assertEquals(list.findWrap("11").getNext(), list.findWrap("22"));
		assertEquals(list.findWrap("22").getPrev(), list.findWrap("11"));
		
		//2개 이상 존재, after가 tail 아님
		list.addAfter("11", "11.5");
		assertEquals(list.findWrap("11").getNext(), list.findWrap("11.5"));
		assertEquals(list.findWrap("11.5").getPrev(), list.findWrap("11"));
		assertNotEquals(list.findWrap("22").getPrev(), list.findWrap("11"));
		
		//2개이상 존재, after가 tail
		list.addAfter("22", "33");
		assertEquals(list.findWrap("22").getNext(), list.findWrap("33"));
		assertEquals(list.findWrap("33").getPrev(), list.findWrap("22"));
		
		assertEquals(list.getHead(), list.findWrap("11"));
		assertEquals(list.getTail(), list.findWrap("33"));
		
		assertNull(list.findWrap("11").getPrev());
		assertNull(list.findWrap("33").getNext());
		
		assertEquals(4, list.getSize());
	}
	
	
	@Test
	public void testListSize() {

		assertEquals(0, list.getSize());
		
		list.add("11");
		list.add("22");
		list.add("33");
		list.add("44");
		list.add("55");
		list.add("66");
		
		assertEquals(6, list.getSize());
		
		list.add("77");
		
		assertEquals(7, list.getSize());
		
		list.addAfter("77", "88");
		
		assertEquals(8, list.getSize());
		
		list.addBefore("77", "66.5");
		
		assertEquals(9, list.getSize());
		
		list.addByIdx(99, "Nothing");
		
		assertEquals(9, list.getSize());
		
		list.addByIdx(0, "00");
		
		assertEquals(10, list.getSize());
		
		list.addFirst("-11");
		
		assertEquals(11, list.getSize());
		
		list.addLast("99");
		
		assertEquals(12, list.getSize());
		
		list.removeLast();
		
		assertEquals(11, list.getSize());
		
		list.removeLast();
		
		assertEquals(10, list.getSize());
		
		list.removeByIdx(99);
		
		assertEquals(10, list.getSize());
		
		list.removeByIdx(3);
		
		assertEquals(9, list.getSize());
		
		list.removeBefore("66");
		
		assertEquals(8, list.getSize());
		
		list.removeAfter("11");
		
		assertEquals(7, list.getSize());
		
		list.remove("-11");
		
		assertEquals(6, list.getSize());
		
		list.clear();
		
		assertEquals(0, list.getSize());
		
	}


}


저작자표시 비영리 변경금지 (새창열림)

'Data Structure - Using java' 카테고리의 다른 글

Queue - Created as LinkedList  (0) 2018.05.24
Stack - Created as Array  (0) 2018.05.24
Linked List  (0) 2018.05.22
Item Wrapper 
public class MyLinkedNode<E> {

	private E item;
	private MyLinkedNode<E> next;
	
	public MyLinkedNode(E item) {
		this.item = item;
	}

	public E getItem() {
		return item;
	}

	public MyLinkedNode<E> getNext() {
		return next;
	}

	public void setNext(MyLinkedNode<E> next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return String.format("MyNode [item=%s]", item);
	}
	
}
Item Container 

public class MyLinkedList<E> {

	private MyLinkedNode<E> head;
	private int size;

	public int getSize() {
		return size;
	}

	public MyLinkedNode<E> find(E item) {

		MyLinkedNode<E> search = head;
		while (search != null) {

			if (search.getItem().equals(item)) {
				break;
			}
			search = search.getNext();
		}
		return search;
	}

	public MyLinkedNode<E> getItemByIdx(int index) {

		if (index < 0)
			return null;

		MyLinkedNode<E> search = head;
		for (int i = 0; i < index; i++) {
			search = search.getNext();
			if (search == null)
				break;
		}

		return search;
	}

	public void addFirst(E newItem) {

		if (newItem == null)
			return;

		MyLinkedNode<E> newNode = new MyLinkedNode<>(newItem);

		if (head != null) {
			newNode.setNext(head);
		}

		head = newNode;

		size++;
	}

	public void addAfter(E prev, E newItem) {

		if (prev == null)
			return;

		if (newItem == null)
			return;

		MyLinkedNode<E> newNode = new MyLinkedNode<>(newItem);
		MyLinkedNode<E> search = find(prev);
		if (search != null) {
			newNode.setNext(search.getNext());
			search.setNext(newNode);
			size++;
		}

	}

	public void addByIndex(int index, E newItem) {

		if (index < 0)
			return;

		if (index > size)
			return;

		if (index == 0) {
			addFirst(newItem);
		} else {

			MyLinkedNode<E> prevFoundItem = getItemByIdx(index - 1);
			if (prevFoundItem == null)
				return;

			addAfter(prevFoundItem.getItem(), newItem);
		}

	}
	
	public void removeFirst() {
		if(head != null) {
			head = head.getNext();
			size--;
		}
	}
	
	public void removeAfter(E prev) {

		if (prev == null)
			return;

		MyLinkedNode<E> search = find(prev);
		if (search == null || search.getNext() == null) {
			return;
		}
		
		search.setNext(search.getNext().getNext());
		size--;

	}
	
	public void removeByIndex(int index) {

		if (index < 0)
			return;

		if (index >= size)
			return;

		if (index == 0) {
			
			removeFirst();
			
		} else {

			MyLinkedNode<E> prevFoundItem = getItemByIdx(index - 1);
			if (prevFoundItem == null)
				return;

			removeAfter(prevFoundItem.getItem());
		}

	}
	
	public void removeItem(E item) {

		if (item == null)
			return;
		
		MyLinkedNode<E> search = head;
		MyLinkedNode<E> searchPrev = null;
		
		while (search != null) {

			if (search.getItem().equals(item)) {
				break;
			}
			searchPrev = search;
			search = search.getNext();
		}
		
		if(search == null)
			return;
		
		if(searchPrev == null) {
			removeFirst();
			return;
		}
		
		removeAfter(searchPrev.getItem());

	}
	
	@Override
	public String toString() {

		StringBuilder builder = new StringBuilder();

		MyLinkedNode<E> search = head;
		while (search != null) {
			builder.append(search.toString());
			builder.append("\n");
			search = search.getNext();
		}

		builder.append("total size = " + size);

		return builder.toString();
	}

}
저작자표시 비영리 변경금지 (새창열림)

'Data Structure - Using java' 카테고리의 다른 글

Queue - Created as LinkedList  (0) 2018.05.24
Stack - Created as Array  (0) 2018.05.24
Doubly Linked List  (0) 2018.05.23

+ Recent posts

티스토리툴바