[자료구조] 스택과 큐

스택

• 스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조로 만들어져 있으며, 데이터를 넣는 경우 Push, 꺼내는 경우 Pop을 이용한다. 마지막에 들어간 데이터가 가장 먼저 나온다는 LIFO(Last In First Out)의 특징을 갖고 있다.
• 스택은 웹 브라우저의 뒤로가기, 뒤로가기 단축키 (ctrl + z), 후위 표기법, 재귀 알고리즘 등에서 사용된다.

스택 구현

• 스택은 배열과 리스트로 구현할 수 있다. 배열의 경우 간단하지만, 고정길이를 벗어나는 경우를 대비하기 어렵다. 따라서 스택의 경우 리스트로 구현하여 필요한 만큼 메모리를 사용하고, 가변길이에 대응하는 예제를 진행해보자.

package ds;

public class StackByList {

  private Node head;

  public void push(Object data) {
    Node node = new Node();
    node.data = data;
    if (!isEmpty()) {
      // 새로운 노드는 head가 가리키는 노드의 참조값을 저장
      node.next = head;
    }
    // head는 새로운 노드의 참조값을 저장
    head = node;
  }

  public Object pop() {
    if(isEmpty()) throw new RuntimeException("stack is empty");

    // 삭제할 노드는 head가 가리키는 노드
    Node removeNode = head;
    Object tempData = removeNode.data;
    head = removeNode.next;
    return tempData;
  }

  public Object peek() {
    if (isEmpty()) return null;
    return head.data;
  }


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

  static class Node {
    Node next;
    Object data;
  }
}

큐

• 큐는 먼저 넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장되며, 작업 대기열로 많이 사용된다. 예를 들어 프린터 출력, 메시지 큐, OS 스케줄링, BFS 알고리즘 등에서 사용된다.
• 큐에는 배열로 구현하는 원형 큐, 리스트로 구현하는 큐가 있다. 리스트로 구현하는 큐에선 큐의 맨 앞 노드를 가리키는 front 노드와 맨 마지막 노드를 가리키는 rear 노드가 있다.

큐 구현

public class QueueByList {
  private Node front;
  private Node rear;

  public void add(Object data) {
    Node newNode = new Node();
    newNode.data = data;
    if (isEmpty()) {
      // 최초 노드 삽입 시 front와 rear 는 새로운 노드를 바라본다.
      front = rear = newNode;
    } else {
      rear.next = newNode;
      rear = newNode;
    }
  }

  public Object poll() {
    if (isEmpty()) {
      return null;
    }
    Node removeNode = front;
    Object tempData = removeNode.data;
    front = removeNode.next;

    if (removeNode == rear) {
      rear = null;
    }
    return tempData;
  }

  public Object peek() {
    if(isEmpty()) return null;
    return front.data;
  }
  public boolean isEmpty() {
    return front == null;
  }


  static class Node {
    Node next;
    Object data;
  }
}

---

REFERENCES

https://www.codelatte.io/topics