[자료구조] 스택(Stack)과 큐(Queue)

이미지 출처 : https://www.scaler.com/topics/java/stack-and-queue-in-java/

 

Stack : 쌓다

데이터를 순서대로 쌓는 자료구조

 

LIFO(Last In First Out) : 후입선출 구조

ex) 프링글스, 브라우저 뒤/앞 으로 가기

 

예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.

Stack<Integer> stack = new Stack<>(); //Integer형 스택 선언

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.

stack.pop();
stack.pop();
stack.pop();
stack.pop();
---------------------------

---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다

 

데이터를 '하나씩' 넣고 뺄 수 있고,

단 하나의 입출력 방향을 갖고 있다. 

 

Stack 메서드 

 

Stack<Integer> stack = new Stack<>(); //int형 스택 선언

• push(): 스택에 데이터를 추가
• pop(): 가장 나중에 추가된 데이터를 스택에서 삭제, 삭제한 데이터를 리턴
• size(): 스택에 추가된 데이터의 크기를 리턴
• peek(): 가장 나중에 추가된 데이터를 리턴
• show(): 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴
• clear(): 현재 스택에 포함되어 있는 모든 데이터 삭제
• stack.empty(); // stack이 비어있는지 check (비어있다면 true)
• stack.contains(1) // stack에 1이 있는지 check (있다면 true)

 

 

 

---

Queue : 

줄을 서서 기다리다, 대기행렬

 

FIFO (First In First Out) : 선입선출 구조

먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조

 

예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언

queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.add(3);     // queue에 값 3 추가
queue.add(4);     // queue에 값 4 추가

						   queue.add(데이터)
출력 방향 <---------------------------< 입력 방향
				     1 <- 2 <- 3 <- 4
				<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.

queue.poll();       // queue에 첫번째 값을 반환하고 제거
queue.poll();
queue.poll();
queue.poll();

						   queue.poll()
출력 방향 <---------------------------< 입력 방향

				<---------------------------<
1, 2, 3, 4

데이터는 하나씩 넣고 뺄 수 있음,

데이터 입력/출력 방향이 상이하다.

 

Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'

 

*콘텐츠에서 배운 데이터를 넣고 빼는 메서드는 add/poll 이었다.

궁금해서 찾아보니 enqueue에도 offer, add 메서드가 있고

dequeue에 poll, remove 메서드가 있었다.  

각 메서드들의 차이 참고 : https://cocoon1787.tistory.com/774

 

 

Queue 메서드

• add(): 큐에 데이터를 추가
• poll(): 가장 먼저 추가된 데이터를 큐에서 삭제, 삭제한 데이터를 리턴 (!= pop)
• size(): 큐에 추가된 데이터의 크기를 리턴
• peek(): 큐에 가장 먼저 추가된 데이터를 리턴
• show(): 큐에 들어있는 모든 데이터를 String 타입으로 변환하여 리턴
• clear(): 큐에 들어있는 모든 데이터를 삭제