[자료구조] 1. Stack & Queue

Stack

• 입력과 출력이 한 곳(방향)으로 제한
• LIFO(Last In First Out, 후입선출) : 마지막 입력 데이터가 먼저 출력
• 자바에서는 Vector로 구현 (ArrayList성질이 비슷하다)

 

---

함수

• push() : Stack에 객체를 저장합니다.
• pop() : Stack의 맨 위에 저장된 객체를 꺼냅니다.
• peek() : Stack의 맨 위에 저장된 객체를 반환합니다. Stack에서 꺼내지는 않습니다. 비었을 때 null을 반환합니다.
• empty() : Stack이 비어있는지 알려줍니다. 있으면 true, 없으면 false를 반환합니다.
• search() : Stack에서 주어진 객체를 찾아서 그 위치를 반환합니다. (배열과는 달리 1부터 시작합니다.)
• clear() : Stack의 모든 객체를 삭제합니다.
• size() : Stack의 크기를 반환합니다.

 

---

코드

Stack<Integer> stack = new Stack<>();
		stack.push(1); //1입력
		stack.push(2); //2입력
		stack.push(3); //3입력
		
		System.out.println(stack.size());  
		
		stack.pop(); //최상단 객체를 꺼내고 출력
		
		System.out.println(stack.peek());  
		System.out.println(stack.size());  

		System.out.println("stack.search(1): " + stack.search(1));
		System.out.println("stack.search(2): " + stack.search(2));
		System.out.println("stack.remove(1): " + stack.remove(1));
		System.out.println("stack.peek(): " + stack.peek());

 

 

출력

최상단부터 index값이 1이기 때문에 2의 index는 1, 1의 index는 2입니다.

따라서 remove(1)을 하면 index값이 1인 2가 삭제되므로

최상단은 1이 남게됩니다.

 

 

---

Queue

• 입력과 출력을 한 쪽(front,rear)으로 제한
• FIFO (First In First Out, 선입선출) : 가장 먼저 들어온 데이터가 가장 먼저 나감\
• java에서는 LinkedList로 구현되어 있음.

함수

		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);
		queue.add(2);
		System.out.println(queue.poll()); //1출력
		System.out.println(queue.peek()); //2출력

활용

• 버퍼
• 운영체제 스케줄링
• BFS