[자료구조] 덱

덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그렇지만 여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다. 덱의 추상자료형 객체 : n개의 element형의 요소들의 순서 있는 모임 연산 : create() ::= 덱을 생성한다. init(dq) ::= 덱을 초기화한다. is_empty(dq) ::= 덱이 공백 상태인지를 검사한다. is_full(dq) ::= 덱이 포화 상태인지를 검사한다. add_front(dq, e) ::= 덱의 앞에 요소를 추가한다. add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다. delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭..

[자료구조] 스택

1. 스택이란? 책상에 쌓여있는 책, 창고에 쌓여있는 상자등이 스택의 전형적인 예이다. 새로운 상자를 쌓을 때는 상자더미의 맨 윗부분에 놓을 것이고, 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낼 것이다. 만약 중간에서 상자를 꺼내면 전체 상자 더미가 붕괴될 것이다. 따라서 가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다. 이런 입출력 형태를 후입선출(LIFO : Last-In First-Out)이라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 위 그림처럼 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다. 스택에 저장되는 것을 요소(..