[JAVA] 스택 / 큐

728x90

Stack

자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다.

1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조
2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함
3. 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
4. 그래프의 깊이 우선 탐색(DFS)에서 사용
5. 재귀적(Recursion) 함수를 호출 할 때 사용

메서드

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
size() : 스택의 크기를 반환한다.
contains(int value) : stack의 값을 search하는 함수
clear() : 스택에 있는 모든 값을 제거한다.

구현

1. Array Stack 배열

2. Linked연결 리스트

스택(Stack) 구현

import java.util.*;

public class test {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();

        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop();
        s.push(1);
        s.push(4);
        s.pop();

        // 스택의 최상단 원소부터 출력
        while (!s.empty()){
            System.out.print(s.peek() + " ");	//peek() 메서드 사용
            s.pop();
        }
    }
}

실행결과

1 3 2 5

큐(Queue) 구현

import java.util.*;

public class test {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll();
        q.offer(1);
        q.offer(4);
        q.poll();

        // 먼저 들어온 원소부터 추출
        while (!q.isEmpty()){
            System.out.print(q.poll() + " ");
        }
    }
}