Stack Queue

Java

chbong 2022. 8. 13. 00:31

스택 : 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식이며, 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조이다.

stack 클래스는 List 컬렉션 클래스의 Vector 클래스를 상속받아, 전형적인 스택 메모리 구조의 클래스를 제공

스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO - Last In First Out)의 시멘틱을 따르는 자료 구조이며 가장 나중에 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조이다.

Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메소드를 5개만 상속받아 사용합니다.

boolean empty()	해당 스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
E peek()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환함.
E pop()	해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거함.
E push(E item)	해당 스택의 제일 상단에 전달된 요소를 삽입함.
int search(Object o)	해당 스택에서 전달된 객체가 존재하는 위치의 인덱스를 반환함. 이때 인덱스는 제일 상단에 있는(제일 마지막으로 저장된) 요소의 위치부터 0이 아닌 1부터 시작함.

peek - 읽기

pop - 추출

push - 삽입

Queue : 줄을 지어 순서대로 처리되는 자료구조로 First In First Out의 형태를 가진다. 말 그대로 먼저 들어온 데이터가 먼저 나가는 구조를 말한다.

Queue 인터페이스는 큐 메모리 구조를 표현하기 위해, 다음과 같은 Collection 인터페이스 메소드만을 상속받아 사용

메소드설명

boolean add(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴.
E element()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
boolean offer(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함.
E peek()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함. 만약 큐가 비어있으면 null을 반환함.
E poll()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함. 만약 큐가 비어있으면 null을 반환함.
E remove()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.

배열을 순차적으로 연결된 공간에 데이터를 나열하는 구조

링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

장점

- 데이터 공간을 미리 할당하지 않아도 된다.

단점

- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않다

- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림

- 중간 데이터 삭제 시, 앞 뒤 데이터의 연결을 재구성해야하는 부가적인 작업 필요