반응형
1. 순수 배열로 직접 구현
배열에서 인덱스를 활용해 topIndex의 값을 바꿔주는것이 포인트이다.
POP을 호출해도 배열에서 값을 실제로 삭제하지는 않고 인덱스만을 활용한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | package Stack; public class ArrayStackMain { public static void main(String[] args) { ArrayStack st = new ArrayStack(); st.push("0");//삽입 st.push("1"); st.push("2"); System.out.println("= MyStack1 peek="); System.out.println(st.peek());//마지막 값 리턴 System.out.println("= MyStack1 pop="); while(!st.empty()) { System.out.println(st.pop());//삭제후 리턴 } } } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | package Stack; import java.util.EmptyStackException; public class ArrayStack { int topIndex = -1;//현재 탑의 인덱스를 -1 초기화//데이터가 없는 상태 private Object[] StackArr = new Object[100];//배열의 크기는 100으로 일단 제한 public Object push(Object data) { StackArr[++topIndex] = data; return data; } public Object pop() { Object data = peek();// Stack에 저장된 마지막 요소를 읽어온다. topIndex--;//탑 인덱스의 연산을 통해 삭제를 해주는것과 같은 결과를 낸다 //어레이 리스트 기반으로 하면 삭제를 위해 앞뒤땡겨주는 연산까지하게된다. return data; } public Object peek() { if (topIndex == -1) {//현재 데이터가 없다면 throw new EmptyStackException(); } return StackArr[topIndex];//현재 탑의 값을 리턴 } public boolean empty() { return topIndex == -1;//-1이라면 데이터가 없음 } } | cs |
2. ArrayList api를 활용한 직접 구현
- 배열 기반의 ArrayList를 활용한다.
- 주요 메소드 호출시 전체 리스트 size를 증감한다.
- POP호출시 값을 실제로 삭제한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | package Stack; import java.util.ArrayList; import java.util.EmptyStackException; public class ArrayListStack extends ArrayList{//어레이 리스트 기반 public Object push(Object data) { add(data); return data; } public Object pop() { Object data = peek();// Stack에 저장된 마지막 요소를 읽어온다. remove(size() - 1);//마지막 요소를 삭제한다 return data; } public Object peek() { int len = size();//전체 데이터 갯수 if (len == 0) {//전체 데이터 갯수가 없다면 throw new EmptyStackException(); //EmptyStackException을 발생 } return get(len - 1);//마지막 리스트 엘리먼트 리턴 } public boolean empty() { return size() == 0;//갯수가 0개라면 투르 } } | cs |
3. LinkedList로 직접 구현 ( node의 연결을 활용)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | package Stack; import java.util.EmptyStackException; public class LinkedListStack { private Node head; private int size = 0; public class Node{ private Object data; private Node next; public Node(Object input) { this.data = input; this.next = null; } } public void push(Object input){ Node newNode = new Node(input); newNode.next = head; head = newNode; size++; } public Object peek() { int len = size(); if (len == 0) { throw new EmptyStackException(); } return head.data; } public Object pop(){ if(head != null) { Node temp = head; head = temp.next; Object returnData = temp.data; temp = null; size--; return returnData; }else return (Object)"Stack에 값이 없습니다"; } public boolean empty() { return size() == 0; } public int size(){ return size; } } | cs |
4) 자바 라이브러리 이용
- Stack 클래스 제공 ( vector의 상속, 배열 기반 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | package Stack; import java.util.Stack; public class StackApi { public static void main(String[] args) { Stack<String> st = new Stack();//벡터를 구현한 스택 st.push("0"); st.push("1"); st.push("2"); System.out.println("= MyStack0 peek="); System.out.println(st.peek());//마지막 값 리턴 System.out.println("= MyStack0 pop="); while(!st.empty()) { System.out.println(st.pop()); } } } | cs |
- LinkedList 클래스 제공 ( Node 객체 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | package Stack; import java.util.LinkedList; public class LinkedListStackApi { public static void main(String[] args) {//기존의 더블링크드 리스트 api를 이용한 stack LinkedList<String> st = new LinkedList(); st.addFirst("1"); st.addFirst("2"); st.addFirst("3"); System.out.println("= LinkedList getFirst="); System.out.println(st.getFirst()); System.out.println("= LinkedList removeFirst="); while(!(st.size()==0)) { System.out.println(st.removeFirst()); } st.push("1"); st.push("2"); st.push("3"); System.out.println("= LinkedList peek="); System.out.println(st.peek());//마지막 값 리턴 System.out.println("= LinkedList pop="); while(!(st.isEmpty())) {//size()==0 System.out.println(st.pop()); } } } | cs |
반응형
'Basic > 자료구조,알고리즘' 카테고리의 다른 글
Queue의 다양한 구현 (0) | 2018.12.08 |
---|---|
Queue - 큐의 개념과 특성들 (0) | 2018.12.08 |
Stack 스택의 개념과 특성들 (0) | 2018.12.06 |
원형 연결리스트(CircularLinkedList)직접 구현 (0) | 2018.12.06 |
Doubly linked list(이중 연결 리스트) 직접 구현 (0) | 2018.11.29 |