Stack과 Queue

2개의 stack으로 queue를 구현하는 알고리즘을 풀면서 정리한 Stack과 Queue 개념

 

stack은 먼저들어온 것이 나중에 나간다(LIFO) 
→ 나중에 들어온 것이 먼저 나간다. 
ex. 3, 4, 5 의 요소를 순서대로 push했을 때, 
아래서부터 3, 4, 5 이렇게 stack 에 쌓이고, 
pop을 3번 했을 때 위에 있는 요소가 먼저 나오기 때문에 
5, 4, 3 이렇게 요소가 순서대로 없어진다. 

queue는 먼저들어온 것이 먼저 나간다(FIFO) 
→ 나중에 들어온 것이 나중에 나간다. 
3, 4, 5 가 아래서부터 순서대로 쌓여 있을 때 
pop을 하면 먼저 들어온 것부터(3) 나오기 때문에 
3, 4, 5 가 순서대로 없어진다.

stack과 queue는 push 했을 때 차이가 없지만 
pop을 했을 때는 차이가 발생한다. 
stack은 나중에 들어온 것이 먼저 나가고(LIFO) 
queue는 먼저 들어온 것이 먼저 나가는 구조다(FIFO) 
ex. 스택은(stack, 쌓여있다의 의미) 책이 책상 위에 쌓여 있는 구조,
제일 아래에 있는 책을 꺼내는 것보다 제일 위에 있는 책을 꺼내는 느낌,
큐는 줄을 서는 개념, 줄을 먼저 서 있는 사람이 먼저 기회를 얻는 개념이다. 

---

실습 
두 개의 스택을 사용해서 큐를 구현하기 
--> 두 개의 스택으로 입력(push)과 출력(pop, peek)을 분리하여 구현하기 
push할 경우 stack1에 저장한다. peek, pop할 경우 stack2에서 꺼내는데, 
stack2가 비어 있으면 stack1에서 모두 옮겨 담는다. 
빈 상태는 두 스택 모두 비었는지 확인한다. 
push의 경우 stack1에 그냥 넣는다. 

 

부분 풀이

public class MyQueue { 
    /*  Integer 타입의 데이터만 저장할 수 있는 제네릭 스택 
        MyQueue 클래스의 인스턴스 변수(필드) 
        private 접근 제한자 → 해당 클래스(MyQueue) 내부에서만 접근이 가능하다. 
        외부 클래스, 외부 메서드, 서브 클래스에서는 직접 접근이 불가하다. 
        private final Stack<Integer> stackIn; 
        private Stack<Integer> stackIn; 
        final 유무의 차이, 
        private 접근 제한자로 인해 접근 권한은 동일(클래스 내부에서만 접근 가능) 
        final이 붙은 변수에는 다른 Stack 객체를 재할당할 수 없다. 
        --> 클래스 내부에서는 언제든지 다른 Stack 객체로 재할당 할 수 없다. 
    */ 

    private Stack<Integer> stackIn; 
    private Stack<Integer> stackOut; 

    public int push(int x) { 
        stackIn.push(x); 
    } 

    public void peek() { 
        if(stackOut.isEmpty()) { // push가 이루어졌다면 stackIn에는 데이터가 있는 상태, stackOut에 데이터가 비어 있다면, 
            while(!stackIn.isEmpty()) { // stackIn이 비어있지 않을 때까지 
                // → stackIn에 데이터가 비어있다면 반복문(while)을 빠져 나간다. 
                // → stackIn에 데이터가 남아있는 동안 블록문 안의 코드를 반복한다. 
                stackOut.push(stackIn.pop()); 
            } 
        } 
        return stackOut.peek(); 
    } 

    public void pop() { 
        if(stackOut.isEmpty()) { // push가 이루어졌다면 stackIn에는 데이터가 있는 상태, stackOut에 데이터가 비어 있다면, 
            while(!stackIn.isEmpty()) { // stackIn이 비어있지 않을 때까지 
                // → stackIn에 데이터가 비어있다면 반복문(while)을 빠져 나간다. 
                // → stackIn에 데이터가 남아있는 동안 블록문 안의 코드를 반복한다. 
                stackOut.push(stackIn.pop()); 
            } 
        } 
        return stackOut.pop(); 
    } 
}

pop은 항상 stackOut에서 데이터를 꺼낸다. 
단, stackOut이 비어 있으면 stackIn의 모든 요소를 이동시켜서 순서를 뒤집는다. 
이동이 끝나면 outStack은 한 번 다 비워질 때까지 계속 사용된다. 

 

전체풀이

package algo2025.august;

import java.util.Stack;

