본문 바로가기

자료구조5

자료구조 선형 큐 (Linear Queue) 자바로 구현 1. 개요 큐는 대표적인 자료구조중 하나로, 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출, FIFO (First In First Out) 형태의 자료구조다. 활용방법으로는 프린터 출력 (가장 먼저 대기열에 오른 프린트를 먼저 실행) 대기열, 대기표 (먼저 신청한 사람이 먼저 업무를 봄) 순서가 보장된 처리를 제공 사용자가 몰린 서버에 유 기능으로는 offer() : 데이터 삽입 poll() : 데이터 빼기 peek() : 데이터를 뽑지 않고, 큐 안에서 가장 먼저 들어온 데이터 확인 2. 구현 package queue; public interface IQueue { void offer(T data); T poll(); T peek(); int size(); void clear(); boolean.. 2022. 2. 16.
자료구조 스택 (Stack) 자바로 구현 1. 개요 스택은 대표적인 자료구조중 하나로, 가장 마지막에 들어간 데이터가 가장 먼저 나오는 후입선출, LIFO (Last In First Out) 형식의 자료구조다. 활용방법으로는 웹 브라우저 뒤로가기 : 가장 마지막에 열린 페이지부터 나온다. 실행 취소 (undo) : 가장 마지막에 실행된 것부터 실행을 취소한다. (ctrl + z) 함수 호출 : 프로그램에서 함수를 호출할 때, 함수가 끝나면 원래 코드로 돌아가야 한다. 이런 함수의 정보를 저장하는 메모리를 콜 스택이라고 한다. 기능으로는 push() : 데이터를 넣는 메소드 pop() : 데이터를 빼는 메소드 top(), peek() : 데이터를 빼지 않고, 가장 위에 있는 데이터를 확인하는 메소드 자세히 설명하면, push는 데이터를 하나씩 담.. 2022. 2. 15.
자료구조 이중 연결 리스트(Double Linked List) 자바로 구현 1. 개요 연결 리스트는 "노드" 에 객체를 담고, 포인터를 통해 연결되어있다. 단일 연결 리스트는 next 포인터로 앞으로 밖에 갈 수 없지만, 이중 연결 리스트는 prev, next 포인터 가 있어서 뒤로도 갈 수 있다. 단일 연결 리스트로 가장 마지막에 데이터를 넣으려면 처음부터 포인터를 타고 가야 하므로, 데이터가 100개면 100번, 1억개면 1억번 이동을 해야 하는데 이중 연결 리스트는 마지막에 tail이라는 더미 노드를 만들어놓고, 뒤로 갈 수 있기에, tail 에서 prev 포인터로 이동하면 데이터가 100만개가 있던, 1억개가 있던 1번의 동작으로 그 위치까지 이동할 수 있다. 또한, 삽입이나 삭제를 할 때도, head와 tail중, 가까운 곳에서 탐색을 시작하면, 데이터가 100만개면 .. 2022. 2. 14.
자료구조 배열 리스트 (ArrayList) 자바로 구현 1. 개요 자료구조인 배열 리스트를 자바로 구현하고, 메소드별 시간복잡도를 확인해본다. 우선 배열 리스트의 장단점을, 연결 리스트와 비교하며 확인해보자 장점 배열로 구현되어 있으므로, 인덱스 번호로 접근이 가능하고, 탐색시간이 아주 짧다. (연결 리스트의 경우, 원하는 데이터를 찾을 때까지, 포인터를 타고 이동하면서 찾아야 한다.) 단점 생성할 때, 크기를 정하고 생성해야 하는데, 크기가 작으면 데이터가 꽉 찼을 때, 다시 생성해줘야 하고, 크기가 크면 남는 공간만큼 메모리의 낭비가 생긴다 효율적으로 관리하기 위해, 연속적으로 데이터를 넣어줘야 하는데, 데이터의 추가와 삭제가 있을 경우, 데이터를 밀고 당겨야 하는 작업이 필요하고, 시간이 오래 걸린다. (배열의 크기가 50이고, 40개의 데이터가 차있다.. 2022. 2. 13.

티스토리툴바