Stack (스택)

Stack

www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm

• LIFO(Last In First Out) 구조를 가진 자료구조다.
• 말그대로 나중에 들어온 데이터가 먼저 나간다.
• 먼저 들어온 데이터가 가장 아래에 위치한다.
  • 아래있는 데이터를 꺼내려면 그 위에 있는 데이터를 모두 꺼내야 한다.
• 스택에 데이터를 넣는 행위를 push 이라고 한다.
• 스택에서 데이터를 꺼내는 행위를 pop 이라고 한다.

두가지 자료구조를 활용해서 스택을 구현했다.

• 하나는 배열, 하나는 ListNode(LinkedList를 실습하기 위해 만든 클래스)이다.
• 배열로 구현했을 땐, 크기를 미리 정해야하기 때문에 가변적이지 못하다.
• ListNode로 구현했을 땐 스택 크기 제한이 없다.

구현1 (int 배열 사용)

테스트코드 포함 전체 코드 링크

package com.example.week4;

public class Stack {
    int[] datas;
    int pointer = -1; // empty

    public Stack(int size) {
        datas = new int[size];
    }

    public void push(int data) {
        pointer++;
        datas[pointer] = data;
    }

    public int pop() {
        int data = datas[pointer];
        pointer--;
        return data;
    }
}

구현2 (ListNode 사용)

테스트코드 포함 전체 코드

package com.example.week4;

public class StackWithListNode {

    private ListNode head = new ListNode();
    private int pointer = -1;

    public void push(int data) {
        pointer++;
        ListNode.add(head, new ListNode(data), pointer);
    }

    public int pop() {
        ListNode removed = ListNode.remove(head, pointer);
        pointer--;

        return removed.data;

    }
}