[자료구조] 스택

Stack

  - 후입선출 (Last-In-First-Out - LIFO)

  - ex) 인터넷 브라우저 뒤로 가기, Ctrl + z

Stack 예제

1. 우선 List와 같이 Stack 구현에 사용할 IStack 인터페이스를 생성

package stack;

public interface IStack<T> {
    void push(T data);
    T pop();
    T peek();
    int size();
}

 

2. IStack을 구현할 MyStack 클래스를 생성 후 메서드를 생성

package stack;

public class MyStack<T> implements IStack<T> {

    @Override
    public void push(T data) {
        
    }

    @Override
    public T pop() {
        return null;
    }

    @Override
    public T peek() {
        return null;
    }

    @Override
    public int size() {
        return 0;
    }
}

 

3. Stack도 List와 같이 Node 기반으로 구현 하므로 Node를 생성

// node 기반이기 때문에 node class 선언
    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

 

4. 멤버변수 설정 및 생성자 생성

private int size;
    private Node head;

    public MyStack() {
        this.size = size();
        this.head = new Node(null);
    }

 

5. Stack에 데이터를 넣어주는 push함수 예제

@Override
    public void push(T data) {
        Node node = new Node(data, this.head.next);
        this.head.next = node;
        this.size++;
    }

 

6. Stack에서 데이터를 가져오는 pop함수 예제

@Override
    public T pop() {
        if(this.isEmpty()) {
            return  null;
        }
        
        Node curr = this.head.next;
        this.head.next = curr.next;
        curr.next = null;
        this.size--;
        return curr.data;
    }

 

7. Stack의 데이터를 확인만 진행하는 peek함수 예제

@Override
    public T peek() {
        if(this.isEmpty()) {
            return  null;
        }
        return this.head.next.data;
    }

    private boolean isEmpty() {
        return this.head.next == null;
    }

 

8. Stack의 size를 확인하는 size함수 예제

@Override
    public int size() {
        return this.size;
    }

 

전체 코드

package stack;

public class MyStack<T> implements IStack<T> {

    private int size;
    private Node head;

    public MyStack() {
        this.size = size();
        this.head = new Node(null);
    }

    @Override
    public void push(T data) {
        Node node = new Node(data, this.head.next);
        this.head.next = node;
        this.size++;
    }

    @Override
    public T pop() {
        if(this.isEmpty()) {
            return  null;
        }

        Node curr = this.head.next;
        this.head.next = curr.next;
        curr.next = null;
        this.size--;
        return curr.data;
    }

    @Override
    public T peek() {
        if(this.isEmpty()) {
            return  null;
        }
        return this.head.next.data;
    }

    private boolean isEmpty() {
        return this.head.next == null;
    }

    @Override
    public int size() {
        return this.size;
    }

    // node 기반이기 때문에 node class 선언
    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}