본문 바로가기
카테고리 없음

[JAVA] Stack(스택)과 Queue(큐)

by 잉ㅈI 2024. 2. 4.

알고리즘을 요즘 풀고있는데 스택과 큐에 대한 정리를 하면 좋을것 같은 생각이 ㅠㅠ ...!!

각각 어떤 메서드가 있는지 알아보고 

열심히 써보도록하자 (´ヮ`)

 

0. Stack과 Queue 구조

좌) stack 우) queue

 

1)Stack(스택)

일명 박스쌓기!  선입후출(FILO) 구조 또는 후입선출(LIFO)구조라고 한다!

FILO == First In Last Out

2)Queue(큐)

일명 대기줄!이라고 할수있다. 선입선출(FIFO)구조라고한다. (공정하죠?^,^)

FIFO == First In First Out

 

 

1.Stack 메서드

  • boolean isEmpty() / empty()
    • Stack이 비어있으면 True,
    • Stack이 비어있지않으면 False
  • Object peek()
    • Stack의 맨 위 저장된 객체 반환
    • pop() 과 다른점: 객체를 꺼내지 않음 => 즉, 그냥 반환만 함! 나오지않음
    • 비어있을 경우 : EmptyStackException 발생
  • Object pop()
    • Stack의 맨위 저장된 객체 꺼냄
    • 비어있을 경우 : EmptyStackException 발생 // isEmpty() == true 일때 예외처리하기
  • Object Push(Object item)
    • Stack에 item(객체)를 저장함
  • int Search(Object o)
    • Stack에서 주어진 객체를 찾아서 그위치 반환
    • 못찾을 시 -1 반환
    • 위치 1부터 시작(인덱스처럼 0 아님 주의)
  • int Size()
    • Stack의 사이즈 반환

2. Queue 메서드

  • boolean offer(Object o)
    • Queue에 객체 저장함
    • 성공하면 true, 실패시 false 반환
  • Object poll()
    • Queue에 객체꺼내서 반환
    • 비어있으면 null 반환
  • boolean add(Object o)
    • Queue에 객체 저장
    • 성공시 true 반환
    • 저장공간 부족시 illegalStateException 발생
  • Object remove()
    • Queue에서 객체 꺼내 반환
    • 비어있으면 NoSuchElementException 발생
  • Object element()
    • 삭제없이 요소 읽기 + 리스트에서 요소를 제거하지 않고 가져오는 메서드
    • Queue 비어있으면 NoSuchElementException 발생
  • Object peek() -> 둘 다 가능!
    • 삭제없이 요소 읽기 + 리스트에서 요소를 제거하지 않고 가져오는 메서드
    • Queue 비어있으면 null 반환 : element()와 다른점
  • Object peekLast(), peekFirst()
    • 삭제없이 요소 읽기 + 리스트에서 요소를 제거하지 않고 가져오는 메서드
    • Dequeue 메서드이지만 구현체인 LinkedList에서 같이 사용가능
    • peekLast(): 리스트의 마지막 요소 가져옴, peekFirst(): 리스트의 첫번째 요소 가져옴
  • int Size()
    • Queue의 사이즈 반환

3. Stack 구현

1) 선언

Stack<Integer> s = new Stack<>();

 

2) 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();

 

3)출력

스택의 최상단 원소부터 출력해보자!

* peek()로 꺼내진 않고 반환하기 -> 이후 pop()하기

이때 stack을 비우지 않는다면 while에 걸려 무한루프가 돌아용

while (!s.empty()){
            System.out.println(s.peek()); 
            s.pop(); 
        }

 

*아예 pop()하면서 출력시키기

while (!s.empty()){
            System.out.println(s.pop()); //1 3 2 5 (/n 생략)
        }

 

 

4. Queue 구현

1)선언

Queue 인터페이스 구현체인 LinkedList 사용 => 둘다 사용가능하다~

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

 

2) 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

q.offer(5);
q.offer(2);
q.offer(3);
q.offer(7);
q.poll();
q.offer(1);
q.offer(4);
q.poll();

 

3)출력 

먼저 들어온 순서대로 출력하기

isEmpty()로 비어있는지 확인 후 poll()하면서 출력

while (!q.isEmpty()){
            System.out.println(q.poll()); //3 7 1 4 (/n생략)
        }

 

Stack은 empty()로 원소 비어있는지 확인
Queue는 isEmpty()로 원소 비어있는지 확인하기 // 둘다가능함 ㅋ

티스토리툴바