StackとQueueの実装📌

16351 ワード

📌 Stack


🔥 using array
import java.util.NoSuchElementException;

public class StackImpl {
    static final int STACK_SIZE = 3;
    int size=STACK_SIZE;
    // 다음에 들어갈 값을 가르킴
    int index=0;
    int[] arr = new int[STACK_SIZE];

    void push(int val){
        if(isStackOverSize()){
            extendStackSize();
        }
        arr[index++]=val;
    }

    int pop(){
       if (index==0){
           throw new NoSuchElementException();
       }
       // index가 다음에 들어갈 값을 가르키기 때문에 미리 빼주어야 한다.
       return arr[--index];
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i=0;i<index;i++){
            sb.append(arr[i]);
            if(i!=index-1){
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    boolean isStackOverSize(){
        return index >= size;
    }
    void extendStackSize(){
        int[] temp = arr;
        size = index*STACK_SIZE;
        arr = new int[size];
        for(int i=0;i<index;i++){
            arr[i] = temp[i];
        }
    }
}

📌 Queue


🔥 using node
import java.util.NoSuchElementException;

public class QueueImpl {
    class Node{
        int val;
        Node next;
        Node(int val){
            this.val=val;
        }
    }

    Node first;
    Node last;

    void offer(int val){
        Node node = new Node(val);
        if(last!=null){
            last.next=node;
        }
        last = node;
        // 첫번째 값을 넣었을 때 first = null 임 그래서 first = last 시켜줘야 한다
        if(first==null){
            first=last;
        }
    }

    int poll(){
        if (first==null){
            throw new NoSuchElementException();
        }
        int returnValue = first.val;
        first= first.next;
        // last에 대한 설정값도 해주어야 한다.
        if(first==null){
            last=null;
        }
        return returnValue;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node node = this.first;
        while(node!=null){
            sb.append(node.val);
            if(node.next!=null){
                sb.append(",");
            }
            node=node.next;
        }
        sb.append("]");
        return sb.toString();
    }
}