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

Stack 이란?

• data를 순서대로 쌓는 자료구조
• 임시 데이터를 처리할 수 있는 간결한 도구
• 임시 데이터를 처리하되 데이터를 처리하는 순서에 특히 중점을 둔다
• 후입선출 (LIFO : Last In First Out)
  • 가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다.

//ex) 1, 2, 3, 4를 스택에 차례대로 넣는다. (push)

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

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

-----------------------------------------------------
//ex) 스택이 빌 까지 데이터를 전부 빼낸다. (pop)

stack.pop();
stack.pop();
stack.pop();
stack.pop();
//제일 마지막에 들어온 4부터 차례대로 빠진다.
//4 -> 3 -> 2 -> 1

 

Stack의 기타 메서드

stack.size();       //stack의 크기 출력
stack.empty();      //stack이 비어있는지 확인 (비어있으면 true)
stack.contains(1);  //stack의 값을 검색 (stack에 1이 있으면 true)

스택 사용시 제약

1. 데이터는 스택의 끝에만 삽입할 수 있다. (push)
2. 데이터는 스택의 끝에서만 삭제할 수 있다. (pop)
3. 스택의 마지막 원소만 읽을 수 있다.

top

• 삽입과 삭제가 일어나는 위치
• 스택의 가장 위에 있는 데이터
• 데이터가 삽인되면 top은 새로 삽입된 데이터의 위치로 갱신
• 항상 스택의 가장 위에 있는 데이터 = 가장 마지막에 삽입된 데이터의 위치

---

추상 데이터 타입

• 규칙 집합이며, 특정 결과를 얻기 위해 배열과 상호작용하는 방식을 다룬다.
• 내부적으로 어떤 데이터 구조를 쓰든 개의치 않는다.
• LIFO 방식으로 동작하는 데이터 원소들의 리스트면 된다.
• ⇒ 그래서 스택은 추상 데이터 타입에 속한다.

---

제약을 갖는 데이터 구조의 중요성

1. 제약을 갖는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있다.
2. 스택 같은 데이터 구조는 문제를 해결하는 새로운 사고 모델을 제공한다.

스택 요약

스택은 마지막에 들어 온 데이터부터 먼저 처리해야 할 때 이상적

 

---

Queue 란?

• 줄을 서서 기다리다, 대기행렬
• 임시 데이터를 처리하기 위해 디자인된 데이터 구조
• 추상 데이터 타입
• 선입선출 (FIFO : First In First Out)

//ex) 1, 2, 3을 큐에 차례대로 넣는다.

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

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

출력 방향 <-----------------------< 입력 방향
									1 <- 2 <- 3    //들어간 순서대로 1이 먼저, 3이 마지막으로 들어감

//ex) 큐가 빌 때까지 데이터를 전부 빼낸다.
queue.pull();
queue.pull();
queue.pull();

//1, 2, 3
//제일 첫 번째에 있는 데이터부터 차례대로 나옴

• 데이터는 하나씩 넣고 뺄 수 있다.
• 두 개의 입출력 방향을 갖고 있다.

 

큐의 메서드

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

//queue 값 추가
queue.add(1);     //삽입에 성공하면 true 반환
queque.offer(2);

//queue 값 삭제
queue.poll();   //큐가 비어있으면 null 반환
queue.remove();
queue.clear();  //큐의 모든 요소 제거(초기화)

//queue 첫번째 저장된 값 참조
queue.peak();

 

큐 사용시 제약 사항

1. 데이터는 큐의 끝에만 삽입할 수 있다. (스택과 동일)
2. 데이터는 큐의 앞에서만 삭제할 수 있다. (스택과 정반대)
3. 큐의 앞에 있는 원소만 읽을 수 있다. (스택과 정반대)

 

 

 

//누구나 자료구조와 알고리즘 개정2판 ch09