2.2.1 자료구조 - 스택과 큐

프링글스 통에서 맨 위에 있는 감자칩은
가장 나중에 생산된 것일까? 먼저 생산된 것일까?

자료구조 강의에 들어서면서
가장 먼저 배웠던 것은 스택이었다.

스택은 LIFO(Last In First Out)의 규칙을 가지며,
보통 프링글스 통을 예로 든다.

큐는 FIFO(First In First Out)의 규칙을 가지며,
편의점 점장이라면 좋아할 자료 구조일 것이다.

---

Stack

Java에서는 Stack을 제공하고 있어
java.util.Stack을 import 하면 바로 사용이 가능하다.

---

기본 메서드

import java.util.Stack;

Stack<Integer> stack = new Stack();
// stack에 값 넣기
stack.push(1);
stack.push(2);
stack.push(3);
// stack = [1, 2, 3]

// stack에 값 빼기
stack.pop();
// stack = [1, 2]
int n = stack.pop();
// stack = [1], n = 2

// stack의 최상단 값
stack.peek();
// 1

// stack이 비었는지
stack.isEmpty();
// false

---

java stack 특징

java에서 제공하고 있는 stack은
Vector 클래스를 상속받기 때문에
중간에 데이터를 삽입하거나 삭제도 가능하다.

...
// 특정 인덱스의 원소 찾기
stack.get(1);
// 특정 인덱스에 삽입
stack.set(1, 2);
// 특정 인덱스의 원소 삭제
stack.remove(1);

사실 이 기능을 사용할 지는 모르겠다.

---

직접 구현

ArrayList를 이용해 Stack을 직접 구현이 가능하다.

class Stack<E> {
	private ArrayList<E> stack;
    public void Stack(){
    	this.stack = new ArrayList<E>();
    }
    public void push(E data){ stack.add(data); }
    public E pop(){
    	if (stack.isEmpty()) return null;
        return stack.remove(stack.size()-1);
    }
    public E peek(){
    if (stack.isEmpty()) return null;
        return stack.get(stack.size()-1);
    }
}

---

Queue

Queue 또한 java에서 제공하는 class로
Queue로 생성하지만, 생성자는 LinkedList를 받는다.

기본 메서드

import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();

// 값 추가
queue.add(1);
queue.add(2);
queue.add(3);
// queue = [1,2,3]

//값 빼기
queue.poll();
// queue = [2, 3]
int t = queue.poll();
// queue = [3], t = 2

// 첫 번째 값 출력
queue.peek();
// 3

---

직접 구현

Queue또한 ArrayList를 이용해 Stack을 직접 구현이 가능하다.

class Queue<E> {
	private ArrayList<E> queue;
    public void Queue(){
    	this.queue = new ArrayList<E>();
    }
    public void add(E data){ stack.add(data); }
    public E poll(){
    	if (queue.isEmpty()) return null;
        return queue.remove(0);
    }
    public E peek(){
    if (queue.isEmpty()) return null;
        return queue.get(0);
    }
}