스택

스택은 자료구조에서 매우 기본적인 개념이고, 스택을 포함하는 다른 자료 구조들도 존재하기에 (ex. DFS) 매우 중요한 개념이다. 먼저 스택(stack)이란 쌓아 올린다는 것을 의미한다. 즉 스택이란 책을 쌓는 것처럼 차곡 차곡 쌓아 올린 형태의 자료구조를 의미한다.

스택은 후입선출 (LIFO - Last In First Out)이란 구조적 특징을 갖고있기때문에 자료가 추가 될때 마다 최 상단(top)의 자료의 위에 쌓이게 된다. 또한 삭제시에도 top을 통해서만 가능하며, 스택에 데이터를 삽입하는 연산을 'push' , top을 통한 삭제하는 연산을 'pop'라 한다. (자바 스크립트 내장 메서드 push, pop)과 동일한 기능을 한다.

<장점>

데이터의 삽입과 삭제가 빠르다. (맨 위 원소 접근 O(1))

<단점>

탐색을 하려면 원소를 하나하나 꺼내서 옮겨가면서 해야함.
맨위의 원소만 접근이 가능하다.

큐

큐는 스택과 매우 흡사한 구조를 갖고있지만, 큰 차이점이있다. 이는 바로 스택과는 달리 선입선출(FIFO - First in first out)적인 구조적 특징을 갖고있다는 것인데, 이는 마치 매표소에서 줄을 기다리는 것처럼 먼저 들어온것이 먼저 나가는 형태를 갖고있다.

정해진 곳(top)에서만 데이터의 삽입 및 삭제가 이루어지는 스택과는 달리, 삭제만 수행되는 프론트(front)와 삽입만 수행되는 리어(rear)로 나뉘어져 양 끝에서 작업이 이루어진다. 이때, 큐의 리어(rear)에서 이루어지는 삽입 작업을 enQueue, 프론트(front)에서 이루어지는 삭제 작업을 디큐(dnQueue)라고 한다.

<장점>

데이터의 삽입/삭제가 빠르다. O(1)

<단점>

queue의 중간에 위치한 데이터로의 접근이 어렵다.