/*
    stack 2개 사용해서 선입선출(FIFO) 큐를 구현
    큐 클래스가 갖는 기능: push, peek, pop, empty
     - void push(int x): 요소 x가 큐의 맨 뒤에 추가
     - int pop(): 큐의 앞쪽에서 요소를 제거하고 반환
     - int peek(): 큐의 앞에 있는 요소를 반환
     - boolean empty()
        - true: 대기열이 비어 있으면 true 를 반환
        - false: 대기열이 비어 있지 않으면 false 를 반환




*/
class MyQueue {
    // private final Stack<Integer> stackIn;
    private Stack<Integer> stackIn;
    private final Stack<Integer> outStack;

    public MyQueue() {
        stackIn = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        stackIn.push(x);
    }

    public int pop() {
        if(outStack.empty()) // outStack 에 데이터가 비어있다면
            // Stack 타입의 인스턴스가 가진 데이터를 Stack 타입의 또 다른 인스턴스에 addAll 한다면
            // 그 구조가 가진 요소가 그대로 복사된다. ex. 1, 2 요소가 0, 1 인덱스에 차례로 대입되어 있다면
            // 복사도 동일한 구조로 된다.
             outStack.addAll(stackIn.reversed());
        return outStack.pop(); // stackIn.addAll(outStack.reversed());
        // pop() 한 후에 없어진 요소를 stackIn 에도 적용해야할 것 같은데,
    }

    public int peek() {
        if(outStack.empty()) // outStack 에 데이터가 비어있다면
            // outStack.addAll(stackIn);
            outStack.addAll(stackIn.reversed());
        return outStack.peek();
    }

    public boolean empty() {
        // stack 의 size 로도 empty 상태인지 판별할 수 있을 듯?
        return stackIn.isEmpty() && outStack.empty();
    }

    public static void main(String[] args) {
        MyQueue queue = new MyQueue();

        queue.push(1);
        System.out.printf("push(1) 한 후, queue: %s\n", queue);

        queue.push(2);
        System.out.printf("push(2) 한 후, queue: %s\n", queue);

        queue.peek();
        System.out.printf("peek() 한 후, queue: %s\n", queue);

        queue.pop();
        System.out.printf("pop() 한 후, queue: %s\n", queue);

        System.out.print("queue.empty(): "+queue.empty());
    }
}

 

---

자료구조에서 선형구조에 속하는 큐와 스택 
선형구조(Linear Structure)란 데이터 요소들이 일렬로 나열되어 있고(순차적 배치), 
각 요소가 순차적으로 연결된 구조를 의미한다(이웃한 데이터가 연결되어 있음). 
데이터를 앞에서부터 뒤까지 하나씩 순서대로 접근하거나 처리할 수 있는 구조를 의미한다. 
(처리 순서가 중요함) 
*비선형구조는 (데이터를 저장하는 방법중에서) 일렬로 나열되지 않은 자료구조를 의미한다. 
데이터가 계층적으로 구성된 경우에 사용한다. ex. 트리, 그래프 

선형구조에는 배열, 리스트, 큐, 스택, 덱이 있다. 
배열은 크기와 데이터 타입이 모두 지정된 데이터의 집합이다. 
리스트의 예로는 Linked List가 있으며, Linked List는 여러 타입으로 나뉜다. 
Java에서는 java.util 패키지의 LinkedList 클래스를 사용하는데, 
연결 리스트를 직접 구현하거나 Java Collection Framework의 클래스를(LinkedList) 활용하기도 한다. 
배열과 인덱스는 순차 자료구조로(요소들이 순서대로 나열되어 있어) 
각 요소에 부여된 번호(인덱스)로 해당 요소에 빠르게 접근할 수 있다. 
→ 배열과 리스트 모두 인덱스로 접근 가능한 순차 자료구조 
LinkedList와 ArrayList를 비교했을 때
배열기반인 ArrayList는 이중 연결 리스트 기반인 LinkedList 보다 인덱스 접근 속도가 빠르기 때문에
검색과 같은 조회기능을 사용할 때 유용하고, 삽입 및 삭제와 같은 기능을 사용할 때는 LinkedList 를 사용하는 것이 유용하다.

스택은 먼저 들어온 데이터가 가장 나중에 나간다(FILO) 
이는 가장 나중에 들어온 데이터가 가장 먼저 나간다는 의미와 같다(후입선출) 
큐는 먼저 들어온 데이터가 가장 먼저 나간다(FIFO) 
이는 가장 나중에 들어온 데이터가 가장 나중에 나간다는 의미와 같다(선입선출) 

---

참고자료 
[youtube] 자료 구조 이해를 위한 쉬운 설명 | 스택 vs 큐