[자료구조] Stack과 Queue 개념 정리

김동욱·2023년 3월 16일
0

Data Structure

목록 보기
1/1

스택(Stack)이란?

스택(Stack)은 데이터를 임시로 저장하기 위한 자료구조 중 하나이며, 마지막으로 삽입된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last-In-First-Out) 구조를 가지고 있다.
마치 상자에 책을 쌓아서 넣고 빼는 형식과 같다.

스택 기본 연산

  • Object Push(): 데이터를 삽입
  • Object Pop(): 데이터를 삭제
  • Object Peek(): 가장 위에 있는 데이터를 반환하여 확인하는 함수
  • boolean empty() : 비어있는지 확인
  • int search(Object obj): 주어진 객체(obj)를 찾아서 그 위치를 반환, 못 찾으면 -1을 반환한다. 배열과 달리 0이 아닌 1부터 시작한다

스택 시간 복잡도

접근검색삽입삭제
O(n)O(n)O(1)O(1)

스택의 활용

수식계산, 수식괄호검사, 함수 콜 스택, 인터럽트 처리
워드프로세서의 undo/redo, 뒤로가기/앞으로가기 : 스택2개사용하거나 포인터 사용

자바에서 스택 구현 방법

1.클래스 사용

 public class Stack {
  public static void main(String[] args) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    System.out.println(stack.pop()); 
    System.out.println(stack.peek()); 
    
  }
}

2.배열 사용 (스택에 효율적)
0 1 2 3 4 로 저장하면 마지막 데이터인 4부터 삭제하게 되니 배열 이동이 필요 없다

class MyStack {
    ArrayList list;

    MyStack() {this.list = new ArrayList();}

    public boolean isEmpty() {
        if (this.list.size()==0) {
            return true;
        }
        return false;
    }
		
//Push() 구현
    public void push(int data) {
        this.list.add(data);
    }
//pop() 구현
    public Integer pop() {
        if (this.isEmpty()) {
            System.out.println("Stack is empty");
            return  null;
        }
        int data = (int) this.list.get(this.list.size()-1);
        this.list.remove(this.list.size()-1);
        return data;
    }
//peek()구현
    public Integer peek() {
        if (this.isEmpty()) {
            System.out.println("Stack is empty");
            return null;
        }
        int data = (int) this.list.get(this.list.size()-1);
        return data;

    }
//스택 출력
    public void printStack() {
        System.out.println(this.list);
    }
}

3. 연결 리스트 (큐에 효율적)
0 1 2 3 4로 저장하면 0번부터 삭제하게 되니 만약 배열이라면 0을 삭제 후 뒷 데이터들을 앞으로 이동시켜줘야한다. 하지만 연결 리스트는 연결만 바꿔주면 되기 때문에 편하다.

큐(Queue)

FIFO(First In First Out) 먼저 들어온 데이터가 먼저 나가게 되는 것

큐의 활용

최근 사용문서 : 최근 사용문서를 보여줌, 새로운 문서를 열면 가장 오래된 문서를 기록에서 지운다.

프린터 대기목록, 버퍼(buffer), BFS(Breath-First Search)

큐의 기본연산

예외발생X

  • boolean offer(Object obj): 객체를 저장, 성공하면 true, 실패하면 false를 반환한다.
  • Object Poll(): 객체를 꺼내서 반환, 비어있으면 null을 반환한다.
  • Object peek(): 삭제없이 요소를 읽음. 비어있으면 null 반환

예외발생O

  • boolean add(Object obj): 지정된 객체를 큐에 추가한다. 성공하면 true, 저장공간이 부족하면 IllegalStateException 발생
  • Object remove(): 큐에서 객체를 꺼내 반환. 비어있으면 NoSuchElementExceoption 발생 (예외발생 O)
  • Object element(): 삭제없이 요소를 읽어옴. peek()과 달리 큐가 비었을 때 NoSuchElementException 발생

큐의 시간복잡도

접근검색삽입삭제
O(n)O(n)O(1)O(1)

Queue 사용방법

Stack은 클래스라서 객체 생성이 가능하다. 하지만 Queue는 인터페이스 구성이라 객체 생성이 불가능하다.
(⇒ Queue q = new Queue(); 객체 생성 불가)

Queue를 구현한 클래스는 인터페이스 Queue의 추상 메소드를 모두 사용할 수 있기 때문에 이를 찾아서 사용한다.
ex) LinkedList, ArrayDeque
Queue q = new LinkedList();
Queue q = new ArrayDeque();

profile
안녕하세요. 공부해요

0개의 댓글