Stack & LIFO (후입선출)
1. 정의
-
가장 최근에 요청된 것을 가장 먼저 처리, 가장 처음에 들어온 요청은 최후에 처리
- 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다
- top 으로 정한 곳을 통해서만 접근 가능해서, 거기서 데이터의 추가/삭제가 이뤄진다.
-
자료 구조 中
stack에 들어 있는 프로그램의 작업요청을 처리하는 방식- top 을 통해 삽입하는 연산 = 'push'
- top 을 통해 삭제하는 연산 = 'pop'
-
'stack underflow' : 비어있는 stack 에서 원소를 추출하는 경우
'stack overflow' : stack 이 넘칠 경우 -
어떤 경우에서는 LIFO 가 더 효율적일 수도 있다.
-
Stack에는 배열 기반의 컬렉션 프레임워크가 적합 (ArrayList 등...)
-
활용 예시
-
웹 브라우저의 앞/뒤로 가기
- 가장 나중에 열린 페이지부터 다시 보여준다.
-
수식 계산
-
수식 괄호 검사
- 연산자 우선순위 표현을 위한 괄호 검사
-
워드프로세스의 undo/redo
- undo (실행 취소) : 가장 나중에 실행된 것부터 실행 취소
-
역순 문자열 만들기
- 가장 나중에 입력된 문자부터 출력
-
2. 사용법
예시 1
public class StackQueue {
public static void main (String[] args) {
Stack<String> st = new Stack<String>();
st.push("0");
st.push("1");
st.push("2");
System.out.println("--- Stack ---")
While(!st.isEmpty()) {
System.out.println(st.pop());
}
}
}
/* 출력 결과
2
1
0
*/- Java에서는 스택을 Stack클래스로 구현하여 제공한다
예시 2 : 메서드
import java.util.Stack;
public class Col1 {
public static void main(String[] args) {
Stack<Integer> intStack = new Stack<Integer>(); // 선언 및 생성
intStack.push(1);
intStack.push(2);
intStack.push(3);
// 다 지워질때까지 출력
while (!intStack.isEmpty()) {
System.out.println(intStack.pop()); // 3,2,1 출력
}
// 다시 추가
intStack.push(1);
intStack.push(2);
intStack.push(3);
// peek() vs pop()
// 1. peek()
System.out.println(intStack.peek()); // 3 출력
System.out.println(intStack.size()); // 3 출력 (peek() 할때 삭제 안됬음)
// 2. pop()
System.out.println(intStack.pop()); // 3 출력
System.out.println(intStack.size()); // 2 출력 (pop() 할때 삭제 됬음)
System.out.println(intStack.pop()); // 2 출력
System.out.println(intStack.size()); // 1 출력 (pop() 할때 삭제 됬음)
// 다 지워질때까지 출력
while (!intStack.isEmpty()) {
System.out.println(intStack.pop()); // 1 출력 (마지막 남은거 하나)
}
}
}
/* 출력 결과
3
2
1
3
3
3
2
2
1
1
*/-
empty()- 스택이 비어있는지 확인
- 비어 있다면 true, 없으면 false 를 반환
- empty() vs isEmpty() 어떤 것이 맞을까? -> 참고: Java Stack 에서 empty() vs isEmpty()
-
peek()- 스택의 맨 위에 저장된 객체를 반환
- pop()과는 달리, 객체를 반환 후 삭제하지는 X (즉, 스택에서 객체를 꺼내지 않음)
- 비었을 때 EmptyStackException 을 반환
-
pop()- 스택의 맨 위에 저장된 객체를 반환하고 삭제
- 비었을 때 EmptyStackException 을 반환
-
push()- 스택에 객체를 저장(위에서 삽입)
-
search()- 스택에서 주어진 객체를 찾아서 그 위치를 반환
- 해당 객체가 있다면 1, 없으면 -1 을 반환
- 위치는 1부터 시작 (배열은 0부터 시작)
예시 3 : 수식 괄호 검사
import java.util.*;
public class Ex {
public static void main(String[] args) {
Stack st = new Stack();
String expression = "((3+5)*8-2)";
System.out.println("expression:"+expression);
try {
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == '(') { // ( 를 만나면, 스택에 넣기
st.push(ch + "");
} else if (ch == ')') { // ) 를 만나면, 스택에서 꺼내기
st.pop();
}
}
// 스택이 비어있을 경우 -> '('와 ')' 의 개수가 일치했을 경우
if (st.isEmpty()) {
System.out.println("괄호가 일치합니다.");
// 스택이 비어있지 않을 경우 -> EmptyStackException 발생
} else {
System.out.println("괄호가 일치하지 않습니다.");
}
} catch (EmptyStackException e) {
System.out.println("괄호가 일치하지 않습니다.");
}
}
}4. 호출 스택 (Call Stack)
1) 작동 방식
-
밑이 막힌 상자 위로 차곡차곡 쌓는다.
-
꺼낼 때는 마지막에 쌓은 것부터 나온다.
-
중간에 새로운 것을 끼어넣을 순 없다.
2) 정의
-
메소드 수행에 필요한 메모리가 제공되는 공간
-
메소드가 호출되면, 호출 스택에 메소드가 작업을 수행하는 데 필요한 공간이 만들어짐(호출 스택에 메모리가 할당됨)
작업이 종료되면, 호출 스택에서 메소드가 작업하던 메모리 공간이 사라진다. -
지역변수는 호출 스택(call stack)에 생성된다
- 힙 영역에는 인스턴스(인스턴스변수)가 생성된다
3) 대기, 실행
-
처음엔 main 메소드가 실행된다.
-
main 메소드가 println 을 호출하고, pritln 을 실행한다.
이때, 원래 실행중이던 main 메소드는 대기 상태로 변한다. -
prinln 메소드가 종료되면, 즉시 사라지고
대기중이던 main 메소드가 다시 실행 상태로 변한다.
Queue & FIFO (선입선출)
1. 정의
-
가장 오래된 요청(가장 먼저 요청된)을 가장 먼저 처리
-
한쪽 끝에서 삽입 작업, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
-
프론트(front) : 삭제 연산만 수행되는 곳 → 디큐(Dequeue) : front에서 이루어지는 삭제연산
리어(rear) : 삽입 연산만 수행되는 곳 → 인큐(Enqueue) : rear에서 이루어지는 삽입 연산
-
-
자료 구조 中
큐에 들어 있는 프로그램의 작업요청을 처리하는 방식-
"Queue" : (무엇을 기다리는 사람, 자동차 등의) 줄 , 혹은 줄을 서서 기다리는 것
-
스택과 달리(new Stack 처럼), 생성자가 없는 인터페이스
- Queue 는 생성자가 없는 껍데기라서 바로 생성할수는 없다. (껍데기 = 인터페이스)
- 생성자가 존재하는 클래스인
LinkedList를 사용하여Queue를 생성해서 받을 수 있다. - Queue 를 사용하기 위해선 java.util.LinkedList; 와 import java.util.Queue; 를 추가해야한다.
-
-
데이터를 꺼낼 때, 항상 첫 번째 저장된 데이터를 삭제
- 따라서, Queue에는 데이터의 추가/삭제가 쉬운 컬렉션 프레임워크가 적합 (LinkedList 등...)
-
활용 예시
주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용
-
최근 사용 문서 목록
-
인쇄 작업 대기 목록
-
Buffer (버퍼)
-
우선순위가 같은 작업 예약
-
은행 업무
-
콜센터 고객 대기시간
-
프로세스 관리
-
너비 우선 탐색(BFS, Breadth-First Search) 구현
-
캐시(Cache) 구현
-
선착순 티켓 판매
-
2. 사용법
예시 1
public class StackQueue {
public static void main (String[] args) {
Queue<String> q = new LinkedList<String>(); // LinkedList 클래스로 객체 생성
q.offer("0");
q.offer("1");
q.offer("2");
System.out.println("--- Queue ---")
While(!q.isEmpty()) {
System.out.println(q.pop());
}
}
}
/* 출력 결과
0
1
2
*/- Java에서는 큐를 Queue 인터페이스로만 정의해둬서, 별도의 클래스 제공은 X
- 따라서, Queue 인터페이스를 구현한 클래스들 中 하나를 사용하면 된다 (예시에서는 LinkedList를 사용함)
예시 2 : 메소드
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> intQueue = new LinkedList<>(); // 선언 및 생성
intQueue.add(1);
intQueue.add(2);
intQueue.add(3);
// 다 지워질때까지 출력
while (!intQueue.isEmpty()) {
System.out.println(intQueue.poll()); // 1,2,3 출력
}
// 다시 추가
intQueue.add(1);
intQueue.add(2);
intQueue.add(3);
// peek() vs pop()
// 1. peek()
System.out.println(intQueue.peek()); // 1 출력 (맨먼저 들어간값이 1 이라서)
System.out.println(intQueue.size()); // 3 출력 (peek() 할때 삭제 안됬음)
// 2. poll()
System.out.println(intQueue.poll()); // 1 출력
System.out.println(intQueue.size()); // 2 출력 (poll() 할때 삭제 됬음)
System.out.println(intQueue.poll()); // 2 출력
System.out.println(intQueue.size()); // 1 출력 (poll() 할때 삭제 됬음)
// 다 지워질때까지 출력
while (!intQueue.isEmpty()) {
System.out.println(intQueue.poll()); // 3 출력 (마지막 남은거 하나)
}
}
}-
add()- 지정된 객체를 큐에 추가
- 성공하면 true, 실패하면 false를 반환
- 저장 공간이 부족하면 IllegalStateException 발생
-
offer()- 큐에 객체를 저장
- 성공하면 true, 실패하면 false를 반환
-
remove()- 큐에서 객체를 꺼내 반환
- 비어있으면 NoSuchElementException 를 발생
-
element()- 삭제 없이 저장된 요소를 읽어온다
- peek()와 달리, 큐가 비었을 때 NoSuchElementException을 발생 (peek()는 null을 반환)
-
peek()- 삭제 없이 저장된 요소(맨 앞(front)가 가리키는 값)를 읽어온다
- 큐가 비었을 때 null을 반환
-
poll()- 큐에서 객체(맨 앞(front)가 가리키는 값)를 꺼내서 반환
- 큐가 비어 있으면 null을 반환
-
clear()- 큐에 저장된 데이터들을 삭제하고 초기화
-
enqueue()- 큐의 마지막 위치에 데이터를 추가하는 메서드
-
dequeue()- 큐의 첫 번째 위치에 있는 데이터를 반환하고 삭제하는 메서드
Java 에서 Queue 인터페이스로 선언하여 라이브러리를 사용할 경우, back() 과 같은 역할을 하는 메소드가 없다.
(맨 앞의 원소를 반환하는 peek() 메소드는 있음)
예시 3 : 최근 입력한 명령어 목록
import java.util.*;
public class Ex {
static Queue q = new LinkedList();
static final int MAX_SIZE = 5; // Queue에 최대 5개까지만 저장되도록 설정
public static void main(String[] args) {
System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");
while(true) {
System.out.println(">>");
try {
// 화면으로부터 라인단위로 입력받는다.
Scanner s = new Scanner(System.in);
String input = s.nextLine().trim();
if ("".equals(input)) {
continue;
}
// q 를 입력할 경우, 프로그램 즉시 종료
if (input.equalsIgnoreCase("q")) {
System.exit(0);
// help 를 입력할 경우, 다음 문장들을 출력
} else if (input.equalsIgnoreCase("help")) {
System.out.println(" help - 도움말을 보여줍니다.");
System.out.println("q 또는 Q - 프로그램을 종료합니다.");
System.out.println(" history - 최근에 입력한 명령어를 " + MAX_SIZE + "개 보여줍니다.");
// history 를 입력할 경우
} else if(input.equalsIgnoreCase("history")) {
// 입력받은 명령어를 저장하고,
save(input);
//LinkedList의 내용을 보여준다.
LinkedList tmp = (LinkedList)q;
ListIterator it = tmp.ListIterator();
while (it.hasNext()) {
System.out.println(++i + "." + it.next());
}
} else {
save(input);
System.out.println(input);
}
} catch(Exception e) {
System.out.println("입력오류입니다.");
}
}
}
public static void save(String input) {
//queue에 저장
if (!"".equals(input)) {
q.offer(input);
}
// queue의 최대크기를 넘으면, 제일 처음 입력된 것을 삭제
if (MAX_SIZE < q.size()) { // size() : Collection인터페이스에 정의돼있음
q.remove();
}
}
}hasNext() : 읽어올 요소가 남아있는지 확인하는 메서드. (요소가 있으면 true, 없으면 false)
next() : 다음 데이터를 반환
3. PriorityQueue
class GfG {
public static void main(String args[]) {
// 우선순위 큐 선언
PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
// 데이터 입력
pQueue.add(10);
pQueue.add(20);
pQueue.add(15);
// 첫 번째 데이터 결과 출력
System.out.println(pQueue.peek());
// 오름차순하여 데이터 출력 -> 출력한 데이터는 제거된다
System.out.println(pQueue.poll());
// 두 번째 데이터 15 출력
System.out.println(pQueue.peek());
}
}
/* 출력 결과
10
10
15
*/-
우선 순위에 따라 객체를 처리할 때 사용
-
FIFO 가 아닌요소의 우선순위에 따라 출력 순서가 바뀌므로, 일반적인 Queue 가 아니다 -
선입선출을 기본으로 하지만,
우선 순위에 따라 먼저 처리해야할 것이 있다면, 우선 순위 힙(heap)을 기반으로 처리
-
-
숫자가 작을수록 우선순위가 높음(오름차순)
4. Deque
1) 정의
-
큐 데이터 구조의 변형
-
"양방향 큐"
→ 양쪽 끝에서 요소를 추가/제거할 수 있는 구조
2) ArrayDeque
public class ArrayDequeDemo {
public static void main(String[] args) {
// Deque 선언
ArrayDeque<Integer> de_que = new ArrayDeque<Integer>(10);
// 값 입력
de_que.add(10);
de_que.add(20);
de_que.add(30);
de_que.add(40);
de_que.add(50);
// 결과 출력
System.out.println(de_que);
// deque초기화
de_que.clear();
// 첫 번째에 데이터 입력
de_que.addFirst(564);
de_que.addFirst(291);
// 마지막에 데이터 입력
de_que.addLast(24);
de_que.addLast(14);
// 결과 출력
System.out.println(de_que);
}
}
/* 출력 결과
[10, 20, 30, 40, 50]
[291, 564, 24, 14]
*/-
크기가 조정되는 배열
-
양쪽 끝에서 요소를 추가/제거하는 구조
참고: FIFO and LIFO (first-in, first-out and last-in, first-out) ; 선입선출 및 후입선출
참고: [자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시
참고: [자료구조] Stack(스택) : LIFO
참고: [Java] 스택(Stack)과 큐(Queue) Java로 구현하기
참고: 06. [자바] Stack, Queue 그리고 Deque - 자료구조
참고: [자바의 정석] chapter11 컬렉션 프레임웍 1.4 Stack과 Queue
참고: [Java] Iterator, hasNext() 와 next()
