#1 Stack (스택)

Writer: Steven, Lee

Date: 12/31, Monday

Purpose: Learning #1 Stack

Level: Easy to understand

* 한국어는 아랫쪽에 있습니다. *

 * Caution *

 Every time you have to know what kind of data structure technique or algorithm you gonna use for some problem. Especially, It's more important than knowledge.   

 * What is Stack? *

Meaning of stack is "heap" or "pile" like a pile of books. Here is a good example to understand. 

              

there are four books (stack) which are accumulated like that. the only way to access one of the books is top of stack and bottom of the stack is not able to be accessed. Because if you wanna try to get the bottom book of the stack, it is blocked by the book on the book you are trying to get. there are basically two functions Push and Pop. Push means you gonna add a book on the top of the stack. Pop means you gonna pop a book from the top of the stack. we call this form LIFO(Last In First Out) 

* Uses with Stack*

there are a lot of uses with Stack. For example, users on the internet used to go back where users were. In this situation, we use stack technique for this. and also recursive need to use this if you want to backtrack values. or you can convert a string to reversed string :)

* Embodiment of Stack. *

Actually, there are two types of making stack code. Linked list and Array are the normal types of the stack. But I would like to show you array one. There are a lot of functions in stacks that I made. you need to know how to use it by yourself. It's quite easy :)

public class StackOfIntsLab {
    private int[] elements;
    private int size;
    private static int time;
    private static final int DEFAULT_CAPACITY = 2;
 
    /** Construct a stack with the default capacity */
    public StackOfIntsLab() {
        this(DEFAULT_CAPACITY);
    }
    public StackOfIntsLab(int capacity){
        elements = new int[capacity];
    }
 
    /**
     * Push a new int into the top of the stack
     * Double the stack capacity when size > capacity().
     * */
    public void push(int item) {
        if(size == 0 && capacity() == 0){
            int[] temp = new int[1];
            elements = temp;
        }
        else if (size >= capacity()) {
            int[] temp = new int[capacity() * 2];
            System.arraycopy(elements, 0, temp, 0, size);
            elements = temp;
        }
        elements[size++] = item;
    }
 
    /**
     * Return and remove the top element from the stack
     * Reduce the stack capacity in half when
     * (size * 4 <= capacity())
     */
    public int pop(){
        if (size * 4 <= capacity()) {
            int[] temp = new int[capacity() / 2];
            System.arraycopy(elements, 0, temp, 0, size);
            elements = temp;
        }
        return elements[--size];
    }
 
    /** Return the top element from the stack */
    public int peek() {
        return elements[size-1];
    }
 
    /** Test whether the stack is empty */
    public boolean empty() {
        return size == 0;
    }
 
    /** Return the number of elements in the stack */
    public int size() {
        return size;
    }
 
    public int capacity() {
        return elements.length;
    }
 
    /** Make the stack empty */
    public void clear() {
        size = 0;
        elements = new int[DEFAULT_CAPACITY];
    }
 
    /** make it fit tight */
    public void trimToSize() {
        // resize elements to capacity
        if (capacity() > size) {
            int[] temp = new int[size];
            System.arraycopy(elements, 0, temp, 0, size);
            elements = temp;
        }
    }
 
    /*
     * Returns a string repr. of stack
     * For example: "[1, 2, 4]"
     */
    @Override
    public String toString(){
        String delimiter = ", ";
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++)
            sb.append(elements[i] + delimiter);
        int i = sb.lastIndexOf(delimiter);   // remove the last ", " if any.
        if (i > 0) sb.delete(i, i+2);
 
        sb.append("]");
        return sb.toString();
    }
 
    @Override
    public boolean equals(Object obj){
        if(this == obj)    return true;
        if (getClass() != obj.getClass()) return false;
 
        StackOfIntsLab other = (StackOfIntsLab) obj;
        if(!Arrays.equals(elements, other.elements)) return false;
        if(size != other.size) return false;
 
        return true;
    }
 
 
 
 
 

* 한국어 *

* 주의 *

모든 순간마다 당신은 어떤 데이터 구조나 알고리즘을 어떤 문제에 사용해야 할지 알아야 합니다. 특히, 이것은 단순히 지식보다 더 중요한 것입니다.

 * What is Stack? *

 * 스택이란? *

