Collection Framework 02 - Stack/ Queue + DeQueue

나는 Queue를 먼저 접했어서 두 가지가 굉장히 헷갈렸었다.

Stack을 먼저 배우면 Queue는 따라오는 거라 외우기 더 쉬울 것 같다는 생각이 든다.

---

• Stack & Queue : 데이터의 추가와 삭제가 단방향으로만 이루어짐
• DeQueue : 데이터의 추가와삭제가 양방향에서 가능

---

1. Stack (바구니, 후입선출 - Last In First Out, LIFO - )

Stack 자료구조

• 말 그대로 데이터를 쌓는 자료구조
• 쌓는 구조이기 때문에 아래에 있는 데이터를 꺼내려면 위에있는 데이터를 먼저 꺼내야 함
• 배열로 만드는 것이 유리

1) 메서드

메서드	설명
boolean empty()	비어있는지 확인
Object peek()	Stack의 맨 위에 저장된 객체 반환(삭제 X)
Object pop()	맨 위에 저장된 객체를 꺼냄(삭제) 비었을 때 사용하면 EmptyStackException 발생하므로 주의
Object push(Object item)	item 넣기
int search(Object o)	주어진 객체(o)를 찾아 그 위치 반환. 없을 경우 -1 반환 배열과 달리 위치가 1부터 시작

2) 사용

• Stack이라는 클래스가 따로 있기 때문에 객체를 생성하여 사용 가능

https://javaiary.tistory.com/91

프로그래머스) 크레인 인형뽑기 게임

• stack을 이용하여 푼 문제

3) 활용
수식계산, 수식괄호검사, undo/redo

---

2. Queue (빨대, 선입선출 - First In First Out, FIFO - )

Queue 자료구조

• 데이터를 한쪽으로 넣고 반대편으로 빼내는 자료구조
• 먼저 넣은 데이터가 가장 먼저 꺼내짐
• 링크드 리스트로 만드는 것이 유리

1) 메서드

메서드	설명
boolean add(Object o)   추가	지정된 객체를 Queue에 추가. 성공시 true반환 저장공간이 부족하면 예외발생
Object remove()   삭제	Queue에서 객체를 꺼내어 반환 비어있을 경우 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어옴 비어있을 경우 NoSuchElementException 발생
boolean offer(Object item)   추가	객체 저장(추가) . 성공시 true, 실패시 false 반환
Object poll()   삭제	Queue에서 객체를 꺼내어 반환. 비어있으면 null 반환 (예외 발생 X)
Object peek()	삭제 없이 요소를 읽어옴 (확인)

2) 사용

• 인터페이스만 존재하기 때문에 객체 생성 불가
• 따라서 Queue 인터페이스를 구현한 클래스들을 사용하여 queue의 메서드 사용 가능!

ex ) LinkedList

import java.util.LinkedList;
import java.util.Queue;	
	Queue<String> queue = new LinkedList<String>();

• 참조변수 타입이 Queue 이기 때문에 Queue 와 LinkedList의 공통된 부분만 사용하였다고 생각하면 됨.
  (LinkedList에만 있는 메서드를 고려하지 않아도 됨)

3) 활용
최근 사용 문서, 인쇄작업 대기목록, 버퍼

---

4.Queue 연습 - 최근 5개의 명령어만 출력하기

package CollectionFramework;

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Scanner;

public class QueueExample {
	static Queue q = new LinkedList();
	static final int MAX_SIZE = 5;

	public static void main(String[] args) {
		while (true) {
			System.out.print(">>");
			try {
				// 화면으로부터 라인단위로 입력받음
				Scanner scan = new Scanner(System.in);
				String input = scan.nextLine().trim(); // 문자열 앞,뒤 공백 제거

				if ("".equals(input)) continue;

				if (input.equalsIgnoreCase("q")) { // 대소문자 구분하지 않고 검사
					System.exit(0);
				} else if (input.equalsIgnoreCase("help")) {
					System.out.println("help - 도움말");
					System.out.println("q/Q - 프로그램 종료");
					System.out.println("history - 최근 입력 명령어 최대 " + MAX_SIZE + "건 노출");

				} else if (input.equalsIgnoreCase("history")) {
					int i = 0;
					// 입력받은 명령어 저장
					save(input);
					// 최근 입력 명령어 출력
					LinkedList tmp = (LinkedList) q;
					ListIterator itr = tmp.listIterator();

					while (itr.hasNext()) {
						System.out.println(++i + ". " + itr.next()); // 순서및 다음 명령어 출력

					}

				} else {
					save(input);
					System.out.println(input);
				} // if(input.equalsIgnoreCase("q"))

			} catch (Exception e) {
				System.out.println("입력 오류입니다. ");
			}
		}
	}

	public static void save(String input) {
		// queue에 저장
		if (!"".equals(input))
			q.offer(input);

		// queue의 최대 크기를 넘으면 가장 오래된 것 삭제
		if (q.size() > MAX_SIZE)
			q.remove();
	}
}// end

 

계속해서 history를 뽑아내더라도 가장 오래된 목록이 계속해서 삭제됨

• trim()
  문자열 앞, 위에 공백이 있을 경우 제거
• equalsIgnoreCase()
  문자열의 대소문자를 구분하지 않고 같은지만 확인
• "".equals(변수)
  변수가 null 일 경우도 포함 됨
  • 변수 != null && 변수.equals("") 와 동일
• ListIterator부분
  • list.size()를 받아서 일반적인 for문을 돌려도 됨

---

5. Dequeue (Double-ended Queue)

Dequeue 자료구조

• 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조

1) 데이터 추가

addFirst()	덱의 앞쪽에 엘리먼트를 삽입 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생
offerFirst()	덱의 앞쪽에 엘리먼트를 삽입 정상적으로 엘리먼트가 삽입된 경우 true 리턴 용량 제한에 걸리는 경우 false 리턴
addLast()	덱의 마지막 쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량 초과시 예외가 발생
add()	= addLast()
offerLast()	덱의 마지막 쪽에 엘리먼트를 삽입 정상적으로 엘리먼트가 삽입된 경우 true 리턴 용량 제한에 걸리는 경우 false를 리턴

2) 데이터 삭제

removeFirst()	앞쪽 엘리먼트 하나 제거 후, 해당 엘리먼트를 리턴 덱이 비어있으면 예외 발생
pollFirst()	앞쪽 엘리먼트 하나 제거 후, 해당 엘리먼트를 리턴 덱이 비어있으면 null 리턴
removeLast()	뒤쪽 엘리먼트 하나 제거 후, 해당 엘리먼트를 리턴 덱이 비어있으면 예외 발생
pollLast()	뒤쪽 엘리먼트 하나 제거 후, 해당 엘리먼트를 리턴 덱이 비어있으면 null 리턴
remove()	= removeFirst()
poll()	= pollFirst()

3) 데이터 불러오기 (삭제 X)

getFirst()	가장 앞쪽 엘리먼트 리턴 덱이 비어있으면 예외 발생
peekFirst()	가장 앞쪽 엘리먼트 리턴 덱이 비어있으면 null 리턴
getLast()	가장 뒤쪽 엘리먼트 리턴 덱이 비어있으면 예외 발생
peekLast()	가장 뒤쪽 엘리먼트 리턴 덱이 비어있으면 null 리턴
peek()	= peekFirst()