Stack 스택 클래스
-
밑이 막힌 상자 ⨆
-
LIFO 구조 : Last In First Out. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
-
저장(push) 순서 : 0 -> 1 -> 2
-
추출(pop) 순서 : 2 -> 1 -> 0
-
✨배열에 적합 : 스택을 배열로 구현하자!
-
예) 웹브라우저의 뒤로/앞으로
Queue 큐 인터페이스
-
양끝이 뚫린 상자
-
FIFO 구조 : First In First Out. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.
-
저장(offer) 순서 : 0 -> 1 -> 2
-
추출(poll) 순서 : 0 -> 1 -> 2
-
✨LinkedList에 적합 : 쿠를 LinkedList로 구현하자!
-
예) 최근 사용문서, 인쇄작업대기목록, 버퍼
-
인터페이스 -> ✨✨Queue를 구현한 클래스를 사용
Stack 선언
Stack st = new Stack(); Stack<> st = new Stack<>();
Stack 메소드
저장, 추가(push)
Object push(Object item)
- Stack에 객체 item 저장
추출, 삭제(pop)
Object pop()
-
Stack의 맨 위에 저장된 객체를 꺼낸다.
-
예외발생O : 비었을 땐
EmptyStackException발생
읽기
Object peek()
-
Stack의 맨 위에 저장된 객체를 반환.
-
맨 위에 있는 걸 보기만 함!
-
✨
pop()과 달리 Stack에서 객체를 꺼내지 않는다. -
비었을 땐
EmptyStackException발생
검색
int search(Object o)
-
Stack에서 주어진 객체 o를 찾아서 그 위치를 반환, 못찾으면 -1 반환
-
✨✨✨배열과 달리 위치는 0이 아닌 1부터 시작, 마지막에 저장한 데이터가 1
배열s = [0, 1, 2]
index = 3/ 2/ 1boolean empty()
- Stack이 비어있는지, 비어있으면 true
Queue 선언
Queue q = new LinkedList(); Queue<> q = new LinkedList<>();
Queue 메소드
저장, 추가(offer)
boolean offer(Object o)
-
Queue에 객체 o 저장. 성공하면 true
-
✨예외발생 X
boolean add(Object o)
-
Queue에 객체 o 추가. 성공하면 true
-
예외발생 O : 저장공간이 부족하면
IllegalStateException
-> ✨✨try-catch반드시 사용!!
추출, 삭제(poll)
Object poll()
-
Queue에서 맨 처음의 요소를 꺼내서 반환.
-
✨예외발생 X : 비어있으면 null 반환
-> null을 처리하고 싶다면if(o == null) ...
Object remove()
-
Queue에서 맨 처음의 요소를 꺼내서 반환.
-
예외발생 O : 비어있으면
NoSuchElementException
-> ✨✨try-catch반드시 사용!!
읽기
Object peek()
-
삭제없이 맨 처음의 요소를 읽어온다.
-
✨예외발생 X : 비어있으면 null 반환
Object element()
-
삭제없이 맨 처음의 요소를 읽어온다.
-
예외발생 O : 비어있으면
NoSuchElementException
-> ✨✨try-catch반드시 사용!!
검색
boolean isEmpty()
- 비어있는지, 비어있으면 true
추가-삭제-읽기
예외발생 X
✨offer() - poll() - peek()
예외발생 O
add() - remove() - element()
ex11_02
import java.util.LinkedList;
import java.util.Queue;
//import java.util.*로 한방에 해도 됨
import java.util.Stack;
public class Ex11_02 {
public static void main(String[] args) {
Stack st = new Stack();
Queue q = new LinkedList(); //Queue인터페이스의 구현체 LL
st.push("0");
st.push("1");
st.push("2");
q.offer("0");
q.offer("1");
q.offer("2");
System.out.println("== Stack ==");
while(!st.empty()) { //***차있으면
System.out.println(st.pop());
}
System.out.println("st.empty() = "+st.empty());
System.out.println("== Queue ==");
while(!q.isEmpty()) {
System.out.println(q.poll());
}
System.out.println("q.isEmpty() = "+q.isEmpty());
}
}== Stack ==
2
1
0
st.empty() = true
== Queue ==
0
1
2
q.isEmpty() = true활용
스택의 활용 예
- 수식계산, 수식괄호검사(괄호의 짝 일치여부), undo/redo, 웹브라우저의 뒤로/앞으로
큐의 활용 예
- 최근 사용문서, 인쇄작업대기목록, 버퍼
수식괄호검사 예제
Ex11_03
알고리즘
-
'(' 만나면 Stack 요소 채우기(push)
-
')' 만나면 Stack 요소 없애기(pop)
-
Stack이 비어있으면(empty) 수식괄호의 짝이 일치, 차있으면 불일치
import java.util.EmptyStackException;
import java.util.Stack;
public class Ex11_03 {
public static void main(String[] args) {
if(args.length !=1) {
System.out.println("Usage:java Ex11_03 \"EXPRESSION\"");
System.out.println("Example:java Ex11_03 \"((2+3)*1)+3\"");
System.exit(0);
}
Stack st = new Stack();
String expression = args[0];
System.out.println("expression: "+expression);
//******')'이 많을 경우 EmptyStackException이 생긴다!!!
//****예외처리
try {
for(int i=0; i<expression.length(); i++) {
char c = expression.charAt(i); //***
if(c=='(') {
st.push(c + "");
//***Stack 객체에 넣는거기에 기본형char가 아닌 String이 더 좋다??
} else if(c==')') {
st.pop();
}
}
if(st.empty()) {
System.out.println("괄호 쌍이 일치합니다.");
} else {
System.out.println("괄호 쌍이 일치하지 않습니다."); // '(' 이 더 많음
}
} catch (EmptyStackException e) {
// ')' 이 더 많음 -> EmptyStackException
System.out.println("EmptyStackException : 괄호 쌍이 일치하지 않습니다.");
}
}
}
👀✨👀 주의해야 할 것
-
✨✨
EmptyStackException예외처리를 하자!!! -
char ch = charAt(i)
👀👀 궁금해서 찾아본 것
empty() vs. isEmpty()
empty()
Tests if this stack is empty.
Returns:true if and only if this stack containsno items; false otherwise.
Stack클래스의 메소드
isEmpty()
Tests if this vector has no components.
Specified by: isEmpty() in List, Overrides: isEmpty() in AbstractCollection
Returns:true if and only if this vector hasno components, that is, its size is zero; false otherwise.
List인터페이스의 메소드- List의 예전 버전인 vector와 연관
- 결론
empty(): Stack 에서만 사용isEmpty(): Stack, Queue(LinkedList), ... 모든 클래스 다 사용가능
최근 5개 명령어 저장하기
ex11_04
import java.util.*;
public class Ex11_04 {
static Queue q = new LinkedList();
static final int MAX_SIZE = 5; //Queue에 최대 5개까지만 저장하도록
//****static 이유 : iv가 아닌 cv만을 static메소드가 사용할 수 있으니까!!!
public static void main(String[] args) {
System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");
while(true) {
System.out.print(">> ");
try {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine().trim();
//앞뒤공백제거, 한줄 단위로
if("".equals(input)) continue; //맨밑으로가 다음 반복으로
//***두 문자열의 위치가 바뀐다면?? input이 null일 경우 오류가 나기에 방지차원!!!
if(input.equalsIgnoreCase("q")) {
System.exit(0);
//???? 아래 else는 안해도 될 것 같은데??
} 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")) {
//우선 입력받은 명령어 history 저장하고
save(input);
//LL의 내용을 보여준다.
LinkedList list = (LinkedList)q;
//***q로는 못하니까(인터페이스!) -> 새로운 리모콘+q를 형변환해서 넣기
final int SIZE = list.size();
//이렇게 하는게 더 좋은 코드!!
for(int i=0; i<SIZE; i++) {
System.out.println((i+1)+". "+list.get(i));
}
} else { //history 입력안하고 다른 명령어 입력하면 저장하고 출력
save(input);
System.out.println(input);
}
} catch (Exception e) {
System.out.println("입력오류입니다.");
}
}//while(true) 끝
}//main 끝
public static void save(String input) {
//input이 공백이 아니면 queue에 저장
if(!"".equals(input)) q.offer(input);
//***queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제
if(q.size()>MAX_SIZE) q.poll();
//size() - Collection인터페이스에 정의
}
}
✨👀✨주의해야 할 것
-
✨✨static 메소드는 iv를 접근 못하므로 cv로 만들어야 한다.
-
참조변수도 static 가능
-
반복문을 돌 동안 계속 size()를 재게 하는 건 안좋다. final을 사용하여 상수화로 쓰자!
