[자료구조&알고리즘] 2-2 스택과 큐

## 이 문서는 성균관대학교 성재필 교수님의 강의인 인공지능을 위한 알고리즘과 자료구조를 정리한 내용입니다.

강의 목표

1.Discuss key data structures and algorithems essential for solving problems with computers

2.Programming skills -Translate your idea into languages that computers can understand

3.Computational thinking -Problem formulation(abstraction) -solution expression(automation) -solution execution and evaluation(analysis)

Stack

A collection of elements that are inserted and removed according to the last-in-first-out order

스택은 선형자료구조의 하나로써, LIFO라고 부르는 특성을 가지고 있는 자료구조이다.LIFO라고 하면 Last-in-First-out의 약자인데, 말 그대로 last-in 마지막으로 들어간 element가 first-out 처음으로 나온다는 이야기이다.스택에서는 insertion이나 remove를 할때, 스택의 최상단, 탑이라고 불리는 최상단에서만 이루어지는 특징이 있다.

스택이라는 자료구조에서 단어들이 있는데 정리하면 다음과 같다,

TOP = 상단 Push = 어떤 아이템을 탑 위치에 추가하겠다라는 뜻이다. Pop = 스택의 최상단에서 하나의 아이템을 빼내겠다 라는 뜻이다.

그럼 스택에서 어떤 문제를 풀 수 있나라고 한다면, 프로그래밍을 할 때, 괄호 같은 걸 체크해주는데 이때 괄호를 하이라이팅을 해주는 경우 스택을 이용해서 수행할 수 있다. 괄호매칭문제를 해결하기 위해 스택을 사용할 수 있는데 예를 들어보자.

만약 이 문자가 닫는 괄호라고 하면, 여는 문자를 스택에 푸쉬한다. 그리고 보고 있는 문자가 닫는 괄호라고 하면, 스택에서 하나의 여는 괄호를 꺼내서 둘을 매칭시켜 준다. 모든 문자열을 다 봤을 때, 스택이 비어있다고 하면 주어진 문자열은 괄호 차원에서 밸런스가 되어 있는 것이며, 그렇지 않으면 밸런스가 되어 있찌 않다고 이야기 할 수 있다.

Queue

스택은 큐와 다르게 first-in-first-out 구조이다. 그러니까 먼저 들어간 데이터가 제일 먼저 나오는 구조이다. 일반적으로 먼저 줄선사람이 먼저 서비스를 받는 형태라고 생각할 수 있다.

A collection of elements that are inserted and removed according to the first-in-first-out(FIFO) order

용어를 정리하자면 Front(head)는 dequeue 즉, deletion이 발생하는 곳이며, rear(back)dms insertion이 발생하는 곳이다. 그래서 enqueue라고 하면 큐에 아이템을 insertion하는 것이며, 그곳의 위치는 rear가 되는 것이다.

하지만 위 그림과 같이 인큐 디큐는 마지막에 나오는 것처럼 front가 5를 가리키고 있고, rear는 어레이의 끝을 가르키고 있기 때문에, 이 상황에서는 분명히 공간이 2개 있음에도 불구하고 더 이상의 데이터를 rear에 추가할 수 없는 상황히 발생한다,

따라서 circular queue를 많이 사용하며, circular queue는 어느 시점이 되면 rear가 돌아서 다시 0인덱스로 돌아오는 형태로 이루어져있다.