Stack(스택)과 Queue(큐)란?

Data Structure(자료구조)

Stack(스택)과 Queue(큐)란?

Somaz 2022. 8. 22. 13:24

728x90

Overview

오늘은 Stack(스택)과 Queue(큐)에 대해서 공부해보려고 한다.

Stack(스택)이란?

Stack(스택)은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아올린 형태의 자료구조입니다.

아래의 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있습니다.

또한 Stack은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있습니다.

새로 삽입되는 자료는 top이 가리키는 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능합니다.

그리고 스택에서는 삽입 연산을 push, 삭제 연산을 pop이라고 하며, 이러한 스택의 구조를 후입 선출의 구조라고 하며, 줄여서 LIFO(Last In First Out)라고 부릅니다.

Stack(스택)의 TOP & BOTTOM

TOP/BOTTOM은 스택의 특정위치를 가리킵니다.
TOP는 가장 최근에 스택에 저장된 값, BOTTOM은 가장 처음 스택에 저장된 값을 가리킵니다.

BOTTOM의 위치는 항상 스택 가장 아랫값을 가리키고 있기 때문에 고정됩니다.

하지만 TOP의 위치는 데이터가 추가되거나, 데이터가 제거될 때 마다 달라집니다.

Stack(스택)의 사용 사례

웹 브라우저 방문기록 (뒤로 가기)
실행 취소(undo)
역수 문자열 만들기
후위 표기법 계산

Stack(스택)의 구현

프로그래밍 문제의 종류에 따라 적합한 방법을 찾아 코딩합니다.

따라서 어떠한 문제냐에 따라 배열에 저장하는 것보다, 스택을 사용하여 적장하는 것이 적합한 방법일 수 있습니다.

Stack은 배열, 연결리스트로 구현할 수 있습니다.

# 연결 리스트로 사용할 노드 Class

public class Node {

        private Object data;
        private Node nextNode;
        
        public Node(Object data){
        		this.data = data;
                this.nextNode = null;
        }
        
        # 해당 노드를 원하는 노드(Node top)와 연결해주는 메소드
        public void linkNode(Node top){
        		this.nextNode = top;
        }
        
        # 해당 노드의 데이터를 가져오는 get메소드
        public Object getData(){
        		return this.data;
        }
        
        # 해당 노드와 연결된 노드를 가져오는 get메소드
        public Node getNextNode(){
        		return this.nextNode;
        }
}

연결리스트는 노드로 구성되어 있으며 노드는 데이터와 다음 노드를 가르키는 주소로 구성되어 있습니다.

Node Class의 코드를 보면 property로 data와 nextNode가 있습니다. linkNode(Node top) 메서드를 통해 자신의 nextNode property에 인자로 받은 top 노드를 주입합니다. 이로써 자신과 top 노드를 연결합니다.

아래는 연결리스트로 구현된 스택입니다.

public class ListStack {

    private Node top;
    
    public ListStack(){
    	top = null;
    }
    
    public boolean isEmpty(){
    	return (top==null);
    }
    
    public void push(Object item){
    	Node newNode = new Node(item);
        newNoe.linkNode(top);
        top = newNode;
    }
    
    public Object peek(){
    	return top.getData();
    }
    
    public Object pop(){
    	if(isEmpty()) throw new ArrayIndexOutOFBoundsException();
        else{
            Object item = peek();
            top = top.getNextNode();
            return item;
        }
    }
}

push(Object item) 메서드에서 새로운 노드를 생성합니다. Node newNode = new Node(item);
만들어진 노드를 linkNode(Node top) 메서드를 활용해 만들어진 노드와 기존에 노드랑 연결해줍니다. newNode.linkNode(top);
마지막으로 새로운 노드가 가장 앞에 있으니 top으로 표시를 해줍니다. newNode.linkNode(top);

pop()은 지울 데이터를 반환하고 top의 위치를 이전 노드로 표시해줍니다. top = top.getNextNode():

public class main {
        public static void main(String[] args) {
        
        ListStack stackL = new ListStack();
                
                stackL.push(5);
                stackL.push("Hi");
                stackL.push("again");
                stackL.push("Monsieur Songsong");
                
                while(!stackL.isEmpty()){
                		System.out.println(stackL.pop());
                }
         }
{

배열, 연결리스트 각각의 장단점이 있습니다. 배열은 데이터 양이 많지만 삽입/삭제가 거의 없고, 데이터의 접근이 빈번히 이뤄질 때 유리합니다. 반대로 연결리스트는 삽입/삭제가 빈번히 이뤄지고, 데이터의 접근이 거의 없을 때 유리합니다.

Queue(큐)란?

Queue는 Stack과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로, FIFO(Firts IN First Out)의 구조를 가지고 있습니다.

Queue(큐)는 Stack(스택)과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로 FIFO(First In First Out)의 구조를 가지고 있습니다.

삭제 연산이 수행되는 곳을 Front(프론트), 삽입 연산이 이루어지는 곳은 rear(리어)로 FIFO 구조를 위해서 스택과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있습니다.

큐는 rear(리어)에서 이루어지는 삽입 연산을 Enqueue(인큐)라고 부르며, Front(프론트)에서 이루어지는 삭제 연산을 Dequeue(디큐)라고 부릅니다.

Queue(큐)의 주요 동작들

enQueue(): 큐에 데이터를 넣는다.
deQueue(): 큐에 데이터를 빼낸다.
isEmpty(): 큐가 비어있는지 확인한다.
isFull(): 큐가 꽉 차 있는지 확인한다.
peek(): 앞에있는 원소를 삭제하지 않고 반환다.

Queue(큐)의 사용 사례

은행 업무
대기열 순서와 같은 우선순위의 작업 예약 등
서비스 센터의 대기시간
프로세스 관리

Queue(큐)의 문제점

Queue(큐)를 구현하고 사용할 때 Queue에서 데이터를 빼내는 deQueue()함수를 쓰게되면 맨 앞에 있던 값이 빠져나가게 됩니다.

이 때 front가 한칸씩 뒤로 밀려나게 되면서 큐의 가용범위가 줄어들고, 큐의 재사용 또한 불가능하게 됩니다.

만약에, 억지로 큐의 재사용을 하기위해서 front를 출력하고 front뒤의 인덱스를 하나씩 앞당긴다고 하더라도 불필요한 연산이 너무 많아집니다.

Queue(큐)의 다른 형식

원형 큐 (Circle Queue)

위와 같은 큐의 문제점을 보완하기 위해서 "원형 큐(Circle Queue)"를 사용합니다.

우선순위 큐 (Priority Queue)

우선순위를 이용하여 우선순위가 높은 순서대로 나가게 된다.

쉽게 말해, 병원에서 기존 환자들을 진료보다가 응급환자가 오게되면 먼저 진료하게된다고 이해하면 된다.

Queue(큐)의 기본문법

선언

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

추가

Queue<Integer> stack = new LinkedList<>(); //int형 queue 선언
queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.offer(3);   // queue에 값 3 추가

삭제

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값 제거
queue.clear();      // queue 초기화

조회

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.peek();       // queue의 첫번째 값 참조

728x90

현재글Stack(스택)과 Queue(큐)란?

Somaz의 IT 공부 일지