스택 (1) - 개요

1. Stack

스택은 자료를 차곡차곡 쌓는 자료구조이다. 한쪽 끝에서만 삽입과 삭제가 가능하며, 가장 먼저 들어간 데이터가 가장 나중에 출력되어 LIFO(Last In, First Out) 혹은 FILO (First In, Last Out)이라고 말한다.

 

[그림] Stack (스택)

2. Top

스택의 가장 높히 있는 원소의 인덱스를 Top이라고 한다. 그래서 스택에 데이터를 넣을 때는 Top변수를 1 늘리고, 데이터를 뺄 때는 Top 변수를 1 줄인다. 이 Top은 사실상 스택의 Size로 사용할 수 있다. 

 

3. Push & Pop  & Peek

스택에서는 데이터를 넣을 때, 아래로 밀어넣는다는 의미에서 Push, 데이터를 꺼낼때 튀어나온다는 의미에서 Pop이라고 한다. Insert, Delete와 같은 표현을 써도 상관은 없지만, 일반적으로 Push와 Pop이라는 용어를 쓴다. 또한 가장 데이터를 꺼내지 않고 확인만 할 때는 Peek(훔쳐보다)라는 함수명을 사용한다.

 

4. ArrayStack 구현

Stack은 ArrayList와 LinkedList 등을 이용해서 구현할 수 있다. 정확히 말하자면 그들을 이용하여 구현하지만, ArrayList와 LinkedList는 어디에서든 삽입 삭제가 가능하기 때문에 사실상 그들의 기능을 일부러 제한하는 것과 같다.

 

import java.util.Arrays;

/**
 * @author : Hyunwoong
 * @when : 4/28/2020 2:54 PM
 * @homepage : https://github.com/gusdnd852
 */
public class ArrayStack {
    private int[] array;
    private int capacity;
    private int top = -1;

    public ArrayStack(int capacity) {
        this.array = new int[capacity];
        this.capacity = capacity;
    }

    public ArrayStack() {
        this.array = new int[10];
        this.capacity = 10;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    private void grow(float rate) {
        int newCapacity = (int) (capacity * rate);
        int[] newArray = new int[newCapacity];

        for (int i = 0; i < capacity; i++) {
            newArray[i] = array[i];
        }

        capacity = newCapacity;
        array = newArray;
    }

    public void push(int data) {
        if (isFull())
            grow(2.0f);

        top++;
        array[top] = data;
    }

    public int pop() {
        if (isEmpty())
            throw new NullPointerException();

        int data = array[top];
        array[top] = 0; // 값 초기화화
       top--;
        return data;
    }

    public int peek() {
        if (isEmpty())
            throw new NullPointerException();

        return array[top];
    }

    public int size() {
        return top + 1;
    }

    @Override public String toString() {
        return Arrays.toString(array);
    }
}

 

5. ListStack 구현

ListStack을 구현할때 주의할 점이 있는데, push와 pop을 head쪽에서 해야한다는 것이다. 만약 tail쪽에서 push와 pop을 하게 되면, push하기 위해 tail까지 loop를 타고 움직여야한다 (Singlely List의 경우) 

/**
 * @author : Hyunwoong
 * @when : 4/28/2020 2:54 PM
 * @homepage : https://github.com/gusdnd852
 */
public class ListStack {
    private Node head;
    private int top = 0;

    public void push(int data) {
        if (head == null) {
            head = new Node();
            head.data = data;
        } else {
            Node node = new Node();
            node.data = data;
            node.next = head;
            head = node;
        }
        top++;
    }

    public int pop() {
        int data = head.data;
        head = head.next;
        top--;
        return data;
    }

    public int peek() {
        return head.data;
    }

    public boolean isEmpty(){
        return top == 0;
    }

    @Override public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("]");
        for (Node node = head; node != null; node = node.next) {
            builder.append(node.data);
            if (node.next != null) {
                builder.append(" ,");
            }
        }
        builder.append("[");
        builder.reverse();
        return builder.toString();
    }

    private static class Node {
        private int data;
        private Node next;
    }

    private int size() {
        return top;
    }
}

 

6. Reference

자료구조