스택의 의미는 "더미"라고 할 수 있습니다. 예를 들어 책을 쌓아올린 것처럼 말이죠. 여기에 이해하기 쉬운 좋은 예시가 있습니다.

              

 네 개의 책으로 쌓아올리는 것(스택)이 있습니다. 이 책 중에서 하나를 접근할 수 있는 방법은 오직 스택의 윗 부분입니다. 그리고 스택의 맨 아래는 접근할 수가 없습니다. 왜냐하면 만약 당신이 아래에 있는 책을 얻으려고 하면 바로 접근하기 위한 곳 윗 부분에서 막혀있기 때문입니다.  기본적으로 push와 pop이라는 기능들이 있는데 push는 스택의 맨 윗 부분에 책을 더하는 것입니다. pop은 스택의 맨 윗 부분을 가져온다는 것입니다. 우리들 이러한 것들을 LIFO(Last in First OUT)이라고 부릅니다.

* 스택의 사용들 *

스택을 사용한 것들이 많은데 예를 들어보면 인터넷에서 유저가 있었던 부분으로 돌아갈 때 스택을 사용합니다. 또한 backtracking이라는 기법을 할 때도 사용합니다. 혹은 문자열을 거꾸로 만들기 위해서도 사용합니다.

* 스택의 구현 *

사실 스택을 구현할 때는 두 가지 종류로 구현할 수 있습니다. 연결 리스트와 배열입니다. 하지만 저는 이번에 배열을 소개하고 싶습니다. 지금 제가 만든 코드에서 다양한 기능들이 들어가 있는데 스스로 이해하실 수 있어야 합니다. 이 부분은 꽤 쉬울 듯 하네요.

public class StackOfIntsLab {
    private int[] elements;
    private int size;
    private static int time;
    private static final int DEFAULT_CAPACITY = 2;
 
    /** Construct a stack with the default capacity */
    public StackOfIntsLab() {
        this(DEFAULT_CAPACITY);
    }
    public StackOfIntsLab(int capacity){
        elements = new int[capacity];
    }
 
    /**
     * Push a new int into the top of the stack
     * Double the stack capacity when size > capacity().
     * */
    public void push(int item) {
        if(size == 0 && capacity() == 0){
            int[] temp = new int[1];
            elements = temp;
        }
        else if (size >= capacity()) {
            int[] temp = new int[capacity() * 2];
            System.arraycopy(elements, 0, temp, 0, size);
            elements = temp;
        }
        elements[size++] = item;
    }
 
    /**
     * Return and remove the top element from the stack
     * Reduce the stack capacity in half when
     * (size * 4 <= capacity())
     */
    public int pop(){
        if (size * 4 <= capacity()) {
            int[] temp = new int[capacity() / 2];
            System.arraycopy(elements, 0, temp, 0, size);
            elements = temp;
        }
        return elements[--size];
    }
 
    /** Return the top element from the stack */
    public int peek() {
        return elements[size-1];
    }
 
    /** Test whether the stack is empty */
    public boolean empty() {
        return size == 0;
    }
 
    /** Return the number of elements in the stack */
    public int size() {
        return size;
    }
 
    public int capacity() {
        return elements.length;
    }
 
    /** Make the stack empty */
    public void clear() {
        size = 0;
        elements = new int[DEFAULT_CAPACITY];
    }
 
    /** make it fit tight */
    public void trimToSize() {
        // resize elements to capacity
        if (capacity() > size) {
            int[] temp = new int[size];
            System.arraycopy(elements, 0, temp, 0, size);
            elements = temp;
        }
    }
 
    /*
     * Returns a string repr. of stack
     * For example: "[1, 2, 4]"
     */
    @Override
    public String toString(){
        String delimiter = ", ";
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++)
            sb.append(elements[i] + delimiter);
        int i = sb.lastIndexOf(delimiter);   // remove the last ", " if any.
        if (i > 0) sb.delete(i, i+2);
 
        sb.append("]");
        return sb.toString();
    }
 
    @Override
    public boolean equals(Object obj){
        if(this == obj)    return true;
        if (getClass() != obj.getClass()) return false;
 
        StackOfIntsLab other = (StackOfIntsLab) obj;
        if(!Arrays.equals(elements, other.elements)) return false;
        if(size != other.size) return false;
 
        return true;
    }