[Java] Stack, Queue

YoungMinKim·2020년 11월 8일
0
post-thumbnail

Section 01


Goal

Stack과 Queue에 대해 간략히 정리 해보자.

Queue Interface를 구현하는 Collection Class

Stack

  • LIFO(Last In First Out)
    • 선입 후출의 개념을 가진다.
    • 먼저 저장된 데이터가 가장 마지막에 빠져 나가는 자료 구조 형태

Queue

  • FIFO(First In First Out)
    • 선입 선출의 개념을 가진다.
    • 먼저 저장된 데이터가 가장 먼저 빠져 나간다.
    • 즉, 들어간 순서대로 데이터가 출력이 된다.

Stack과 Queue는 특정 알고리즘에서 사용이 된다.

Queue 인터페이스

기본 Method 제공

위 세 가지 Method는 예외 처리 메커니즘이 제공 되며, 실제로 예외가 발생 한다.
  • boolean add(E e)
    • 데이터 넣기.
    • 해당 데이터 공간에 데이터를 삽입 한다.
  • E remove()
    • 데이터 꺼내기.
    • 해당 Instance의 참조 값반환 해준다.
  • E element()
    • 데이터 확인하기.
    • 데이터를 꺼내지 않고 그 자리에 저장 한다.

추가 Method 제공

Queue 자료구조는 다른 자료 구조나, 알고리즘을 구현하는 도구가 되기도 한다.
예외 상황 자체가 알고리즘의 일부, 또는 해당 상황을 활용 할 수 도 있기 때문에. 
  • boolean offer(E e)
    • 넣기, 넣을 공간이 부족하면 false 반환
  • E poll()
    • 꺼내기, 꺼낼 대상이 없으면 null 반환
  • E peek()
    • 확인하기, 확인할 대상이 없으면 null 반환

Example

package com.java.study.Queue;

import java.util.LinkedList;

public class Queue {

	public static void main(String[] args) {
    	java.util.Queue<String> que = new LinkedList<String>();
		que.offer("A");
		que.offer("B");
		que.offer("C");

		// 우엇이 다음에 나올지 확인
		System.out.println("next : " + que.peek());

		// 첫 번째, 두 번째 인스턴스 꺼내기
		System.out.println(que.poll());
		System.out.println(que.poll());

		// 무엇이 다음에 나올지 확인
		System.out.println("next : " + que.peek());

		// 마지막 인스턴스 꺼내기
		System.out.println(que.poll());
	}
}
  • LinkedList<E>는 List< E >와 동시에 Queue< E >를 구현하는 Collection Class다.
  • 어떠한 타입의 참조 변수로 참조 하느냐에 따라서 리스트, 로 동작한다.'

스택(Stack)의 구현

  • Java에는 기본적으로 Stack 클래스가 존재 한다.
  • 과거에 작성된 Code의 호환성을 위해 구현되어 있는 클래스.

Deque< E > 인터페이스의 메소드

// Deque<E> 자료 구조의 경우 입구, 출구가 뚫려 있는 그림이기에 위치에 상관없이 데이터를 꺼낼 수 있다

앞으로 넣고, 꺼내고, 확인하기

  • boolean offerFirst(E e)
    • 넣기, 공간 부족하면 false 반환.
  • E pollFirst()
    • 꺼내기, 꺼낼 대상 없으면 null 반환.
  • E peekFirst()
    • 확인하기, 확인할 대상 없으면 null 반환.

뒤로 넣고, 꺼내고, 확인하기

  • boolean offerLast(E e)
    • 넣기, 공간 부족하면 false 반환.
  • E pollLast()
    • 꺼내기, 꺼낼 대상 없으면 null 반환.
  • E peekLast()
    • 확인하기, 확인할 대상 없으면 null 반환.

위 두 세트를 한 세트로 바라봐야 한다. 즉 들어가는 위치, 출력되는 위치만 다른 것이다.

내부적으로 예외 처리를 제공해주는 Method

  • 앞으로 넣고, 꺼내고, 확인하기

    • void addFirst(E e) : 넣기
    • E removeFirst() : 꺼내기
    • E getFirst() : 확인하기
  • 뒤로 넣고, 꺼내고, 확인하기

    • void addLast(E e) : 넣기
    • E removeLast() : 꺼내기
    • E getLast() : 확인하기

Map<k, v> 인터페이스를 구현하는 Collection 클래스

Map<key, value>는 실무에서 가장 많이 사용 되는 자료 구조로 중요하다.

Map<k, v>의 특징

  • Map은 일종의 자료 구조인데, 반복자를 제공하지 않는다.
  • Key - Value 한 쌍으로 데이터를 저장 한다.
    • Key : 데이터를 참조하는데 필요한 정보 또는 찾기 쉽도록 책갈피 역할을 해주는 것.
    • Value : 해당 Key의 실제 데이터를 의미한다.
  • Key는 중복을 허용하지 않고, Value는 중복을 허용 한다.

Map의 순차적인 접근?

  • Map은 Set< E >와 좀 더 적합하다.
  • Set< E >는 중복을 허용하지 않기 때문이다.

HashMap<K, V>의 순차적 접근 방법

HashMap<k, v> 클래스는 Iterable< T > 인터페이스를 구현하지 않으니 for-each문을 통해서, 혹은

반복자를 얻어서 순차적 접근을 진행 할 수 없다.

대신 다음 메소드 호출을 통해서 Key를 따로 모아 놓은 Collection Instance를 얻을 수 있다.

그리고 이때 반환된 Collection Instance를 대상으로 반복자를 얻을 수 있다.

public Set<K> **keySet**()

Example

package com.java.study;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapTest {

	public static void main(String[] args) {
		// [1] Map<k, v>
		Map<String, Object> map = new HashMap<String, Object>();
			
		map.put("a", "A");
		map.put("b", "B");
		map.put("c", "C");
			
		System.out.println("a : " + map.get("a"));
		System.out.println("b : " + map.get("b"));
		System.out.println("c : " + map.get("c"));
		System.out.println();
			
		map.remove("a");
			
		System.out.println("a : " + map.get("a"));
		System.out.println();
			
		// [2] HashMap<k, v>
		HashMap<String, Object> paramMap = new HashMap<String, Object>();
			
		paramMap.put("a", "Brown");
		paramMap.put("b", "Jane");
		paramMap.put("c", "Aplil");
		paramMap.put("d", "Kane");
		paramMap.put("e", "Mike");
		paramMap.put("f", "Michel");
			
			
		Set<String> paramKey = paramMap.keySet();
		for(String key : paramKey) {
			System.out.print(key + "\t");
		}
			
		System.out.println();
			
		for(String key : paramKey) {
			System.out.print(paramMap.get(key) + "\t");
		}
	}
}
profile
https://ym1085.github.io

0개의 댓글