알고리즘 Stack, Queue, Deque, Heap

정적인 메모리 : 컴파일할 때 메모리를 할당받고 시작한다 ex) 기본형 자료형

동적인 메모리 : 실행하는 런 타임에 메모리를 할당받는다 ex) 참조형 자료형

 

스택 Stack

LIFO 후입선출의 구조

백트래킹, 인터넷 사용기록 보관 등이 스택을 사용하는 LIFO 구조를 갖고 있다

한쪽(TOP)에서만 데이터를 넣고 꺼낼 수 있다.

 

스택오버플로우: 정해진 크기의 스택에 계속해서 PUSH 하다 스택의 크기를 초과하여 더 이상 데이터를 추가할 수 없게 된 것으로 흔히 스택을 사용하는 재귀 함수 호출 시 많이 경험한다. 컴퓨터의 사칙 연산 계산에서 후위 표기법을 사용할 때도 스택을 활용한다.

 

PUSH : 스택의 TOP에 데이터 추가

POP : 스택의 TOP의 데이터를 읽고 제거

PEEK : 스택의 TOP의 데이터를 읽음

 

 

 

큐 Queue

FIFO 선입선출의 구조

순서를 보장하는 처리가 필요할 때 쓸 수 있다. 선착순, 서비스 처리 등의 큐를 사용하는 FIFO구조를 갖고 있다.

한 방향으로만 데이터를 넣고, 꺼낼 수 있다

 

큐 중에서도 우선순위를 고려하여 순서를 조작할 수 있는 것이 존재하기도 한다.

 

Rear에서 Enqueue : 큐에 데이터 추가

Front에서 Dequeue : 큐에서 데이터를 읽고 제거

PEEK : 큐의 가장 먼저 들어온 데이터를 읽고 삭제하지 않는다.

 

 

덱 Deque

덱은 Double Ended Queue로, 양쪽 방향으로 넣고 꺼낼 수 있다.

스택과 큐의 특성을 모두 지니고 있기 때문에 스택과 큐 모두로 활용할 수 있다

덱운 양방향 연결 리스트로 구현할 수 있다.

 

 

힙 Heap

힙의 기억 장소는 지시자(pointer) 변수를 통해 동적으로 할당받고 돌려준다. 이는 연결 목록이나 나무, 그래프 등의 동적인 자료 구조를 만드는 데 꼭 필요한 것이다.

프로그램들이 요구하는 블록의 크기나 요구/횟수의 순서가 일정한 규칙이 없다

프로그램에 할당되었다 회수되는 작용이 반복되는 영역이기도 하다 

 

 

트리 Tree

어떤 하나의 집합(레코드나 디렉터리 등)으로부터 하위 레벨로 가지가 나오는 집합 관계를 갖는 계층 구조

부분적으로도 루트를 형성하는 경우는 없다

정보 처리 분야에서는 이 같은 트리구조를 가진 개념이 많이 있다

대표적으로 순서 트리나 2진 트리 등이 있다