스택(Stack), 큐(Queue)

1. 스택(Stack)

스택의 구조

스택은 후입 선출(Last In First Out -가장 마지막에 삽입된 자료가 가정 먼저 삭제된다는 의미) 개념이다. 즉, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.
예를들어 바닥이 막힌 상자에 물건을 쌓는다고 생각하면 쉽다. 나중에 넣은 물건이 제일 위에 있으므로 먼저 꺼내게 된다.

• 정해진 방향으로만 쌓을 수 있다.
• 저장소의 끝 부분(가장 최근에 들어온 자료). 즉, 가장 먼저 빠져나갈 데어터의 위치를 top이라고 한다.
  top으로 정한 곳을 통해서만 접근가능하며, 새로 사입되는 데이터는 top이 가리키는 맨 위에 쌓이고, 자료를 삭제할 때도 top의 위치의 데이터를 삭제한다.
• 삽입은 push, 삭제는 pop 한다고 한다.
• 스택의 시간 복잡도
     삽입(Insertion ) : O(1)
     삭제(Deletion) : O(1)
     검색(Search) : O(n)
  맨위에 데이터를 삽입, 삭제하기 때문에 시간복잡도는 O(1)
  히자만 특점 데이터 검색 시 맨 밑에 있는 자료를 찾으려면 모든 자료를 검색해봐야 하므로 O(n)

2. 큐(Queue)

큐의 구조

큐는 선입선출(First In First Out -가장 먼저 들어오는 데이터가 가장 먼저 나가게 된다는 의미) 개념이다.  즉, 한쪽 끝에서는 삽입 작업이 이루어지고, 다른 끝에서는 삭제 작업이 이루어지는 형태의 자료구조를 말한다.
예를들어 식당에서 음식을 주문했을 때, 먼저 시킨 손님부터 음식이 나간다고 생각하면 쉽다.

• 삽입이 이루어지는 곳을 리어(rear), 삭제가 이루어지는 곳을(front)라고 한다.
• 큐 맨 뒤에 데이터 삽입 동작을 인큐(Enqueue), 큐 맨 앞의 데이터 삭제 동작을 디큐(Dequeue)라고 한다.
• 큐의 시간 복잡도
     삽입(Insertion) : O(1)
     삭제(Deletion) : O(1)
     검색(Search) : O(n)

3. 문제 유형

https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

위 프로그래머스 문제는 스택/큐 관련 Level 2 문제이다.

* 구현

문제 풀이

위 문제의 경우 큐 개념을 사용하여 구현하였다.

★ 스택/큐는 가장 기본적인 자료구조이다. 따라서 개념을 확실히 하고, 따로 스택의 push, pop 큐의 enqueue, dequeue 함수를 직접 구현해보며 학습하는 것을 추천!!