스택(Stack) 그리고 큐(Queue)

2 minute read

Mention : 쌓는가🏗, 줄을 서는가🎢?

스택 (Stack)

스택은 위의 사진 처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
- top의 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있다.
- 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
- 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
- top을 통해 삽입하는 연산을 ‘push’ 삭제하는 연산을 ‘pop’ 이라고 한다.
- peek 은 top 위치에 현재 있는 데이터를 단순 확인하는 연산
따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 지님
이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조이라고 한다.
비어있는 스택에서 원소를 추출하려고 할 때 stack underflow라고 하며, 스택이 넘치는 경우 stack overflow라고 한다.
깊이 우선 탐색 (DFS), 백트래킹 종류의 코딩 테스트에 효과적

Queue 란 게임에서 흔히 볼 수 있는데, ‘큐를 돌린다’ 즉 대기한다, 줄을 서서 기다리는 것을 의미한다.
- 따라서, 선입선출 (FIFO, First in first out) 방식의 자료구조를 말한다.

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어 진다.
삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 수행되는 곳을 리어(rear) 로 정하여 각각의 연산작업만 수행된다.
이때, 큐의 프론트에서 이루어지는 삭제연산을 디큐(dnQueue), 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue) 라고 부른다.
- 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
- 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성
- 접근방법은 가장 첫 원소와 끝 원소로만 가능
- 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제
즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

스택이란 쌓다라는 의미로, 데이터를 차곡차곡 쌓아 올린 자료구조를 말합니다. 데이터가 순서대로 쌓이고 가장 마지막에 쌓인 자료가 가장 먼저 삭제되는 구조로 LIFO(Last In First Out) 입니다. 스택에서 삽입 연산은 push(), 삭제 연산은 pop()입니다. 큐는 대기하는것(줄서기)를 의미하며, 스택과 다르게 먼저 들어온 것이 먼저 나가는 선입선출 구조를 가지고 있습니다. 이를 FIFO(First In First Out) 라고 합니다.

Reference 📚