4주차 과제: Stack

 

스택 (Stack) 에 대하여

사전적 의미로 "쌓다", "더미" 라는 뜻이다.

바구니에 물건을 하나씩 쌓아 둔다 로 생각하면 편하다.

https://dev.to/rinsama77/data-structure-stack-and-queue-4ecd

 

위의 이미지를 보면 처음 들어간 물건이 나중에 나온다. 후입선출로 스택은 LIFO 구조이다.

예를 들어, 인터넷 뒤로가기 앞으로가기가 있다.

​

---

​

 

Stack을 구현하세요.

int 배열을 사용해서 정수를 저장하는 Stack을 구현

public class Stack {

    private int size = 5; // 스택의 용량
    private int[] valeus; // 스택에 저장된 값들
    private int topIndex; // 스택의 포인터

    //stack 생성자
    public Stack() {
        this.topIndex = 0;
        valeus = new int[size];
    }

    @Override
    public String toString() {
        return "Stack{" +
                "size=" + size +
                ", valeus=" + Arrays.toString(valeus) +
                ", topIndex=" + topIndex +
                '}';
    }
}

 

void push(int data)를 구현하세요.

    public void push(int data) {

        // 스택이 다 찼을 경우
        if (size - 1 == topIndex) {
            size += 5;
            valeus = Arrays.copyOf(valeus, size);
            valeus[topIndex++] = data;
            return;
        }

        valeus[topIndex++] = data;

    }

 

int pop()을 구현하세요.

    public void push(int data) {

        // 스택이 다 찼을 경우
        if (size - 1 == topIndex) {
            size += 5;
            valeus = Arrays.copyOf(valeus, size);
            valeus[topIndex++] = data;
            return;
        }

        valeus[topIndex++] = data;

    }

​

​

데모

Stack stack = new Stack();

stack.push(1);
System.out.println("push 1 ->" +stack);
stack.push(2);
System.out.println("push 2 ->" +stack);
stack.push(3);
System.out.println("push 3 ->" +stack);
stack.push(4);
System.out.println("push 4 ->" +stack);
stack.push(4);
System.out.println("push 4 ->" +stack);
stack.push(4);
System.out.println("push 4 ->" +stack);
stack.push(5);
System.out.println("push 5 ->" +stack);



stack.pop();
System.out.println("pop -> " +  stack);
stack.pop();
System.out.println("pop -> " +  stack);
stack.pop();
System.out.println("pop -> " +  stack);
stack.pop();
System.out.println("pop -> " +  stack);
// 출력

push 1 ->Stack{size=5, valeus=[1, 0, 0, 0, 0], topIndex=1}
push 2 ->Stack{size=5, valeus=[1, 2, 0, 0, 0], topIndex=2}
push 3 ->Stack{size=5, valeus=[1, 2, 3, 0, 0], topIndex=3}
push 4 ->Stack{size=5, valeus=[1, 2, 3, 4, 0], topIndex=4}
push 4 ->Stack{size=10, valeus=[1, 2, 3, 4, 4, 0, 0, 0, 0, 0], topIndex=5}
push 4 ->Stack{size=10, valeus=[1, 2, 3, 4, 4, 4, 0, 0, 0, 0], topIndex=6}
push 5 ->Stack{size=10, valeus=[1, 2, 3, 4, 4, 4, 5, 0, 0, 0], topIndex=7}
pop -> Stack{size=10, valeus=[1, 2, 3, 4, 4, 4, 0, 0, 0, 0], topIndex=6}
pop -> Stack{size=10, valeus=[1, 2, 3, 4, 4, 0, 0, 0, 0, 0], topIndex=5}
pop -> Stack{size=5, valeus=[1, 2, 3, 4, 0], topIndex=4}
pop -> Stack{size=5, valeus=[1, 2, 3, 0, 0], topIndex=3}

​

 

---

 

​

과제 4. 앞서 만든 ListNode를 사용해서 Stack을 구현하세요.

 

ListNode head를 가지고 있는 ListNodeStack 클래스를 구현하세요.

public class LinkedListStack {
    ListNode head;

    public LinkedListStack() {
    }

    public LinkedListStack(ListNode head) {
        this.head = head;
    }


    public String toString() {
        StringBuilder str = new StringBuilder();
        ListNode tempNode = head;

        //헤더가 없을 경우 그냥 리턴
        if (tempNode == null) {
            return null;
        }

        while (true) {
            str.append(tempNode.getData()).append(" ");

            if (tempNode.getPoint() == null) {
                break;
            }

            tempNode = tempNode.getPoint();
        }
        return str.toString();
    }


}

 

void push(int data)를 구현하세요.

    public void push(int data) {
        ListNode pushNode = new ListNode(data);
        this.pushNode(pushNode);
    }


    public void pushNode(ListNode pushNode) {
        ListNode tempNode = head;

        if (head == null) {
            head = pushNode;
            return;
        }

        // 가장 마지막 노드로 이동
        while (tempNode.getPoint() != null) {
            tempNode = tempNode.getPoint();
        }

        //A(tempNode) - > B(addNode) -> null 형태
        tempNode.updateNextPoint(pushNode);
        pushNode.updateNextPoint(null);

    }

 

int pop()을 구현하세요.

    public int pop() {
        ListNode popNode = this.popNode();

        if (popNode == null) {
            throw new ArrayIndexOutOfBoundsException();
        }

        return popNode.getData();
    }


    public ListNode popNode() {
        ListNode tempNode = head;
        ListNode beforeNode = null;

        if (head == null) {
            return null;

        }

        // 가장 마지막 노드로 이동
        while (tempNode.getPoint() != null) {
            beforeNode = tempNode;
            tempNode = tempNode.getPoint();
        }

        if (beforeNode != null) {
            beforeNode.updateNextPoint(null);
        }

        if (tempNode.equals(head)) {
            head = null;
        }


        return tempNode;
    }

 

데모

public class LinkedListStackDemo {
    public static void main(String[] args) {
        LinkedListStack list = new LinkedListStack();

        list.push(1);
        System.out.println(" push 1 -> " + list);
        list.push(2);
        System.out.println(" push 2 -> " + list);
        list.push(3);
        System.out.println(" push 3 -> " + list);
        list.push(4);
        System.out.println(" push 4 -> " + list);
        list.push(5);
        System.out.println(" push 5 -> " + list);
        list.push(6);
        System.out.println(" push 6 -> " + list);


        list.pop();
        System.out.println(" pop -> " + list);
        list.pop();
        System.out.println(" pop -> " + list);
        list.pop();
        System.out.println(" pop -> " + list);
        list.pop();
        System.out.println(" pop -> " + list);
        list.pop();
        System.out.println(" pop -> " + list);

    }
}

 

// 출력결과
 push 1 -> 1 
 push 2 -> 1 2 
 push 3 -> 1 2 3 
 push 4 -> 1 2 3 4 
 push 5 -> 1 2 3 4 5 
 push 6 -> 1 2 3 4 5 6 
 pop -> 1 2 3 4 5 
 pop -> 1 2 3 4 
 pop -> 1 2 3 
 pop -> 1 2 
 pop -> 1