선형자료구조 - 스택

📌 스택

1. 후입 선출(Last In First Out; LIFO) 자료구조

- 마지막에 들어온 데이터가 먼저 나가는 구조

 

 

2. 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용

- ex) 함수 콜 스택, 수식 계산, 인터럽트 처리 등

- 함수 콜 스택 : 함수의 내부 함수를 실행하는 전체 로직을 저장하는 공간(fun2 -> fun1 -> main 함수)

 

함수 호출에 의한 스택 프레임의 변화 (출처 : https://www.tcpschool.com/c/c_memory_stackframe)

 

 

- 인터럽트 처리 : 로직을 실행하다가 중간에 다른 처리가 필요할 때 사용 (기존 로직을 스택에 저장한 후 중간 처리를 실행한 뒤에 다시 로직 실행)

 

 

 

스택 기본 구조

• 후입 선출 구조
• 기본적으로 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이러우짐
• 스택 공간 안에 스택 하단(Bottom)과 스택 상단(Top)이 있고, 데이터 삽입(Push)과 데이터 삭제(Pop) 동작이 이루어짐

스택 구조 (출처 : https://bambbang00.tistory.com/3)

 

 

 

스택 기본 연산

• 데이터 추가(Push)
  • 스택의 가장 마지막 위치에 데이터 추가

 

• 데이터 꺼내기(Pop)
  • 스택의 가장 마지막 위치에서 데이터 꺼냄

 

 

스택 기본 코드

import java.util.Stack;

public class Main {
	public static void main(String[] args) {
    	Stack stack = new Stack();   // 스택 자료구조 생성
        
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack);    // [1, 2, 3, 4, 5]
        
        System.out.println(stack.pop());  // 5
        System.out.println(stack);    // [1, 2, 3, 4]
        
        System.out.println(stack.peek());  // 4
        System.out.println(stack);    // [1, 2, 3, 4]
        
        System.out.println(stack.contains(1));   // true
        System.out.println(stack.size());   // 4
        System.out.println(stack.empty());  // false
        
        stack.claer();   
       	System.out.println(stack);   // []
        stack.pop();    // 에러 발생 => 스택이 비어있기 때문
	}
}

 

 

 

ArrayList를 이용한 스택 구현

import java.util.ArrayList;

class MyStack1 {
	ArrayList list;
    
    MyStack1() {
    	this.list = new ArrayList();
    }
    
    // 데이터 유무 확인
    public boolean isEmpty() {
    	if(this.list.size() == 0) {
        	return true;
        } else {
        	return false;
        }
    }
    
    // 데이터 삽입
    public void push(int data) {
    	this.list.add(data);
    }
    
    // 데이터 삭제
    public Integer pop() {
    	if(this.isEmpty()) {
        	System.out.println("Stack is empty!");
            return null;
        }
        
        int data = (int) this.list.get(this.list.size() - 1); // 인덱스 마지막 데이터 가져오기
        // 상단에 ArrayList list가 제너릭하게 선언되어 있지 않기 때문이 (int) 형변환 필요
        
        this.list.remove(this.list.size() - 1);
        retrun data;
    }
    
    // peek
    public Integer peek() {
    	if (this.isEmpty()) {
        	System.out.println("Stack is empty!");
            return null;
        }
        
        int data = (int) this.list.get(this.list.size() - 1);
        return data;
    }
    
    // 스택 출력
    public void printStack() {
    	System.out.println(this.list);
    }
}



public class Practice1 {
	public static void main(String[] args) {
    	MyStack1 myStack = new MyStack1();
        System.out.println(myStack.isEmpty());     // true
        
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        myStack.printStack();   // [1, 2, 3, 4, 5]
        
        System.out.println(myStack.peek());  // 5
        myStack.printStack();   // [1, 2, 3, 4, 5]
        
        System.out.println(myStack.pop());   // 5
        System.out.println(myStack.pop());   // 4
        myStack.printStack();  // [1, 2, 3]
        
        System.out.println(myStack.pop());  // 3
        System.out.println(myStack.pop());  // 2
        System.out.println(myStack.pop());  // 1
        myStack.printStack(); // []

 

---

스택은 한마디로 '데이터를 쌓아 올리는 형태로 관리하는 자료 구조' 이다.

마지막으로 들어온 데이터가 먼저 나가는 LIFO 원칙을 따르고,

기본 기능으로서 스택에 데이터를 추가하는 push,

스택에서 데이터를 제거하고 반환하는 pop,

스택의 맨 위에 있는 데이터를 제거하지 않고 반환하는 peek,

스택이 비어있는지 확인하는 isEmpty를 잘 숙지해야 되겠다.

 

구현 방법으로는 배열을 사용하면 고정된 크기의 스택을 만들 수 있고, 연결 리스트를 사용하면 동적으로 크기를 조절할 수 있다.

 

응용 분야로는 함수가 호출될 때마다 호출 정보를 스택에 저장하고, 종료되면 해당 정보를 스택에서 꺼내는 함수 호출 스택,

스택에서 데이터를 꺼내는 문자열 역순 처리, 코드나 수식의 괄호 균형을 검사할 때 사용하는 구문 검사가 있다.

 

코드 구현 시 java.util.Stack 클래스를 사용하여 스택을 생성하고, 위 기본 기능인 push, pop, peek, isEmpty 기능을 사용