[자료구조] Stack, Queue

Benjamin·2022년 12월 7일

자료구조

목록 보기

4/9

스택과 큐는 배열에서 발전된 형태의 자료구조

Stack

스택(stack) = 쌓아 올린다는 것을 의미
스택 자료구조 = 차곡차곡 쌓아 올린 형태의 자료구조

특징

같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
top으로만 접근할 수 있다.
후입선출(LIFO, Last-In-First-Out) 구조
시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함

용어

top = 삽입, 삭제가 일어나는 위치
push = top위치에 새로운 데이터를 삽입하는 연산
pop = top위치에 현재 있는 데이터를 삭제하고 확인하는 연산
peek = top위치에 현재 있는 데이터를 단순 확인하는 연산
stack underflow = 비어있는 스택에서 원소를 추출하려고 할 때
stack overflow = 스택이 넘치는 경우

스택의 활용 예시

스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.

웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
그래프의 깊이 우선 탐색(DFS)에서 사용
재귀적(Recursion) 함수를 호출 할 때 사용

-> 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적이며, 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문이다.

스택의 후입선출이라는 독특한 성질이 종종 시간 복잡도를 줄이거나 특정한 문제의 조건을 손쉽게 해결하는 실마리가 될 떄가 있다.
문제에 접근할 때 혹시 스택을 이용하면 손쉽게 풀리지 않는지 한 번쯤 고민해보자!

java에서 사용법

자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다.

Stack 선언

import java.util.Stack; //import
Stack<Integer> stack = new Stack<>(); //int형 스택 선언
Stack<String> stack = new Stack<>(); //char형 스택 선언

Stack 값 추가

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가

Stack 값 삭제

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.pop();       // stack에 값 제거
stack.clear();     // stack의 전체 값 제거 (초기화)

스택에서 값을 제거하고싶다면 pop()이라는 메서드를 사용하면 됩니다.
pop을 하면 가장 위쪽에 있는 원소의 값이 아래 그림과 같이 제거됩니다.
스택의 값을 모두 제거하고싶다면 clear()라는 메서드를 사용하면 됩니다.

Stack의 가장 상단의 값 출력

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.peek();     // stack의 가장 상단의 값 출력

Stack의 기타 메서드

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)

참고
https://coding-factory.tistory.com/601

Queue

Queue 의 사전적 의미
1. (무엇을 기다리는 사람, 자동차 등의) 줄 , 혹은 줄을 서서 기다리는 것

특징

선입선출(FIFO, First in first out) 방식
한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
접근방법은 가장 첫 원소와 끝 원소로만 가능

용어

front = 큐에서 가장 앞의 데이터를 가리키는 영역
rear = 큐에서 가장 끝 데이터를 가리키는 영역
add = rear 부분에 새로운 데이터를 삽입하는 연산
poll = front 부분에 있는 데이터를 반환 후 삭제하는 연산
remove = front 부분에 있는 데이터를 반환 후 삭제하는 연산
peek = 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산
큐의 rear에서 이루어지는 삽입연산을 인큐(enQueue), front에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.
size() : 큐에 현재 있는 데이터의 개수(크기)

-> 꽉 찼을 때 : add = 예외 발생 / offer = false 리턴

큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
은행 업무
콜센터 고객 대기시간
프로세스 관리
너비 우선 탐색(BFS, Breadth-First Search) 구현
캐시(Cache) 구현

-> BFS에서 자주 사용!

구현

자바에서는 스택을 클래스로 구현하여 제공하지만 큐는 Queue인터페이스만 있고 별도의 클래스가 없다.
그래서 Queue인터페이스를 구현한 클래스들을 사용해야 한다

이 구조가 잘 이해가지 않는다면 디자인 패턴중 생성패턴을 공부해보길 바란다.

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

public class Main {

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<Integer>();

        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);

        while(!queue.isEmpty()) {
            System.out.println(queue.poll());
        }

    }

}

큐 인터페이스를 이용하면 간단하게 구현할수 있다. 하지만 큐를 만들줄도 알아야 한다.

