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

 

자료구조

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

자료구조의 종류

Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다. 마치 프링글스과자 통에 감자칩을 쌓아놓은 형태와 비슷한 이 자료구조는 직역 그대로, 데이터(data)를 순서대로 쌓는 구조이다.

프링글스과자를 보면 가장먼저 들어간 감자칩은 가장 아래에 쌓여 있어 감자칩을 꺼낼때 가장 나중에 나올 수 있다. 다시말하면, 가장 나중에 들어간 감자칩은 가장 먼저 나올 수 있다.

이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 한다.

자료구조 Stack의 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.

Stack의 대표적인 사용 예제는 브라우저에서 뒤로가지, 앞으로 가기 기능을 구현할 때 활용된다.

 

Stack의 특징

1. LIFO(Last In First Out)

먼저들어간 데이터는 제일 나중에 나오는 후입선출의 구조이다.

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

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

stack.push(1); //stack에서 데이터를 넣는 메서드
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
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.

 

2. 데이터는 하나씩 넣고 뺄 수 있다.

Stack 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한꺼번에 여러 개를 넣거나 뺄 수 없다.

 

3. 하나의 입출력 방향을 가지고 있다.

Stack 자료구조는 데이터의 입출력 방향이 같다. 만약, 입출력 방향이 여러 개라면 Stack 자료구조라고 볼 수 없다.

 

 

Stack 메서드

 

메서드	기능
push()	스택에 데이터를 추가한다.
pop()	가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴한다.
size()	스택에 추가된 데이터의 크기를 리턴 한다.
peek()	가장 나중에 추가된 데이터를 리턴 한다.
show()	현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴한다.
clear()	현재 스택에 포함되어 있는 모든 데이터 삭제한다.

 

Using stack as Java ArrayList

// 미리 정의된 ArrayStack 객체를 사용합니다.
ArrayListStack stack = new ArrayListStack()

stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.push(4); // [1, 2, 3, 4]
stack.push(5); // [1, 2, 3, 4, 5]

System.out.println(stack.show()); // [1, 2, 3, 4, 5]

stack.pop(); // [1, 2, 3, 4]
stack.pop(); // [1, 2, 3]

System.out.println(stack.show()); // [1, 2, 3]

 

---

 

Queue

큐(Queue)는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다.

명절에는 고향으로 가기 위해 많은 자동차가 고속도로를 지난다. 고속도로에는 톨게이트가 있고, 자동차는 톨게이트에 진입한 순서대로 통행료를 내고 톨게이트를 통과한다.

톨게이트를 Queue 자료구조, 자동차는 데이터(data)로 비유할 수 있다.

자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있다. 

Queue는 컴퓨터와 연결된 프린터에서 순서대로 인쇄하는 방법으로 예를 들 수있다.

 

 

Queue의 특징

1. 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
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.

 

2. 데이터는 하나씩 넣고 뺄 수 있다.

Queue 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한꺼번에 여러 개를 넣거나 뺄 수 없다.

 

3. 두 개의 입출력 방향을 가지고 있습니다.

Queue 자료구조는 데이터의 입력, 출력 방향이 다르다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없다.

 

Queue 메서드

메서드	기능
add()	큐에 데이터를 추가 한다.
poll()	가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 한다.
size()	큐에 추가된 데이터의 크기를 리턴 한다.
peek()	큐에 가장 먼저 추가된 데이터를 리턴 한다.
show()	큐에 들어있는 모든 데이터를 String 타입으로 변환하여 리턴한다.
clear()	큐에 들어있는 모든 데이터를 삭제한다.