1.4 Stack과 Queue
- 스택(Stack): LIFO구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
- 큐(Queue): FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.
- 스택(Stack): 배열 적합
- 큐(Queue): LinkedList 적합
Stack의 메서드
| 메서드 | 설명 |
|---|---|
| boolean empty() | Stack이 비어있는지 알려준다. |
| Object peek() | Stack의 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지는 않음. (비었을 때는 EmptyStackException발생) |
| Object pop() | Stack의 맨 위에 저장된 객체를 꺼낸다. (비었을 때는 EmptyStack Exception발생) |
| Object push(Object item) | Stack에 객체(item)를 저장한다. |
| int search(Object o) | Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환. 못찾으면 -1을 반환. (배열과 달리 위치는 0이 아닌 1부터 시작) |
Queue의 메서드
| 메서드 | 설명 |
|---|---|
| boolean add(Object o) | 지정된 객체를 Queue에 추가한다. 성공하면 true를 반환. 저장공간이 부족하면 lllegalStateException발생 |
| Object remove() | Queue에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException발생 |
| Object element() | 삭제없이 요소를 읽어온다. peek와 달리 Queue가 비었을 때 NoSuch ElementException발생 |
| boolean offer(Object o) | Queue에 객체를 저장. 성공하면 true, 실패하면 false를 반환 |
| Objcet poll() | Queue에서 객체를 꺼내서 반환. 비어있으면 null을 반환 |
| Object peek() | 삭제없이 요소를 읽어 온다. Queue가 비어있으면 null을 반환 |
예제 11-7/ch11/StackQueueEx.java
package ch11;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class StackQueueEx {
public static void main(String[] args) {
Stack st = new Stack();
Queue q = new LinkedList(); // Queue인터페이스의 구현체인 LinkedList를 사용
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("= Queue =");
while(!q.isEmpty()) {
System.out.println(q.poll());
}
}
}
| 실행결과 |
|---|
| =Stack= |
| 2 |
| 1 |
| 0 |
| ==Queue= |
| 0 |
| 1 |
| 2 |
- 스택을 Stack클래스로 구현하여 제공
- 큐는 Queue인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지않다.
스택과 큐의 활용
스택의 활용 예 - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo,
웹브라우저의 뒤로, 앞으로
큐의 활용 예 - 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)
package ch11;
import java.util.*;
public class ExpValidCheck {
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("괄호가 일치합니다.");
}else {
System.out.println("괄호가 일치하지 않습니다.");
}
} catch (EmptyStackException e) {
System.out.println("괄호가 일치하지 않습니다.");
} //try
}
}
- 입력한 수식의 괄호가 올바른지 체크하는 예제
package ch11;
import java.util.*;
public class QueueEx1 {
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;
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")) {
// 입력받은 명령어를 저장하고,
save(input);
//LinkedList의 내용을 보여준다.
LinkedList tmp = (LinkedList)q;
for(int i=0;i<list.size();i++)
System.out.println((i+1)+"."+list.get(i));
}else {
save(input);
System.out.println(input);
} // if(input.equalsIgnoreCase("q")){
}catch(Exception e) {
System.out.println("입력오류입니다.");
}
}//while(true)
}//main()
public static void save(String input) {
//queue에 저장한다.
if(!"".equals(input))
q.offer(input);
// queue의 최대크기를 넘으면 제일 처음 입력된 것을 삭제한다.
if(q.size()>MAX_SIZE) // size()는 Collection인터페이스에 정의
q.remove();
}
}// end of class 
신입개발자 공부기록 블로그