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

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