Algorithms-[Que & Stack]

이번에는 자주 쓰이는 큐와 스택에 대해서 설명할 것이다. 단순 리스트등으로 구현하면 시간초과나 메모리초과가 나오는 문제들을 자료구조를 큐와 스택으로 설정해서 간단하게 풀리는 문제들이 많다. 

Stack

스택의 가장 큰 특징은 후입선출(LIFO, Last-In-First-Out) (나중에 들어간것이 먼저 나감)이다.

데이터를 추가할 때도 top에 쌓이고, 삭제할 때도 top에 있는 것이 사라진다. 즉 한방향 구조이다. top에 데이터를 삽입하는 것을 push라고 하고, top에 있는 데이터를 삭제하는 것을 pop이라고 한다. 스택은 아래와 같은 문제에서 많이 사용된다. 전부 후입선출이라는 특징때문에 아래와 같이 마지막에 대한 데이터를 다루는 문제에서 유용하다. 특히 괄호쌍 문제는 매우 많이 나온다.

- 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.

- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다

- 괄호 쌍 검사

Que

que는 stack과 다르게 가장 큰 특징이 선입선출(FIFO,First in first out)(먼저 들어온것이 먼저 나감)이다.

큐는 top에서 데이터의 삽입과 삭제가 모두 일어나는 스택과는 달리 rear이라는 한쪽 끝에서는 삽입이 이루어지고 , front에서는 데이터의 삭제가 이뤄진다. rear에서 삽입하는것을 enqueue라고 하고, front에서 삭제하는 과정을 dequeue라고 칭한다. 큐는 선입선출이므로 순서가 중요한 문제들에서 사용된다.-

-우선순위가 같은 작업 예약

-너비 우선 탐색(BFS, Breadth-First Search) 구현

-(Cache) 구현