선형 자료구조 - 3. 스택

스택 (Stack)

스택이란 후입선출(Last In, First Out)의 형태를 가지고 있는 자료구조입니다.

후입선출이란 나중에 들어온 것이 먼저 나간다는 의미입니다.

 

Stack의 모습

 

보통 함수 콜 스택이나 인터럽트 처리 등 데이터를 입력된 순서의 역순으로 처리할 때 사용합니다.

 

스택의 연산

스택의 연산은 Push와 Pop,  Peek으로 이루어져 있습니다.

 

• Push : 데이터를 스택의 가장 마지막 위치에 추가합니다.
• Pop : 스택의 가장 마지막 위치에서 데이터를 꺼냅니다.
• Peek : 가장 마지막 데이터를 꺼내지 않고 읽어오기만 합니다.

 

스택의 시간복잡도

• 삽입 : O(1)
• 삭제 : O(1)
• 탐색 : O(N)

 

프로그래밍 언어로 구현

직접 배열이나 리스트로 구현도 가능하지만, 언어들에서 제공해주는 라이브러리가 존재합니다.

Java

자바에서는 Stack 자료형을 제공하고 있습니다.

Stack<Integer> stack = new Stack<>();  // Stack 자료구조 생성

stack.push(10);  // 10 삽입

stack.peek();   // 가장 마지막 데이터 조회, 10

stack.pop();    // 가장 마지막 데이터 꺼내기 , 10

 

밑은 Stack을 직접 간단하게 구현한 코드입니다.

import java.util.ArrayList;

public class ExampleStack {

   ArrayList<Integer> list;

   public ExampleStack() {
      this.list = new ArrayList();
   }

   public boolean isEmpty() {
      if (this.list.size() == 0) {
         return true;
      }

      return false;
   }

   public void push(int data) {
      this.list.add(data);
   }

   public Integer pop() {
      if (this.isEmpty()) {
         return null;
      }

      int data = this.list.get(list.size() - 1);

      this.list.remove(this.list.size() - 1);

      return data;
   }

   public Integer peek() {
      if (this.isEmpty()) {
         return null;
      }

      return this.list.get(this.list.size() - 1);
   }
}