StackAndQueue.md

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

public class QueueArray {
    int front;
    int rear;
    int[] queue;

    public QueueArray(int size) {
        queue = new int[size];
        front = rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return rear == queue.length - 1;
    }

    public void enqueue(int item) {
        if (isFull()) {
            System.out.println("queue is full");
            return;
        }

        queue[rear++] = item;
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("queue is empty");
            return -1;
        }
        int data = queue[front];
        // 모든 원소를 한칸 앞으로 이동시킨다.
        for (int i = 0; i < rear - 1; i++) {
            queue[i] = queue[i + 1];
        }
        if (rear < queue.length) {
            queue[rear] = 0;
        }
        rear--;

        return data;
    }

    public void display() {
        if (isFull()) {
            System.out.println("queue is empty");
            return;
        }

        for (int i = front; i < rear; i++) {
            System.out.print(queue[i] + " <- ");
        }
        System.out.println();
    }
}

LinkedList로 구현한 Queue

public class QueueLinked {

    public static void main(String[] args) {
        QueueLinked queue = new QueueLinked();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
        }
        queue.display(); // 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -
        for (int i = 0; i < 5; i++) {
            queue.dequeue();
        }
        queue.display(); // 5 - 6 - 7 - 8 - 9 -
    }

    Node front, rear;

    public QueueLinked() {
        front = rear = null;
    }

    public boolean isEmpty() {
        return front == null && rear == null;
    }

    public void enqueue(int item) {
        Node node = new Node(item);
        if (isEmpty()) {
            front = rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("queue is empty");
            return -1;
        }

        int data = front.item;
        front = front.next;

        if (front == null) {
            rear = null;
        }

        return data;
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("queue is empty");
            return;
        }

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

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

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

Stack으로 구현한 Queue

import java.util.Stack;

public class QueueWithStack {

    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();

    public void enqueue(int item) {
        while (!s1.empty()) {
            s2.push(s1.pop());
        }

        s1.push(item);

        while (!s2.empty()) {
            s1.push(s2.pop());
        }
    }

    public int dequeue() {
        if (s1.empty()){
            System.out.println("queue is empty");
            return -1;
        }

        return s1.pop();
    }
}

Deque

• queue 두 개를 좌우로 뒤집어 붙인 자료구조
• 양 쪽 끝(front, rear)에서 삽입, 삭제 연산을 모두 수행할 수 있음
• scroll : 입력이 한 쪽에서만 이루어지고, 출력은 양 쪽에서 이루어지는 deque
• shelf : 입력이 양 쪽에서 이루어지고, 출력이 한 쪽에서만 이루어지는 deque

Array로 구현한 Deque

public class DequeWithArray {

    public static void main(String[] args) {
        DequeWithArray deque = new DequeWithArray(20);
        for (int i = 1; i <= 5; i++) {
            deque.insertFront(i);
        }
        deque.display(); // 5 4 3 2 1
        for (int i = 1; i <= 5; i++) {
            deque.insertRear(-i);
        }
        deque.display(); // 5 4 3 2 1 -1 -2 -3 -4 -5
    }

    private int arr[];
    private int front;
    private int rear;
    private int size;

    public DequeWithArray(int size) {
        arr = new int[100];
        front = -1;
        rear = 0;
        this.size = size;
    }

    public boolean isFull() {
        return ((front == 0 && rear == size - 1) || front == rear + 1);
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public void insertFront(int item) {
        if (isFull()) {
            System.out.println("overflow");
            return;
        }

        if (front == -1) {
            front = rear = 0;
        } else if (front == 0) {
            front = size - 1;
        } else {
            front--;
        }

        arr[front] = item;
    }

    public void insertRear(int item) {
        if (isFull()) {
            System.out.println("overflow");
            return;
        }

        if (front == -1) {
            front = rear = 0;
        } else if (rear == size - 1) {
            rear = 0;
        } else {
            rear++;
        }

        arr[rear] = item;
    }

    public int deleteFront() {
        if (isEmpty()) {
            System.out.println("queue underflow");
            return -1;
        }
        int data = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else if (front == size - 1) {
            front = 0;
        } else {
            front++;
        }

        return data;
    }

    public int deleteRear() {
        if (isEmpty()) {
            System.out.println("queue underflow");
            return -1;
        }

        int data = arr[rear];
        if (front == -1) {
            front = rear = -1;
        } else if (rear == 0) {
            rear = size - 1;
        } else {
            rear--;
        }
        return data;
    }

    public void display() {
        if (isEmpty()) {
            System.out.println("queue is empty");
            return;
        }

        if (front < rear) {
            for (int i = front; i <= rear; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        } else {
            for (int i = front; i < size; i++) {
                System.out.print(arr[i] + " ");
            }
            for (int i = 0; i <= rear; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }
}