Skip to content

Files

Latest commit

425e52e ยท Feb 28, 2022

History

History
503 lines (383 loc) ยท 10.2 KB

StackAndQueue.md

File metadata and controls

503 lines (383 loc) ยท 10.2 KB

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();
        }
    }
}