- 스택과 큐 예제
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
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
2Stack 직접 구현하기
import java.util.EmptyStackException;
import java.util.Vector;
class MyStack extends Vector {
public Object push(Object item) {
addElement(item);
return item;
}
public Object pop() {
Object obj = peek(); // Stack에 저장딘 마지막 요소를 읽어온다.
// 만일 Stack이 비어있으면 peek()메서드가 EmptyStackException을 발생시킨다.
// 마지막 요소를 삭제한다. 배열의 index가 0부터 시작하므로 1을 빼준다.
removeElementAt(size() - 1);
return obj;
}
public Object peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
// 마지막 요소를 반환한다. 배열의 index가 0부터 시작하므로 1을 빼준다.
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public int search(Object o) {
int i = lastIndexOf(o); // 끝에서부터 객체를 찾는다.
// 반환값은 저장된 위치(배열의 index)이다.
if (i >= 0) { // 객체를 찾은 경우
return size() - i; // Stack은 맨 위에 저장된 객체의 index를 1로 정의하기 때문에 계산을 통해서 구한다.
}
return -1; // 해당 객체를 찾지 못하면 -1을 반환한다.
}
}스택과 큐의 활용
- 스택의 활용 예
수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로 - 큐의 활용 예
최근사용문서, 인쇄작업 대기목록, 버퍼(buffer) - 스택 활용 예제1 (웹사이트 뒤로가기)
import java.util.Stack;
public class StackEx1 {
public static Stack back = new Stack();
public static Stack forward = new Stack();
public static void main(String[] args) {
goURL("1. 네이트");
goURL("2. 야후");
goURL("3. 네이버");
goURL("4. 다음");
printStatus();
goBack();
System.out.println("= 뒤로가기 버튼을 누른 후 =");
printStatus();
goBack();
System.out.println("= '뒤로' 버튼을 누른 후 =");
printStatus();
goForward();
System.out.println("= '앞으로' 버튼을 누른 후 =");
printStatus();
goURL("codechobo.com");
System.out.println("= 새로운 주소로 이동 후 =");
printStatus();
}
public static void printStatus() {
System.out.println("back:" + back);
System.out.println("forward:" + forward);
System.out.println("현재화면은 '" + back.peek() + "' 입니다.");
System.out.println();
}
public static void goURL(String url) {
back.push(url);
if (!forward.empty())
forward.clear();
}
public static void goForward() {
if (!forward.empty())
back.push(forward.pop());
}
public static void goBack() {
if (!back.empty())
forward.push(back.pop());
}
}# 실행결과
back:[1. 네이트, 2. 야후, 3. 네이버, 4. 다음]
forward:[]
현재화면은 '4. 다음' 입니다.
= 뒤로가기 버튼을 누른 후 =
back:[1. 네이트, 2. 야후, 3. 네이버]
forward:[4. 다음]
현재화면은 '3. 네이버' 입니다.
= '뒤로' 버튼을 누른 후 =
back:[1. 네이트, 2. 야후]
forward:[4. 다음, 3. 네이버]
현재화면은 '2. 야후' 입니다.
= '앞으로' 버튼을 누른 후 =
back:[1. 네이트, 2. 야후, 3. 네이버]
forward:[4. 다음]
현재화면은 '3. 네이버' 입니다.
= 새로운 주소로 이동 후 =
back:[1. 네이트, 2. 야후, 3. 네이버, codechobo.com]
forward:[]
현재화면은 'codechobo.com' 입니다.- 스택 활용 예제2 (괄호 맞추기)
import java.util.EmptyStackException;
import java.util.Stack;
public class ExpValidCheck {
public static void main(String[] args) {
if (args.length != 1) {
System.out.println("Usage: java ExpValidCheck \"EXPRESSION\"");
System.out.println("Example: java ExpValidCheck \"((2+3)*1+3\"");
System.exit(0);
}
Stack st = new Stack();
String expression = args[0];
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
}
}- 큐 활용 예제
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Scanner;
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.print(">>");
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")) {
int i = 0;
// 입력받은 명령어를 저장하고,
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);
} // 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 classPriorityQueue
저장한 순서에 관계없이 우선순위(priority)가 높은 것 부터 꺼내는 Queue. 저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다.
import java.util.PriorityQueue;
import java.util.Queue;
class PriorityQueueEx {
public static void main(String[] args) {
Queue pq = new PriorityQueue();
pq.offer(3); // pq.offer(new Integer(3)); 오토박싱
pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(4);
System.out.println(pq); // pq의 내부 배열을 출력
Object obj = null;
// PriorityQueue에 저장된 요소를 하나씩 꺼낸다.
while ((obj = pq.poll()) != null)
System.out.println(obj);
}
}# 실행결과
[1, 2, 5, 3, 4]
1
2
3
4
5Deque(Double-Ended Queue)
한 쪽 끝으로만 추가/삭제할 수 있는 Queue와 달리 Deque(덱, 또는 디큐라고 읽음)은 양쪽 끝에 추가/삭제가 가능하다. 구현체로는 ArrayDeque와 LinkedList 등이 있다.
- 큐(queue)와 덱(deque)
덱은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다. - 덱(Deque)의 메서드에 대응하는 큐와 스택의 메서드
Iterator, ListIterator, Enumeration
컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스
Iterator
public interface Iterator {
boolean hasNext();
Object next();
void remove();
}
public interface Collection {
...
public Iterator iterator();
...
}- Iterator 인터페이스의 메서드
- ArrayList에 저장된 요소들을 출력하는 코드
List list = new ArrayList();
Iterator it = list.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}Map 인터페이스를 구현한 컬렉션 클래스는 키(key)와 값(value)을 쌍(pair)으로 저장하고 있기 때문에 iterator()를 직접 호출할 수 없고, 그 대신 keySet()이나 entrySet()과 같은 메서드를 통해서 키와 값을 각각 따로 Set의 형태로 얻어 온 후에 다시 iterator()를 호출해야 Iterator를 얻을 수 있다.
Map map = new HashMap();
...
Iterator it = map