Te JAVA (2) - 자료구조 구현 (Stack)

1. LinkedList 구현 (ListNode, add(), remove(), contains())
2. Stack 구현 (int 배열, push(), pop())
3. Stack 구현 (ListNode, push(), pop())
4. Queue구현 (int배열, ListNode 이용)

 

2주차 실습의 1 내용은 이전 블로그에 존재한다.

https://abbiddo.tistory.com/95

Te JAVA (2) - 자료구조 구현 (LinkedList)

 

---

 

2. Stack 구현 (Array)

Stack 정의

• 한 쪽 끝에서만 데이터를 넣고 뺄 수 있는  LIFO 형식의 자료구조다.
• 스택에 데이터를 추가하면 가장 끝에 추가된다.
• 가장 최근에 스택에 추가한 항목이 가장 먼저 제거된다.

 

기본 정의

• 스택의 크기를 나타내는  size, 맨 끝 위치를 가리키는 top, 데이터들을 저장하는 int 배열 value을 선언한다.
• 생성자에서는 크기를 입력받아 배열의 크기와, 배열, top을 초기화한다.

public class StackArray {

    private int size;   // 스택의 크기
    private int top;    // 스택의 top 지점
    private int[] value;    // 값을 저장하는 배열

    // 생성자
    // top과 배열 초기화

    public StackArray(int size){
        top = -1;
        this.size = size;
        value = new int[size];
    }

 

push 메소드

    // 값 삽입
    void push(int data){
        if (top == size - 1){ return; }
        value[++top] = data;
    }

 

pop 메소드

    // top 반환과 삭제
    int pop(){
        if (top < 0){ return Integer.MIN_VALUE; }
        return value[top--];
    }

 

print 메소드

    void print(){
        for (int i = 0; i <= top; i++){
            System.out.print(value[i] + " - ");
        }
    }

 

---

 

2 - 1. Stack Test

push Test

    @Test
    void push() {

        StackArray stackArray = new StackArray(4);

        stackArray.push(10);
        stackArray.push(20);
        stackArray.push(30);
        stackArray.push(40);

        stackArray.push(5); // 아무것도 실행하지 않고 return

        stackArray.print();
        // 10 - 20 - 30 - 40 -

    }

 

pop Test

    @Test
    void pop() {

        StackArray stackArray = new StackArray(4);

        stackArray.push(10);
        stackArray.push(20);
        stackArray.push(30);
        stackArray.push(40);

        stackArray.pop();
        stackArray.pop();

        stackArray.print();
        // 10 - 20 -

    }

 

---

 

3. Stack 구현 (ListNode)

기본 정의

• 링크드 리스트의 처음을 나타내는 head 노드를 저장할 변수를 선언한다.

public class StackListNode {
    private ListNode head;

 

push 메소드

    void push(int data){

        ListNode add = new ListNode(data);

        if (head == null){
            head = add;
            return;
        }

        ListNode cur = head;
        while (cur.getNext() != null){
            cur = cur.getNext();
        }

        cur.setNext(add);
    }

 

pop 메소드

    int pop(){

        if (head == null) { return Integer.MIN_VALUE; }
        if (head.getNext() == null) {
            head = null;
            return Integer.MIN_VALUE;
        }

        ListNode cur = head;
        while (cur.getNext().getNext() != null){
            cur = cur.getNext();
        }

        int data = cur.getNext().getValue();
        cur.setNext(null);

        return data;
    }

 

print 메소드

    void print(){
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.getValue() + " - ");
            cur = cur.getNext();
        }
    }

 

---

 

3 - 1. Stack Test

push Test

    @Test
    void push() {
        StackListNode stack = new StackListNode();

        stack.push(10);
        stack.push(20);

        stack.print();
        // 10 - 20 -

    }

 

pop Test

    @Test
    void pop() {
        StackListNode stack = new StackListNode();

        stack.push(10);
        stack.push(20);

        assertEquals(stack.pop(), 20);

        stack.print();
        // 10 -
        
    }

 

---

 

2주차 실습의 4 내용은 이후 블로그에 존재한다.

https://abbiddo.tistory.com/97

Te JAVA (2) - 자료구조 구현 (Queue)