선형 자료구조 (배열, 스택, 큐)

출처 https://osy0907.tistory.com/84

 

 

자료구조 (Data Structure) 란

- 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법으로 선형과 비선형으로 구분할 수 있다

 

선형 자료구조 (Linear Data Structure)

 - 데이터 요소가 순차적으로 나열되어 있으며 첫번째부터 마지막 요소까지 백트래킹 없이 순회할 수 있다

 

---

1. 배열(Arrays)

 

1-1) Array

- 가장 기본적인 배열로 ‘고정된 크기’를 가지며 동일한 데이터 타입만 저장할 수 있습니다.

int[] arr = new int[5];
for (int i = 0; i < arr.length; i++) {
    arr[i] = i + 1;
}

메서드	설명
clone()	배열 복사
length	배열 길이
sort()	배열 정렬
fill()	배열의 모든 요소를 특정 값으로 설정
binarySearch()	이진 검색을 수행하여 배열에서 지정된 값의 인덱스를 반환
equals()	배열의 객체와 같은지 확인
toString()	배열의 문자열 반환

 

1 - 2 ) ArrayList

 

-  가변 된 크기’를 가지며 동적으로 크기를 조정할 수 있는 배열로 객체만 저장할 수 있습니다.

ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
list.add("cherry");

메서드	설명
add()	요소 추가
addAll()	모든 요소 추가
remove()	요소 제거
removeAll()	지정된 컬렉션의 모든 요소를 ArrayList에서 제거
contains()	ArrayList가 지정된 객체를 포함하는지 여부를 확인
indexOf()	ArrayList에서 지정된 객체의 인덱스를 반환
size()	ArrayList의 요소 수를 반환

 
 

< Array와 ArrayList의 차이점 >

	Array	ArrayList
크기	초기화 시 표기 (크기 고정)	초기화 시 미표기 (크기 가변적)
속도	ArrayList 보다 빠르다	추가, 삭제할 때 메모리 재할당하기 때문에 느림
다차원	가능	불가능

 

---

 3. Stack

• 스택의 가장 큰 특징은 후입선출(LIFO: Last In First Out)
• 가장 최근에 들어온 데이터가 가장 먼저 나간다
• 그래프의 깊이 우선 탐색 (DFS: Depth-First Search)에서 많이 사용
  
  

import java.util.Stack; //스택 가져오기
Stack<자료타입> stack = new Stack<>(); //스택 선언.

 

 

 예) 1 - 3 - 5 순서대로 push 하고 pop 하면 최근에 들어온 5가 나간다

 

 [스택 연산]

 

init()	스택을 초기화
create()	스택을 생성
is_empty(s)	스택이 비어있는지 검사
is_full(s)	스택이 가득 찼는지 검사
push(e)	스택의 맨 위에 요소 e 추가
pop(s)	스택의 맨 위 요소를 삭제
peek(s)	스택의 맨 위 요소를 삭제하지 않고 반환
top()	스택 맨 위에 있는 데이터 값 반환
push()	스택에 데이터 삽입
pop()	스택에서 데이터 삭제하여 반환
isempty()	스택에 원소가 없으면 'True', 있으면 'False' 값 반환
isfull()	스택에 원소가 없으면 'False', 있으면 'True' 값 반환

---

4. Queue

 

• 선입선출(FIFO - First In First Out) 
• 먼저 추가한 데이터를 먼저 반환/삭제하는 형식의 자료구조 (ex 줄서기)
• bfs에서 많이 사용
• 데크(Deque), 우선순위 큐(Priority Queue) 등으로 변형
  
  

  [큐 연산]

 

init()	큐 초기화
create()	큐 생성
isEmpty()	큐 비어있는지 검사
isFull()	큐 가득 찼는지 검사
enqueue(e)	큐 맨 뒤에 e 추가
dequeue()	큐 맨 앞의 값 삭제
peek()	큐 맨 앞의 값 출력 (큐가 비어있는 경우 null 반환)
element()	큐 맨 앞의 값 출력 (큐가 비어 있는 경우 에러 발생)
offer(e)	큐의 맨 뒤에 e 추가 (큐가 비어있는 경우 null 반환)
add(e)	큐의 맨 뒤에 e 추가(큐가 비어 있는 경우 에러 발생)
poll()	큐의 맨 앞의 값 제거하고 출력 (큐가 비어있는 경우 null 반환)
remove()	큐의 맨 앞의 값 제거하고 출력 (큐가 비어 있는 경우 에러 발생)

---

 

Point 1) 기본형 int vs 배열 int[]

 

Stack<> / Queue<> 에서 <>안에 들어갈 자료타입은 "실제 값”이 아닌 저장된 메모리의 “주소 값”을 가지는 참조 자료형이 들어간다.

예를 들어 int는 기본형이라 들어갈 수없고 대신에 기본형 데이터를 감싸 객체로 표현해주는 클래스 Wrapper class인 Integer로 변경해 사용한다.

여기서 헷갈리지 말아야 할 것은 int와 int[]은 다르다는 것이다

int[]는 기본 타입 int의 배열이지만, Java에서는 배열이 객체로 취급되어 참조 타입으로 간주된다.

고로 적용이 가능하다.

 

Point 1) 좌표 사용 시 int[] or Point 사용

 

→ int[] 배열을 사용

Queue<int[]> q = new LinkedList<>();
q.add(new int[] {x,y});

→ Point 사용

import java.awt.Point;

Queue<Point> que = new LinkedList<>();
que.add(new Point(x,y));

 

 

-  Point 클래스는 좌표 상의 위치를 나타내는데 사용

-  x와 y좌표값을 저장하기 위한 멤버변수를 갖는다

 

Field Summary
Modifier and Type	Field and Description	설명
int	x	x좌표
int	y	y좌표

메소드	설명
void setLocation(int x, int y)	x, y좌표의 위치값을 설정
Point getLocation()	현재 위치의 x, y좌표값을 반환

 

 

*** 계속해서 업데이트 중입니다 ***