스택(Stack)과 큐(Queue) 개념 및 Java 코드 구현

본 포스팅은 jisikTank 스터디에 참여하며 정리한 문서입니다.
jisikTank CS지식 Git Repository

---

스택과 큐(Stack & Queue)

스택(Stack)

• 입력과 출력이 한 곳(방향)으로 제한
• LIFO(Last In First Out, 후입선출): 가장 나중에 들어온 것이 가장 먼저 나옴

언제 사용할까?

• 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법 등

Stack의 특징

• 자주 사용하는 메소드로 push, pop, isEmpty, isFull 이 있다.
• push, pop 과정에 다음 값이 들어갈 최상단 위치를 기억하는 스택 포인터(SP)가 필요(처음 기본값 -1)
• 기본적으로 크기가 정적으로 구성되지만 연결리스트, 동적 배열을 활용해 최대 크기가 존재하지 않도록 구현할 수 있다.
• 시간복잡도 삽입 O(1), 삭제 O(1), 탐색 O(n)

java 코드로 스택 살펴보기

public class BasicStack {

    static int MAX_SIZE = 1000;
    static Object stack[];

    class Stack{
        private int sp = -1;

        public void push(Object o) {
            if(isFull(o)) {
                return;
            }

            stack[++sp] = o;
        }

        public void pushDynamicArrayStack(Object o) {

            if(isFull(sp)) {

                Object[] arr = new Object[MAX_SIZE * 2];
                System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
                stack = arr;
                MAX_SIZE *= 2; // 2배로 증가
            }

            stack[sp++] = o;
        }

        public Object pop() {

            if(isEmpty(sp)) {
                return null;
            }

            Object o = stack[sp--];
            return o;

        }

        private boolean isFull(Object o) {
            return sp + 1 == MAX_SIZE ? true : false;
        }

        private boolean isEmpty(int cnt) {
            return sp == -1 ? true : false;
        }
    }



    public static void main(String args[]){

    }


}

동적 크기 스택(Array형태로 구현)

public class DynamicArrayStack {

    static int MAX_SIZE = 1000;
    static Object stack[];

    class Stack{
        private int sp = -1;

        // 일반 스택과 push method만 차이가 있음
        public void push(Object o) {
            if(isFull(sp)) {

                Object[] arr = new Object[MAX_SIZE * 2];
                System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
                stack = arr;
                MAX_SIZE *= 2; // 2배로 증가
            }
            stack[sp++] = o;
        }

        public Object pop() {

            if(isEmpty(sp)) {
                return null;
            }

            Object o = stack[sp--];
            return o;

        }

        private boolean isFull(Object o) {
            return sp + 1 == MAX_SIZE ? true : false;
        }

        private boolean isEmpty(int cnt) {
            return sp == -1 ? true : false;
        }
    }
}

동적 크기 스택(LinkedList로 구현)

public class DynamicLinkedListStack {

    public class Node {

        public int data;
        public Node next;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    public class Stack {
        private Node head;
        private Node top;

        public Stack() {
            head = top = null;
        }

        private Node createNode(int data) {
            return new Node(data);
        }

        private boolean isEmpty() {
            return top == null ? true : false;
        }

        public void push(int data) {
            if (isEmpty()) { // 스택이 비어있다면
                head = createNode(data);
                top = head;
            }
            else { //스택이 비어있지 않다면 마지막 위치를 찾아 새 노드를 연결시킨다.
                Node pointer = head;

                while (pointer.next != null)
                    pointer = pointer.next;

                pointer.next = createNode(data);
                top = pointer.next;
            }
        }

        public int pop() {
            int popData;
            if (!isEmpty()) { // 스택이 비어있지 않다면!! => 데이터가 있다면!!
                popData = top.data; // pop될 데이터를 미리 받아놓는다.
                Node pointer = head; // 현재 위치를 확인할 임시 노드 포인터

                if (head == top) // 데이터가 하나라면
                    head = top = null;
                else { // 데이터가 2개 이상이라면
                    while (pointer.next != top) // top을 가리키는 노드를 찾는다.
                        pointer = pointer.next;

                    pointer.next = null; // 마지막 노드의 연결을 끊는다.
                    top = pointer; // top을 이동시킨다.
                }
                return popData;
            }
            return -1; // -1은 데이터가 없다는 의미로 지정해둠.

        }

    }


    public static void main(String[] args) {

    }

}

큐(Queue)

• 입력과 출력을 한 쪽 끝(front, rear)로 제한
• FIFO(First In First Out, 선입선출): 가장 먼저 들어온 것이 가장 먼저 나옴

언제 사용할까?

• 버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황, BFS

Queue의 특징

• 큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부름

• 접근은 가장 첫 원소와 끝 원소로만 가능

• 자주 사용하는 메소드로 enQueue, deQueue, isEmpty, isFull이 있음

• 시간복잡도 삽입 O(1), 삭제 O(1), 탐색 O(n)

• 일반 큐(선형)는 빈 메모리가 남아 있어도, 꽉 차있는 것으로 판단할 수 있음(rear가 끝에 도달했을 때) -> 원형 큐

원형 큐

• 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함
• 초기 공백 상태일 때 front와 rear가 0
• 공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둠

(index + 1) % size로 순환시킨다

java 코드로 큐 알아보기




일반 정적 크기 큐 코드

public class BasicQueue {

    class Queue{
        private int size = 0; 
        private int rear = -1; 
        private int front = -1;

        private Object queue[];

        Queue(int size) { 
            this.size = size;
            this.queue = new Object[size];
        }

        public boolean isEmpty() {
            return front == rear;
        }

        public boolean isFull() {
            return (rear == size-1);
        }

        public void enQueue(Object o) {

            if(isFull()) {
                return;
            }

            queue[++rear] = o;
        }

        public Object deQueue() {

            if(isEmpty()) { 
                return null;
            }

            Object o = queue[front];
            queue[front++] = null;
            return o;
        }
    }
}

java 원형 큐 코드

public class Circular {
    public class Circular_Queue {

        int rear = 0;            //최초 0에서부터 시작
        int front = 0;            //최초 0에서부터 시작
        int maxsize = 0;        //배열의 크기
        int[] circular_Queue;          //배열

        public Circular_Queue(int maxsize)
        {
            this.maxsize = maxsize;
            circular_Queue = new int[this.maxsize];
        }

        public boolean Isempty()    //배열이 공백 상태인지 체크하는 메서드입니다.
        {
            if(rear == front)
            {
                return true;
            }
            return false;
        }
        public boolean Isfull()        //배열이 포화 상태인지 체크하는 메서드입니다.
        {
            if((rear+1)%maxsize == front)
            {
                return true;
            }
            return false;
        }

        public void EnQueue(int num)
        {
            if(Isfull())            //배열이 포화상태일경우
            {
                System.out.println("큐가 가득 찼습니다");
            }
            else                //배열이 포화상태가 아닐경우
            {
                rear = (rear+1) % maxsize;
                circular_Queue[rear]=num;
            }
        }

    public int DeQueue()
        {
            if(Isempty())         //배열이 공백상태이면 -1반환
            {
                return -1;
            }
            else                 //배열이 공백상태가 아니라면
            {
                front = (front+1)%maxsize;
                return circular_Queue[front];
            }
        }
    }
    public static void main(String[] args) {

    }

}

Quiz

• 기본적인 스택과 큐를 구현해보세요.
• Stack과 Queue의 차이점은 무엇인가요?(N사 전화면접)
  https://devowen.com/285

참고 자료

• https://github.com/gyoogle/tech-interview-for-developer

Quiz 모범 답안

https://devowen.com/285