programmingu

큐(Queue)란? 새로운 아이템의 추가와 기존의 아이템의 삭제가 다른 끝점에서 일어나는 linear한 자료구조 rear: insertion이 일어나는 끝 점 front: removal이 일어나는 다른 끝 점 FIFO(First-In First-Out): 먼저 들어온 것이 먼저 나간다. 큐의 구현체는 주로 LinkedList 이다. ⇒ Array-based Queue vs Linked Queue 응용 예 그래프의 넓이 우선 탐색(BFS)에서 사용 CPU threading or multi-tasking scheduling 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킴 printing queue(pool) keystrokes Queue에서의 연산 qu..

스택(Stack)이란? 아이템 추가/삭제 연산이 항상 한 쪽 끝(top)에서만 나타나는 자료 구조이다. LIFO (Last-In-First-Out) : 나중에 들어간 것이 먼저 나온다. 스택의 구현체는 주로 Single Linked List. Array List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(n) Linked List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(1) 응용 예 그래프의 깊이 우선 탐색(DFS)에서 사용 재귀적(Recursion) 함수를 호출 할 때 사용 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함 함수의 콜스택 10진수를 2진수로 바꿀 때 코..