[DataStructure] 스택과 큐

[스택]

스택

• 스택(stack) : 한 쪽에서만 데이터 삽입 및 삭제가 가능한 자료구조

• 푸시(push) : 데이터를 저장하는 연산

• 팝(pop) : 데이터를 빼내는 연산

• 후입선출(LIFO) : 한 쪽에서만 데이터 저장, 관리되기 때문에 나중에 삽입된(후입) 데이터가 먼저 나옴(선출)

• 활용 사례 1) 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때 (매개변수 저장)

    int bar(int y) {
        return y + 2;
    }
  
    int foo(int x) {
        bar(2);
        return x + 1;
    }
  
    foo(1);

  1. 매개변수 x → 1로 초기화

     

  2. bar 함수 호출 → 매개변수 y → 2로 초기화

     

  3. bar 함수 (2 + 2) 반환 → 매개변수 y 삭제

     

  4. foo 함수 (1 + 1) 반환 → 매개변수 x 삭제

     

⇒ 함수 호출 시 매개변수 스택에 저장, 함수 실행 종료 시 스택에 저장된 매개변수 삭제

⇒ 최근 호출된 함수의 매개변수 가장 먼저 활용, 가장 먼저 메모리에서 삭제

• 활용 사례 2) 뒤로가기 기능을 만들고 싶을 때

  • 웹 사이트 방문 시 스택에 URL 푸시
  • 뒤로가기 버튼 클릭 시 저장된 URL 팝

  

---

[큐]

큐

• 큐(queue) : 한 쪽으로 데이터를 삽입하고, 다른 한 쪽으로 데이터를 삭제할 수 있는 자료구조
• 선입선출(FIFO) : 데이터가 저장, 관리되면 먼저 삽입된(선입) 데이터가 먼저 나옴(선출)
• 인큐(enqueue) : 한 쪽 끝에 데이터를 삽입하는 연산
• 디큐(dequeue) : 한 쪽 끝으로 데이터를 삭제하는 연산
• 큐는 임시 저장된 데이터를 차례로 내보내거나 꺼내와야 하는 버퍼 로도 활용

원형 큐

• 원형 큐(circular queue) : 데이터를 삽입하는 쪽과 삭제하는 쪽, 양쪽을 하나로 연결해 원형으로 사용하는 자료구조

양방향 큐 - 덱

• 덱(deque) : 양방향 큐(doubl-ended queue)의 약자, 양쪽으로 데이터 삽입, 삭제할 수 있는 큐

우선순위 큐

• 우선순위 큐(priority queue) : 저장된 요소들이 선입선출로 처리 X, 정해진 우선순위가 높은 순으로 처리되는 큐
• 힙(heap) 자료구조 기반

---

💡 참고 자료

• Stack
• Queue
• Circular Queue
• Deque
• Priority Queue