본문으로 바로가기
반응형

알고리즘 문제를 풀 때, 기본적인 자료구조를 알아야만 풀 수 있는 경우가 많다.

자료구조는 컴퓨터가 자료를 처리할 때, 이를 효율적으로 관리하고 구조화시키기 위해 구성하고 처리하는 작업을 의미한다.

예를 들어 선입선출의 원리에 따라 먼저 저장된 자료가 먼저 사용되어야 하는 상황에서, Queue를 사용하면 손쉽게 해결할 수 있다.


C나 C++, Java 등의 프로그래밍 언어는 기본적인 자료구조에 대한 라이브러리를 제공한다.

각 언어에서 제공하는 기본적인 라이브러리를 활용하면 복잡한 자료구조 구현도 가능하다.


컴퓨터가 자료를 처리하게 위해 연구된 수많은 자료구조 중 가장 많이 쓰이고 기본이 되는 Stack, Queue, Deque, Heap 네가지 자료구조에 대해 알아보자.


Stack


Stack은 FILO(First In Last Out)을 기본으로 구현된 자료구조이다.

Push 연산으로 자료를 가장 위에 쌓고, Pop 연산으로 가장 마지막에 들어온 자료부터 꺼내 쓴다.


Queue



Queue는 Stack과 반대되는 개념의 자료구조이다.

FIFO(First In First Out)의 원리로 구현되었다.

Push를 통해 쌓은 자료는 가장 먼저 들어온 자료부터 Pop연산으로 꺼내 쓴다.


Deque




Deque는 Queue와 Stack이 혼합된 개념이다.

앞과 뒤 양쪽에서 Push와 Pop연산이 가능하다. 즉, 가장 먼저 넣은 자료부터 꺼낼 수도 있고 가장 나중에 넣은 자료부터 꺼내 쓸 수도 있다.


Heap



자료구조에 들어있는 데이터들의 최대값 혹은 최소값을 빠르게 찾아내기 위해 고안되었다.

완전이진트리 형식으로 구현되어 있다.

Top 연산으로 현재 상태의 최대값(혹은 최소값)을 확인할 수 있다.

Pop 연산으로 최대값(최소값)을 꺼내 쓰고, Push 연산으로 새로운 값을 추가한다.

새로 값이 추가되면 정렬 순서에 맞게 자료가 저장된다.

반응형

 Other Contents