배열을 이용해서 Queue 구현

queuelsEmpty() : 큐 안이 비었는지 판단하는 함수
queueIsFull() : 배열의 최대크기를 벗어나면 안되기에 큐에 더이상 들어갈 공간이 없는지 판단하는 함수
size() : queue에 현재 들어가 있는 데이터의 개수를 return하는 함수
push(int value) : 큐 안에 데이터를 집어넣는 함수
peek() : 큐 안의 데이터들중 가장 먼저 나오는 데이터를 return 하는 함수
pop() : 큐 안의 데이터들 중 가장 먼저 나올수 있는 데이터를 return 하고 삭제하는 함수

public class ArrayQueue {
    int MAX = 1000;
    int front;    //머리 쪽에 위치할 index값, pop할때 참조하는 index
    int rear;    //꼬리 쪽에 위치할 index값, push할때 참조하는 index
    int [] queue;
    public ArrayQueue() {
        front = rear = 0;    //초기값 0
        queue = new int[MAX]; //배열 생성
    }

    public boolean queueisEmpty() { //queue에 아무것도 들어있지 않은지 판단하는 함수
        return front == rear;
    }
    public boolean queueisFull() {    //queue가 가득 차 공간이 없는지 판단하는 함수
        if(rear == MAX-1) {
            return true;
        }else 
            return false;
    }
    public int size() { //queue에 현재 들어가 있는 데이터의 개수를 return
        return front-rear;
    }
    public void push(int value) {
        if(queueisFull()) {
            System.out.println("Queue is Full");
            return;
        }
        queue[rear++] = value; //rear가 위치한 곳에 값을 넣어주고 rear를 증가시킨다.
    }
    public int pop() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front++];
        return popValue;
    }
    public int peek() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front];
        return popValue;
    }
}

배열로 구현한 Queue는 push pop이 간단하지만 배열의 크기가 유한해 큐의 크기가 다 차버리면 사용할수 없다.
그러면 LinkedList로 Queue를 구현해야 한다.

LinkedList을 이용해서 Queue 구현

Node를 이용해서 Queue를 구현한다. 값이 들어갈 Node와 Queue를 관리할 NodeManager 클래스를 만들면 된다.

public class QueueNode {
    int value; //값을 넣음
    QueueNode queueNode; //다음 노드를 가리킴
    public QueueNode(int value) {
        this.value = value;
        queueNode = null;
    }
    public int getValue() {
        return value;
    }
    public QueueNode getNextNode() {
        return queueNode;
    }
    public void setNextNode(QueueNode queueNode) {
        this.queueNode = queueNode;
    }
}

public class QueueNodeManager{ //큐의 기능을 만들 클래스
    QueueNode front,rear;
    public QueueNodeManager() {
        front = rear = null;
    }
    public boolean queueisEmpty() {
        if(front == null  && rear == null) {
            return true;
        }else {
            return false;
        }
    }
    public void push(int value) {
        QueueNode queueNode = new QueueNode(value);
        if(queueisEmpty()) {    //큐안에 데이터가 없으면 첫번째 Node에 front와 rear를 연결
            front = rear = queueNode;
        }else {
            rear.setNextNode(queueNode); //큐 안에 데이터가 있으면 rear를 다음 노드에 연결 후 rear의 값을 마지막 노드로 삽입
            rear = queueNode;
        }
    }
    public QueueNode pop() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return null;
        }else {
            QueueNode popNode = front;
            front = front.getNextNode();
            return popNode;
        }
    }
    public QueueNode peek() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return null;
        }else {
            return front;
        }
    }
    public int size() {
        QueueNode front2 = front;
        QueueNode rear2 = rear;
        int count = 0;
        while(front2 != rear2 && rear2 !=null) { //큐가 비어있는 경우가 있을수도 있을때도 생각해야함
            count++;
            rear2 = rear2.getNextNode();
        }
        return count;
    }
}

LinkedList로 Queue를 만들게 되면 규현은 복잡하지만 큐의 크기도 무한하고 Queue안에 원하는 기능을 넣을수도 있다는 장점이 있다.