최근에 코딩 테스트를 풀었는데 위 세개의 항목을 실제로 사용한 적도 없고, 그렇다고 이해하고 있지 않았다.
그런 이유로 위 세개를 정리한다.
Stack, Queue, PriorityQueue... 내가 갈게 ㅠㅠ
1. stack
스택 클래스는 객체의 LIFO를 나타낸다. vector가 스택으로 취급될 수 있도록 다섯개의 작업을 가진 Vector클래스를 extends 한다. 보통의 push와 pop작업이 제공된다. top을 뽑아내는 메소드 뿐만 아니라, 스택이 비었는지, 그리고 한 아이템을 스택에서 찾는 메소드, 또 top에서 얼마나 떨어져 있는지 같은 기능을 제공한다.
출처 : https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
스택은 객체의 LIFO stack을 나타낸다. 다섯개의 작동을 가진 Vector class를 상속한다. (Vector가 스택으로 쓰이도록 한다.) Stack이 Vector와 연관되어 있구나...
docs의 경우 설명이 좀 정석이긴 하지만 무언가 잘 와닿지 않는 경우가 있어서 다른곳의 설명을 참고했다.
Java Stack Class
자바에서, Stack은 Vector class를 extends 하는 Collection framework에 속한 클래스다. 또한, interface List, Collection, Iterable, Cloneable, Serializable을 구현한다. 객체의 last-in-first-out 스택을 나타낸다. 스택 클래스를 사용하전에, 우리는 java.util.package를 import해야만 한다. 스택 클래스는 아래에 보여진것 처럼 Collection framework 계층 구조로 나열한다.
생성자 및 메소드 설명 더보기 클릭!
더보기
생성자와 설명
| Stack()
Creates an empty Stack. => 빈 stack을 생성
|
수정자와 타입메소드, 그리고 설명
| boolean | empty()
Tests if this stack is empty. => stack이 비었는지 확인
|
| E | peek()
Looks at the object at the top of this stack without removing it from the stack.
=> stack에서 지우지 않고 꼭대기 object를 찾음. |
| E | pop()
Removes the object at the top of this stack and returns that object as the value of this function.
=> stack의 꼭대기 객체를 지우고, 함수의 값으로 객체를 반환한다. |
| E | push(E item)
Pushes an item onto the top of this stack.
=> stack의 꼭대기에 아이템을 push한다. |
| int | search(Object o)
Returns the 1-based position where an object is on this stack.
=> 객체가 스택에 있는 위치를 반환한다. |
2. 구현 - Stack
stack01.java
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Stack;
import java.util.stream.Stream;
public class stack01 {
public static void main(String[] args) { //declare and initialize a stack object
Stack stack = new Stack();
stack.push("bangal");
stack.push("joshe");
stack.push("shane");
System.out.println("Stack elements using Java 8 forEach:");
//get a stream for the stack
Stream stream = stack.stream();
//traverse though each stream object using forEach construct of Java 8
stream.forEach((element) -> {
System.out.print(element + " ");
// print element
});
System.out.println(" Stack elements using Java 8 forEachRemaining:");
//define an iterator for the stack
Iterator stackIterator = stack.iterator();
//use forEachRemaining construct to print each stack element
stackIterator.forEachRemaining(val -> { System.out.print(val + " "); });
System.out.println("\n===============================\n");
//declare a stack object
Stack stack1 = new Stack();
//print initial stack
System.out.println("Initial stack : " + stack);
//isEmpty ()
System.out.println("Is stack Empty? : " + stack.isEmpty());
//push () operation
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
//print non-empty stack
System.out.println("Stack after push operation: " + stack);
//pop () operation
System.out.println("Element popped out:" + stack.pop());
System.out.println("Stack after Pop Operation : " + stack);
//search () operation
System.out.println("Element 10 found at position: " + stack.search(10));
System.out.println("Is Stack empty? : " + stack.isEmpty());
System.out.println("===========================");
Stack <Integer> stk = new Stack<>();
stk.push(119);
stk.push(203);
stk.push(988);
ListIterator<Integer> ListIterator = stk.listIterator(stk.size());
System.out.println("Iteration over the Stack from top to bottom:");
while (ListIterator.hasPrevious())
{
Integer avg = ListIterator.previous();
System.out.println(avg);
}
/*
Stack elements using Java 8 forEach:
bangal joshe shane Stack elements using Java 8 forEachRemaining:
bangal joshe shane
===============================
Initial stack : [bangal, joshe, shane]
Is stack Empty? : false
Stack after push operation: [bangal, joshe, shane, 10, 20, 30, 40]
Element popped out:40
Stack after Pop Operation : [bangal, joshe, shane, 10, 20, 30]
Element 10 found at position: 3
Is Stack empty? : false
===========================
Iteration over the Stack from top to bottom:
988
203
119
*/
}
}
stack은 뭐... 엄청 어려운 것은 아니다.
Algorithm
1. Top이라고 불리는 pointer는 스택의 top 원소를 추적하는데 사용된다.
2. 초기화 시, top의 값은 -1이다. 그렇게 함으로 stack이 비었을 때를 확인할 때 top == -1인지를 확인한다.
3. 원소을 넣을 때, top의 값이 증가하고 새로운 원소를 top이 가리키는 위치에 넣는다.
4. 원소를 뽑아낼 때, top에 가리켜진 원소를 반환하고 top의 값을 줄인다.
5. 원소를 넣기 전에, stack이 이미 가득 찼는 지 확인한다.
6. 원소를 뽑아내기 전에, stack이 이미 비었는지 확인한다.
출처 : https://medium.com/javarevisited/when-to-use-stack-data-structure-9ac3dfa4d10
3. Queue
Queue란?
this is the endless queue of car!
"차가 끝없이 이어져 있다!" 라고 표현한 것인데 사전적 의미로 queue는 줄을 서다, 혹은 줄을 의미한다.
처리과정에 앞서서 원소를 잡기위해 고완된 collection
(A collection designed for holding elements prior to processing).
queue의 전체적인 구조는 다음과 같다.
위의 구조로 보면 Queue를 구현할 수 있는 구현 클래스는 LinkedList, ArrayDeque, PriorityQueue가 있다.
Enqueue : 큐 맨 뒤에 데이터 추가
Dequeue : 큐 맨 앞쪽의 데이터 삭제
생성자 및 메소드 더보기 클릭!
더보기
Modifier and TypeMethod and Description
| boolean | add(E e)
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
|
| E | element()
Retrieves, but does not remove, the head of this queue.
=> queue의 맨 앞 데이터를 반환하지만 삭제는 안한다. |
| boolean | offer(E e)
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
|
| E | peek()
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
|
| E | poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.
|
| E | remove()
Retrieves and removes the head of this queue.
|
출처 : https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
근데 무언가 기능이 겹치는 method들이 있다.
| 예외 던짐 | 리턴 | |
| enqueue(추가) | add(E e) | offer(E e) |
| dequeue(삭제) | remove() | poll() |
| peek(검사) | element() | peek() |
참고 : https://goodteacher.tistory.com/112
자세한것은 구현을 통해서 확인하려고 한다.
Queue01.java
import java.util.LinkedList;
import java.util.Queue;
public class Queue01 {
public static void main(String[] args) {
Queue<Integer> queue1 = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
queue1.add(1); // queue에 값 1 추가
queue1.add(2); // queue에 값 2 추가
queue1.offer(3); // queue에 값 3 추가
System.out.println("queue1 = " + queue1);
Integer pollInteger = queue1.poll();// queue에 첫번째 값을 반환하고 제거 비어있다면 null
System.out.println("pollInteger = " + pollInteger);
Integer removedData = queue1.remove();// queue에 첫번째 값 제거
System.out.println("removedData = " + removedData);
System.out.println("queue1 = " + queue1);
System.out.println(" ============================ " );
queue1.clear(); // queue 초기화
System.out.println("queue1 = " + queue1);
/*
결과
queue1 = [1, 2, 3]
pollInteger = 1
removedData = 2
queue1 = [3]
============================
queue1 = []
*/
}
}4. PriorityQueue
priority quque의 원소는 natural ordering에 따라, 혹은 queue 생성 타임에 제공된 Comparator에 의해 정렬된다. (생성자가 어떤것을 사용하냐에 따라서도)
Priority queue는 null 원소를 허용하지 않는다.
natural ordering에 의존적인 Priority queue는 또한 비교 불가능한 객체의 삽입을 허용하지 않는다. (만약 그런것을 넣으면 ClassCastException이 날겁니다.)
여기서 흥미로운 점은 natural 정렬을 해주는데, Comparator가 내부에 구현되어 있다는 것이다. 또한, null을 허용하지 않으며 non-comparable 객체의 추가를 허용하지 않는다.
지원 생성자 및 메소드 더보기 클릭!
더보기
Constructor Summary
Constructors Constructor and Description
| PriorityQueue()
Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
|
| PriorityQueue(Collection<? extends E> c)
Creates a PriorityQueue containing the elements in the specified collection.
|
| PriorityQueue(int initialCapacity)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
|
| PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
|
| PriorityQueue(PriorityQueue<? extends E> c)
Creates a PriorityQueue containing the elements in the specified priority queue.
|
| PriorityQueue(SortedSet<? extends E> c)
Creates a PriorityQueue containing the elements in the specified sorted set.
|
Method Summary
Methods Modifier and TypeMethod and Description
| boolean | add(E e)
Inserts the specified element into this priority queue.
|
| void | clear()
Removes all of the elements from this priority queue.
|
| Comparator<? super E> | comparator()
Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.
|
| boolean | contains(Object o)
Returns true if this queue contains the specified element.
|
| Iterator<E> | iterator()
Returns an iterator over the elements in this queue.
|
| boolean | offer(E e)
Inserts the specified element into this priority queue.
|
| E | peek()
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
|
| E | poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.
|
| boolean | remove(Object o)
Removes a single instance of the specified element from this queue, if it is present.
|
| int | size()
Returns the number of elements in this collection.
|
| Object[] | toArray()
Returns an array containing all of the elements in this queue.
|
| <T> T[] | toArray(T[] a)
Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.
|
출처 : https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
구현
PriorityQueue01.java
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueue01 {
public static void main(String[] args) {
// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>();
// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Collections.reverseOrder());
// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue3 = new PriorityQueue<>();
// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue4 = new PriorityQueue<>(Collections.reverseOrder());
//출처 : https://crazykim2.tistory.com/575
Queue priorityQueue01 = new PriorityQueue<>();
priorityQueue01.add(1);
priorityQueue01.add(10);
priorityQueue01.add(8);
System.out.println("priorityQueue01 = " + priorityQueue01);
priorityQueue01.add(2);
priorityQueue01.add(9);
priorityQueue01.add(15);
System.out.println("priorityQueue01 = " + priorityQueue01);
/*
결과
priorityQueue01 = [1, 10, 8]
priorityQueue01 = [1, 2, 8, 10, 9, 15]
Process finished with exit code 0
*/
//출처 : https://crazykim2.tistory.com/575
}
}
처음 priority queue에 값을 넣어주고 출력시에는 1, 10, 8이 되는데
2, 9, 15를 넣어주니 [1, 2, 8, 10, 9, 15]이 된다.
이것은 priority queue가 일반적으로 heap을 이용하여 구현되어 있기 때문이다.
다음에 heap에 대해서도 공부하도록 하겠다.
결론적으로 다음 값은 다음 그림과 같은 tree구조가 될 것이다.
여기서 add를 하나 더 해볼것이다. 그러면 어떤 일이 일어나는지 그림을 통해 알아보자.
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueue01 {
public static void main(String[] args) {
// 동일 코드 생략
priorityQueue01.add(7);
System.out.println("priorityQueue01 = " + priorityQueue01);
}
}
새로 추가한 값이 8보다 작으니까 위로 이동한다.
출력 결과는 다음과 같다.
priorityQueue01 = [1, 10, 8]
priorityQueue01 = [1, 2, 8, 10, 9, 15]
priorityQueue01 = [1, 2, 7, 10, 9, 15, 8]
우리가 예상한대로 됏네!
그러면 가장 위에 있는 친구를 제거하면 어떻게 될지도 궁금하다.
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueue01 {
public static void main(String[] args) {
//동일 코드
Object poll1 = priorityQueue01.poll();
System.out.println("poll1 = " + poll1);
System.out.println("priorityQueue01 = " + priorityQueue01);
}
}
결과는 다음과 같다.
결과
priorityQueue01 = [1, 10, 8]
priorityQueue01 = [1, 2, 8, 10, 9, 15]
priorityQueue01 = [1, 2, 7, 10, 9, 15, 8]
poll1 = 1
priorityQueue01 = [2, 8, 7, 10, 9, 15]
결과로 보면 다음처럼 정렬이 된다.
이번에는 stack, queue, priority queue를 알아봤는데
다음 글에 queue의 구현체인 LinkedList와 ArrayDeque를 정리할 것이다.
그리고 Priority Queue, LinkedList, ArrayDeque를 한번 비교해볼 것이다.
'programming language > Java' 카테고리의 다른 글
| Deque, LinkedList 와 ArrayDeque (0) | 2022.04.11 |
|---|---|
| 직렬화란 무엇인가 ? / serialVersionUID 설정 이유 (0) | 2022.04.11 |
| List 관련 질문 답변 정리 (3) | 2022.04.04 |
| static / final / static final이란? (2) | 2022.04.03 |
| 어노테이션(annotation)이란? (0) | 2022.03.31 |