코드 저장소

공부에는 끝이 없다!

자료구조 3

(JAVA)백준 문제 풀이 - 스택, 큐, 덱 단계 - 24511번 queuestack (실버 3)

이번 문제는 덱을 이용하여 스택과 큐가 혼합된 자료구조에 배열이 입력되었을때 출력 값을 구하는 문제이다. 문제를 이해하는데 꽤 애를 먹었는데 각각의 자료구조에 한 개의 원소가 들어있다라는 문구를 제대로 이해하지 못해서 처음에는 입력받은 자료구조의 배열을 통과하면서 스택과 큐로 변형되는 문제인줄 알았다가 예시를 한참 보고서야 제대로 이해할 수 있었다. 문제부터 이해하자! 예시를 잘 살펴보면서 문제를 이해해보자. 첫번째 예시에서 자료구조는 [큐,스택,스택,큐]의 구조로 이루어진다. 그리고 통과할 배열은 [1,2,3,4]로 이루어져있다. 나는 처음에 초기 상태를 보고 첫번째에는 2라는 입력값이 큐로 한번 통과하여 [2,3,4,2]로 나오고 그다음 출력된 1을 스택으로 통과시켜 [2,3,4,2]로 나오게 하여 ..

덱(Deque)

덱(Deque)이란? 덱(Deque)이란 양끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 큐와 스택의 성질을 모두 가지고 있는 자료구조이다. 양쪽에서 모두 삽입과 삭제가 가능하기 때문에 First,Last로 앞에서 처리할지 뒤에서 처리할지를 결정 할 수 있으며 보다 자유롭게 사용이 가능한 큐라고 이해해도 무방하겠다. 중복 원소를 허용하며 크기 제한이 없는 것도 특징이다. 덱의 특징 덱은 기본적으로 큐이기 때문에, 큐처럼 구현체를 만들어 사용하여야 한다. java.util.Deque 인터페이스를 구현한 클래스를 사용하면 되며 일반적으로는 ArrayDeque와 LinkedList를 사용한다. 덱의 주요 메서드는 다음과 같다. addFirst(E e) / offerFirst(E e): 덱의 맨 앞에 원소..

JAVA/자료구조 2023.10.03

스택과 큐

스택(Stack)이란? 스택(stack)이란 책을 쌓는 것처럼 쌓아 올려진 형태의 자료구조를 말한다. 가령, A,B,C라는 책을 상자에 넣고 뺀다고 생각해보자. 넣을 때는 A,B,C 순으로 들어가겠지만, 뺄때는 C,B,A순으로 빼내어야 한다. 이런 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 한다. 스택의 특징 앞서 설명했듯, 스택은 먼저 들어간 것이 가장 나중에 나오는 형태이다. 따라서 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근 할 수 있다는 특징이 있으며 이러한 특징 때문에 역순 문자열 만들기, 실행 취소, 웹 브라우저 방문 기록(뒤로가기) 등의 분야에서 활용된다. 스택은 top에서 삽입과 삭제의 연산이 같이 이루어지며, ..

JAVA/자료구조 2023.10.02