Stack과 Queue

목차

1) Stack과 Queue의 기본 개념 및 특징

2) Stack과 Queue의 메서드

3) Stack과 Queue의 활용 예시

 

---

1) Stack과 Queue의 기본 개념 및 특징

 

 

 

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO (Last In First Out) 구조로 되어있고, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO (First In First Out) 구조로 되어있다.

 

예를 들어 스택에 0, 1, 2 의 순서로 데이터를 넣었다면 꺼낼 때는 2, 1, 0의 순서로 꺼내게 된다.

큐에는 0, 1, 2 순서로 데이터를 넣었다면 0, 1, 2 의 순서로 데이터를 꺼내게 된다.

 

2) Stack과 Queue의 메서드

 

Stack의 메서드

 

 

 

 

Queue의 메서드

 

 

3) Stack과 Queue의 활용 예시

 

import java.util.*;

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());
		}
	}

}

<위 코드 실행 결과>

 

✔ 스택의 활용 예 : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/ 앞으로
✔ 큐의 활용 예 : 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

 

 

1. 웹브라우저의 '뒤로', '앞으로' 버튼 기능 구현 → 스택 2개 이용

import java.util.Stack;

public class StackEx {
	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("bbinya.tistory.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());
	}
}

위 코드를 실행한 결과

 

2. 최근 명령어 이력 조회하기 → Queue 이용

 

import java.util.*;

public class QueueEx {
	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 sc = new Scanner(System.in);
				String input = sc.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);
				}
				
			}catch(Exception e) {
				System.out.println("입력 오류 입니다.");
			}
		}
	}
	
	public static void save(String input) {
		//queue에 저장한다.
		if(!"".equals(input)) q.offer(input);
		
		// queue의 최대크기를 넘으면 제일처음 입력된 것을 삭제한다.
		if(q.size() > MAX_SIZE) q.remove();
	}
}

 

위 코드를 실행한 결과

---