Edit

Stack & Queue

Stack & Queue

Stack

  • LIFO(Last In First Out) 방식의 자료구조

  • top : 가장 최근에 들어온 데이터를 가리킴, pop/push 연산이 이루어지는 위치

  • 운영체제의 stack 영역에는 함수의 지역변수, 매개변수가 저장됨

    • stack overflow : 함수가 과도하게 호출되어 운영체제의 스택영역이 가득찬 경우

    • stack underflow : 비어있는 스택에서 원소를 추출할 경우

  • 활용 예시

    • 웹 브라우저 뒤로가기 기능, 실행 취소 기능, 후위 표기법, DFS 구현

  • Array로 구현한 Stack

    import java.util.EmptyStackException;

public class StackArray {

    int top;
    int size;
    int[] stack;

    public StackArray(int size) {
        this.size = size;
        stack = new int[size];
        top = -1;
    }

    public void push(int item) {
        if (top >= size) {
            throw new StackOverflowError();
        }

        stack[top++] = item;
    }

    public int pop() {
        if (top == 0) {
            throw new EmptyStackException();
        }
        int data = stack[top];
        stack[top--] = 0;
        return data;
    }

    public int search(int target) {
        for (int i = 0; i < top; i++) {
            if (stack[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

  • LinkedList로 구현한 Stack

    import java.util.EmptyStackException;

public class StackLinked {
    public static void main(String[] args) {
        StackLinked stack = new StackLinked();
        for (int i = 0; i < 10; i++) {
            stack.push(i);
        }

        stack.display(); // 9-> 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1-> 0->
        System.out.println(stack.pop()); // 9
        stack.display(); // 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1-> 0->
    }

    private Node top;

    public StackLinked() {
        top = null;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public void push(int item) {
        Node node = new Node(item);
        node.next = top; // 연결
        top = node; // top은 Stack의 가장 최근에 들어온 데이터를 가리킨다.
    }

    public int pop() {
        if (top == null) {
            throw new EmptyStackException();
        }

        Node node = top;
        top = top.next;
        return node.item;
    }

    public int search(int target) {
        int id = 0;
        Node temp = top;

        while (temp != null) {
            if (temp.item == target) {
                return id;
            }

            temp = temp.next;
            id++;
        }

        return -1;
    }

    public void display() {
        if (top == null) {
            throw new EmptyStackException();
        }

        Node temp = top;
        while (temp != null) {
            System.out.print(temp.item + "-> ");
            temp = temp.next;
        }
        System.out.println();
    }

    public class Node {
        private int item;
        private Node next;

        public Node(int item) {
            this.item = item;
            next = null;
        }
    }
}

Queue

  • FIFO(First In First Out) 방식의 자료구조

  • front : 가장 첫 번째 원소를 가리킴, 삭제연산(dequeue)이 수행됨

  • rear : 가장 끝 원소를 가리킴, 삽입연산(enqueue)이 수행됨

  • 활용 예시

    • 프로세스 스케쥴링, BFS 구현, LRU(오랫동안 사용하지 않는 데이터를 먼저 삭제) 알고리즘

  • Array로 구현한 Queue

  • LinkedList로 구현한 Queue

  • Stack으로 구현한 Queue

Deque

  • queue 두 개를 좌우로 뒤집어 붙인 자료구조

  • 양 쪽 끝(front, rear)에서 삽입, 삭제 연산을 모두 수행할 수 있음

  • scroll : 입력이 한 쪽에서만 이루어지고, 출력은 양 쪽에서 이루어지는 deque

  • shelf : 입력이 양 쪽에서 이루어지고, 출력이 한 쪽에서만 이루어지는 deque

  • Array로 구현한 Deque

PreviousTreeNextHeap

Last updated

Was this helpful?