[자바 기본] 스택과 큐(Stack and Queue)

스택과 큐

스택은 후입선출(LIFO : Last In First Out)은 말 그대로 나중에 넣은 객체가 먼저 빠져나가는 구조를 말합니다.

반대로 큐는 선입선출(FIFO : First In First Out)은 먼저 넣은 객체가 먼저 빠져나오는 구조를 말합니다.

• Stack

옆에 그림을 보면서 설명하겠습니다. 

넣기 : push   /    빼기 : pop

순서대로 1 / 2 / 3 을 push하고 pop 을 하게 된다면 

당연히 3 / 2 / 1 순서대로 pop을 하게 됩니다.

정말 간단한 개념입니다.

스택을 응용한 곳이 바로 JVM 메모리에 스택 영역이 있습니다. 

개념에 대해 공부를 했으니 이제 우리가 이것을 사용해봐야합니다. 

직접 간단한 스택 알고리즘을 한번 구현해보도록 하겠습니다.

출처 : 백준 알고리즘

문제

package Stack;
 
import java.util.ArrayList; // arrayList로 구현
import java.util.Scanner;
 
class MyStack {
    private int top;
    private ArrayList<Integer> stackarr;
 
    public MyStack() {// 생성자
        stackarr = new ArrayList<Integer>();
        top = -1;
    }
 
    public void push(int n) { // push 기능
        top++;                // 스택에 객체를 넣습니다.
        stackarr.add(n);
    }
 
    public void pop() {             // pop 기능
        if (top == -1)              // 이 말은 안에 데이터가 하나도 없다는 뜻
            System.out.println(-1); 
        else {                      // 스택의 제일 위에 객체를 가져옵니다.
            System.out.println(stackarr.get(top));
            stackarr.remove(top);   // 그리고 삭제까지 합니다.
            top--;
        }
    }
 
    public void size() {            // list의 사이즈
        System.out.println(stackarr.size());
    }
 
    public void empty() {           // 스택이 비었는지 안비었는지 체크
        if (stackarr.isEmpty())
            System.out.println(1);
        else
            System.out.println(0);
    }
 
    public void top() {          // 스택의 가장 위에 있는 객체를 가져옵니다.
        if (top == -1)
            System.out.println(-1);
        else
            System.out.println(stackarr.get(top));
    }
}
 
public class Stack {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        MyStack stack = new MyStack();
        sc.nextLine();
        for (int i = 0; i < n; i++) {
            String input = sc.nextLine();
            CheckStack(input, stack);
        }
    }
 
    public static void CheckStack(String input, MyStack mystack) { 
        String command = input.substring(0, 3);
        if (command.equals("pus"))
            mystack.push(Integer.parseInt(input.split(" ")[1]));
        else if (command.equals("pop"))
            mystack.pop();
        else if (command.equals("emp"))
            mystack.empty();
        else if (command.equals("siz"))
            mystack.size();
        else if (command.equals("top"))
            mystack.top();
    } // 문제를 풀기 위해 입력값으로 push 나 empty 를 받기 위해 앞에서부터 3자리까지만 
}     // 잘라서 사용했습니다. 그리고 push를 할 때 push X 에서 X 값을 넣기 위해 자르고
      // 형 변환해서 넣었습니다.

간단하게 문제에 맞춰서 스택을 구현했습니다.

이번에는 자바에서 Stack클래스를 사용해보도록 하겠습니다.

package Stack;
 
import java.util.Stack;
 
public class Stack01 {
 
    public static void main(String[] args) {
 
        Stack<String> stack = new Stack<String>();
 
        stack.push("A"); // 객체를 넣습니다.
        stack.push("B");
        stack.push("C");
        stack.push("D");
        
        String result1 = stack.peek(); // 제일 위에 있는 객체를 가져옵니다.
        System.out.println(result1);   // 삭제를 하지 않습니다.
        
        while (!stack.isEmpty()) {
            String result2 = stack.pop();   // 제일 위에 있는 객체를 가져옵니다.
            System.out.print(result2+ " "); // 그 후에 삭제합니다.
        }
    }
}
 

순서대로 A > B > C > D  로 넣었지만 꺼내 올 때는 D > C > B > A 순서대로 빼옵니다.

이렇게 스택을 구현할 수 있습니다. 그리고 자바API를 확인해보니 

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example: 

Deque<Integer> stack = new ArrayDeque<Integer>();

이걸 사용하라는 것 같네요. 이것 말고도 linkedList로도 구현이 가능하니 

한번 다른 방법으로도 구현해보세요.