[Section2]

[Section] 자료구조(Stack, Queue)

Min_dev 2022. 7. 25. 22:37
반응형

자료구조란?

 

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

 

데이터는 문자, 소리, 숫자, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다.

그런데 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다.

예를 들어 이름이라는 데이터만 알고 있다면, 나의 이름인지, 친구의 이름인지, 부모님의 이름인지 알 수 없기 때문이다.

이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

 

이러한 데이터들을 여러 상황에 맞게 효울적으로 다룰 수 있도록 만든 방법론이 자료구조다.

 

여러 상황의 예시

  • 번호를 다 알지 않아도, 이름을 아는 것만으로 전화를 할 수 있는 방법은 무엇이 있을까?
  • 웹 브라우저에서 뒤로 / 앞으로 가는 방법은 무엇이 있을까?
  • 상담 전화가 오면 먼저온 전화 순서로 상담원에게 분배하려면 어떻게 해야할까?

 

오늘은 수많은 자료구조 가운데에서 Stack과 Queue에 대해서 알아보자!

 

학습목표

- Stack과 Queue의 특징
- 어떤 상황에 어떤 자료구조를 써야할지?
- 자료구조 내부 구현해보기
- 동작원리 이해하기

 

Stack

 

Stack은 데이터를 순서대로 쌓는 자료구조이다.

 

실생활에서 Stack의 예를 찾아보자면, 우리가 간식으로 먹는 핫케잌을 생각하면된다.

핫케잌을 접시에 놓을때는 밑에서부터 1단, 2단, 3단 순서대로 쌓지만 핫케잌을 먹을때는 맨 위에 놓여있는 3단부터 케잌을 먹는다.

 

Stack도 이와 같다.

데이터가 추가 될 때는 밑에서부터 순서대로 쌓이게 되고

데이터를 빼낼때에는 나중에 추가된 데이터가 먼저 나가게 된다.

 

Stack의 특징

1. 입 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.
2. LIFO (Last In First Out) 후입선출의 구조로 이루어져 있다.
3. 데이터는 하나씩 넣고 뺄 수 있다.

 

다음 예시 코드는 LIFO 구조를 잘 보여주고 있다.

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);

        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }
}

//출력값
[1, 2, 3, 4]
4
3
2
1

 

Stack의 실사용 예제는 우리가 자주 사용하는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 활용된다.

 

  1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다..
     
  2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져한다..
     
  3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져혼다.
     
  4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.

 

 

 

Queue

 

큐(Queue)는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다.

예를 들어 설명하면 고속도로의 톨게이트에 진입한 순서대로 통행료를 내고 톨게이트를 통과하는 개념이라고 보면된다.

가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 통과하고, 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다.

 

Queue 특징

1. Queue의 데이터 구조는 FIFO(First In First Out) 구조를 가지고 있다., (선입선출)

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

public class QueueEx {
    public static void main(String[] args) {

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

        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);

        System.out.println(queue);

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}

//출력 결과
[1, 2, 3, 4]
1
2
3
4

위 코드를 보면 데이터를 빼낼 때 먼저 들어간 순서인 1, 2, 3, 4 순서로 데이터가 빠지는걸 볼 수 있다.

 

2. 데이터를 하나씩 넣고 뺄 수 있다.

Queue 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺀다. 한꺼번에 여러개를 넣거나 뺄 수 없다.

 

3. 두 개의 입출력 방향을 가지고 있다.

Queue 자료구조는 데이터의 입력, 출력 방향이 다르다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없다.

반응형
저작자표시