deque

[자료구조] 스택(Stack)/큐(Queue)/덱(Deque)

1. 스택(Stack) ▶ 스택이란, 한쪽에서만 자료를 넣고 뺄 수 있는 후입선출 LIFO(Last In First Out)형식의 선형 자료구조이다. 스택의 기본 개념은 영어 단어의 뜻과 같이 '쌓는다'는 뜻이다. 스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. 예를 들어, 박스 쌓기에 비유할 수 있다. 박스를 아래에서 위로 차곡차곡 쌓으면 아래에 있는 박스를 치우기 위해서는 맨 위의 박스부터 치워야 한다. 아래부터 1->2->3 순서로 쌓여있는 상자를 오른쪽으로 옮긴다고 가정해보자. 먼저 가장 위에 있는 3번 상자를 오른쪽으로 옮기고, 그 후에는 2번 상자를 옮기고, 다음에는 1번 상자를 옮길 것이다. 즉, 마지막에 입력된 상자가 첫 번..