Stack & Queue / Array & LinkedList

Stack & Queue

 

Stack

• 책을 쌓는 것처럼 쌓아 올린 형태의 자료구조
• 즉, 후입선출(LIFO, Last In First Out) 방식의 자료구조
• 시간 순서에 따라 데이터를 쌓아올리는 자료구조
• 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 특징

 

Queue

• 사전적 의미로는 “줄을 서서 기다린다.” 라는 의미
• 먼저 들어온게 먼저나가는 자료구조
• 선입선출(FIFO, First In First Out)
• 데이터 삽입, 삭제가 다른 방향에서 이루어짐
• 삭제 연산만 수행되는 곳은 프론트(front)
• 디큐(dnQueue)라고 부름
• 삽입 연산만 수행되는 곳은 리어(rear)
• 인큐(enQueue)라고 부름
• 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 특징

 

Array & Linked List

 

Array

• 연속된 메모리 공간에 존재
• 컴파일 과정에서 메모리가 할당되는 정적 메모리를 할당
• Stack 영역에 메모리 할당

 

Linked List

• 메모리 상에서 떨어져 있는 데이터들이 앞뒤의 데이터를 기억하는 형태로 존재
• 런타임 환경에서 메모리가 할당되는 동적 메모리를 할당
• Heap 영역에 메모리 할당