[자구] 스택과 큐

스택

스택은 한 쪽에서만 데이터의 삽입 및 삭제가 가능한 자료구조이다.

후입선출(LIFO- last in first out) 자료구조이다.

• 푸시: 스택에 저장
• 팝: 데이터를 빼냄

1. 최근에 임시 저장한 데이터를 가장 먼저 활용하고 싶을 때
2. 뒤로가기 기능을 만들고 싶을때 (페이지, 미로 등)

운영체제-메모리 영역에서 매개변수를 저장하기 위해 스택을 사용하는 경우를 얘기했었다.

public class Example {
    public static int bar(int y) { return y + 2; }
    public static int foo(int x) { bar(2); return x + 1; }

    public static void main(String[] args) {
        System.out.println(foo(1));
    }
}

위의 코드로 예시를 들어보자. 매개변수는 처음에 x=1이 저장되고, 그 다음엔 y=2 가 저장될 것이다. bar 함수가 끝나면 y는 사라질 것이고 foo함수가 끝나면 x는 사라질 것이다.

|       |  |       |  |       |  |       |
|       |  | y = 2 |  |       |  |       |
| x = 1 |  | x = 1 |  | x = 1 |  |       |

---

 

큐

큐는 한 쪽으로 데이터를 삽입하고, 다른 한 쪽으로 데이터를 삭제할 수 있는 자료구조

선입선출(FIFO first in first out) 자료구조

• 인큐: 삽입하는 연산
• 디큐: 빼내는 연산

큐는 버퍼와 같이 줄세우는 경우에 사용한다.

1️⃣ 원형 큐

큐의 시작(front)과 끝(rear)을 연결해 원형 구조로 만든 자료구조이다.

• front = 0, rear=0 으로 모두 0에서 시작한다.
• 데이터를 인큐하면 rear 자리에 추가되고, rear은 한칸 이동한다 (rear = 1)
• 데이터를 디큐하면 front자리에 있는 데이터를 빼내고, front는 한칸 이동한다 (front=1)

 

2️⃣ 덱

양방향 큐의 약자로, 양쪽 데이터를 삽입/삭제할 수 있는 큐이다.

 

 

3️⃣ 우선순위 큐

우선순위가 높은 순으로 처리되는 큐

• 인큐될때마다 힙 구조(완전이진트리 기반)를 이용하여 원소가 삽입될때마다 힙 규칙에 따라 우선순위에 맞게 자동으로 위치가 결정된다.