java/ 자료구조 : 스택Stack과 큐Queue

자료구조

다양한 자료를 효율적으로 표현하고 저장하여 처리할 수 있도록 하는 것

 

컴퓨터가 자료를 효율적으로 처리하게 하기 위해서,

문제를 자료구조 측면에서 분석하고 구성해 더 좋은 프로그램을 만들려는 노력이 필요하다!

 

문제를 정의하고,
처리 방식을 결정해 알고리즘을 작성하고,
처리 대상을 결정해 자료를 정의해
프로그램을 작성한다

 

---

컬렉션과 스택, 큐

스택은 컬렉션 인터페이스를 상속받는  List 인터페이스를 구현하는 Vector 클래스를 상속받는다.

큐는 컬렉션 인터페이스를 상속받는다.

 

따라서 스택을 사용할 때 Vector 클래스의 메서드를 사용할 수 있고, 큐를 사용할 때 컬렉션 인터페이스의 메서드를 사용 가능하다.

 

 

---

Stack

"쌓아 올리다" → 자료를 차곡차곡 쌓아 올리는 자료구조

그림과 같이 push 연산을 수행하면 자료가 차곡차곡 쌓이게 되고, pop 연산을 수행하면 맨 위에 있는 요소만을 꺼내올 수 있다.

• 나중에 들어간 요소가 가장 먼저 나온다 → Last In First Out(LIFO)
• 입력과 출력은 단방향으로 이뤄진다
• 데이터는 하나씩 넣고 뺄 수 있다 (한번에 여러 개의 연산은 불가능하다)

 

Stack 선언

기본형

Stack<E> stack = new Stack<E>();

e.g.

Stack<String> stack = new Stack<>();

 

Stack에 자료를 추가하기

push(): 스택의 맨 위에 자료를 하나 추가한다

stack.push("java");
stack.push("stack");
stack.push("ds");

 

Stack에서 자료를 검색하기(접근하기)

peek(): 스택의 맨 위 요소를 반환한다. 검색된 요소는 삭제되지 않는다.

stack.peek(); //ds

//stack : [java, stack, ds]

 

Stack에서 자료를 삭제하기

pop() : 스택의 마지막 요소를 스택에서 삭제하고, 삭제한 요소를 반환한다

stack.pop(); //ds

//stack : ["java", "stack"]

clear(): 스택의 전체 요소를 삭제한다. (Vector 메서드)

stack.clear();

 

Stack이 비었는지 확인하기

empty(): stack이 비었으면 true, 아니면 false를 반환한다.

stack.empty(); //true

 

---

Queue

"줄을 서서 기다리다", "대기 행렬" → 자료를 한 줄로 저장하는 자료구조

그림과 같이 add 연산을 수행하면 자료가 한 줄로 한개씩 들어가게 되고 , poll 연산을 수행하면 맨 앞에 있는 요소만을 꺼내올 수 있다.

• 먼저 들어간 요소가 가장 먼저 나온다 → Frirst In First Out(FIFO)
• 입력과 출력의 방향은 다르다 →  두개의 입출력 방향을 갖는다
• 데이터는 하나씩 넣고 뺄 수 있다 (한번에 여러 개의 연산은 불가능하다)

 

Queue 선언

큐는 인터페이스이므로 Stack과 달리 Queue 유형의 객체를 생성하는 것은 불가능하다. 따라서, 객체를 생성하기 위해서 Queue 인터페이스를 구현하는 클래스가 필요하다.

 

e.g.

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

 

Queue에 자료를 추가하기

push(): 스택의 맨 위에 자료를 하나 추가한다

queue.add("java");
queue.add("queue");
queue.add("ds");

 

Queue에서 자료를 검색하기(접근하기)

peek(): 큐의 맨 앞 요소를 반환한다. 검색된 요소는 삭제되지 않는다.

queue.peek(); //java

//queue : [java, queue, ds]

 

Queue에서 자료를 삭제하기

pop() : 큐의 처음 요소를 삭제하고, 삭제한 요소를 반환한다

queue.poll(); //java

//queue : ["queue", "ds"]

remove(element) :

queue.remove("queue");

//queue : [ds]

clear() : 큐의 전체 요소를 삭제한다.

queue.clear();

 

Queue가 비었는지 확인하기

isEmpty(): 큐가 비었으면 true, 아니면 false를 반환한다.

queue.isEmpty(); //true

 

---

ref.

Stack Class in Java - GeeksforGeeks

Queue Interface In Java - GeeksforGeeks