스택(Stack)

후입선출(Last In First Out - LIFO) 특성을 가지는 자료구조

(이미지 출처 : https://velog.io/@tiiranocode/자료-구조-스택stack-큐queue)

연산

• push : 스택에 item을 추가
• pop : 스택에서 item을 제거. 이때 제거되는 item은 넣은 순서의 역순으로 가장 위의 요소가 제거됨
• peek : stack의 top 요소 반환
• isEmpty: stack이 비어있으면 true, 그렇지 않으면 false를 반환

구현

스택은 후입선출(LIFO)의 개념으로, 배열과 연결리스트로 구현할 수 있다.

배열 예제

public class StackAsArray {
    static final int MAX = 1000;
    int top;
    int arrStack[] = new int[MAX];

    StackAsArray() {
        top = -1;
    }

    boolean isEmpty() {
        return (top < 0);
    }

    boolean push(int data) {
        System.out.println(data + " pushed to stack");

        if (top > MAX - 1) {
            System.out.println("Stack Overflow");
            return false;
        } else {
            arrStack[++top] = data;
            return true;
        }
    }

    int pop() {
        if (top < 0) {
            System.out.println("Stack is empty");
            return -1;
        } else {
            int x = arrStack[top--];
            return x;
        }
    }

    int peek() {
        return arrStack[top];
	  }
}

연결 리스트 예제

public class StackAsLinkedList {

    StackNode root;

    static class StackNode {
        int data;
        StackNode next;

        StackNode(int data) { this.data = data; }
    }

    public boolean isEmpty() {
        if (root == null) {
            return true;
        }
        return false;
    }

    public void push(int data) {
        StackNode newNode = new StackNode(data);
        newNode.next = root;
        root = newNode;
        System.out.println(data + " pushed to stack");
    }

    public int pop() {
        if (root == null) {
            System.out.println("Stack is empty");
        }

        int popped = Integer.MIN_VALUE;
        popped = root.data;
        root = root.next;
        return popped;
    }

    public int peek() {
        if (root == null) {
            System.out.println("Stack is empty");
        }

        return root.data;
    }

    public static void main(String[] args) {
        StackAsLinkedList sll = new StackAsLinkedList();

        sll.push(10);
        sll.push(20);
        sll.push(30);

        System.out.println(sll.pop() + " popped from stack");

        System.out.println("Top element is " + sll.peek());
    }
}

참고

• https://namu.wiki/w/스택(자료구조)
• https://www.geeksforgeeks.org/stack-data-structure-introduction-program/