스택 (Stack)

스택 (Stack)

---

스택 (Stack)

• 선형 자료구조
• 프링글스처럼 한 쪽은 막혀있고 다른 한 쪽으로 과자를 꺼내거나 넣는 것
• 후입선출 (Last-In, First-Out, LIFO) 구조
  마지막에 삽입한 것이 먼저 나오는 구조
• 배열 또는 리스트로 구현 가능

추상 자료형 (ADT)

자료형	반환값	내용
initialize()	void	스택 초기화
push(Data)	void	스택에 데이터 삽입
pop()	Data	데이터 반환 후 삭제
peek()	Data	데이터 반환 후 삭제하지 않음
isEmpty()	boolean	스택이 비어있는지 확인

 

 

배열로 스택 구현

• 배열의 크기를 고정해야 함
• 스택에서 가장 마지막에 삽입된 위치를 저장하는 변수가 필요 (topIndex)

구현

• 디렉토리 구조
  

  

• ArrayStack.java
  

  package Stack.Array;
  
  import Stack.Stack;
  
  public class ArrayStack implements Stack {
      // 스택 배열의 최대 크기
      final private int MAX_SIZE = 10;
      // 가장 마지막에 삽입된 데이터의 위치
      int topIndex = -1;
      // 스택 설정
      Object[] stack = new Object[MAX_SIZE];
  
      @Override
      public void initialize() {
          // 배열을 null로 초기화
          for(int i=0; i<MAX_SIZE; i++) {
              stack[i] = null;
          }
          // -1 => 아무것도 삽입되지 않음
          topIndex = -1;
      }
  
      @Override
      public void push(Object data) {
          if (topIndex == MAX_SIZE - 1){
              System.out.println("더이상 공간이 없습니다.");
              return;
          }
  
          // 데이터 삽입
          stack[++topIndex] = data;
      }
  
      @Override
      public Object pop() {
          if (isEmpty()){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          // 데이터 반환 후 삭제
          return stack[topIndex--];
      }
  
      @Override
      public Object peek() {
          if (isEmpty()){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          return stack[topIndex];
      }
  
      @Override
      public boolean isEmpty() {
          if (topIndex == -1){
              return true;
          }
  
          return false;
      }
  }​

• ArrayStackMain.java
  

  package Stack.Array;
  import Stack.Stack;
  
  public class ArrayStackMain {
      public static void main(String[] args) {
          Stack stack = new ArrayStack();
          stack.initialize();
  
          stack.push(1); stack.push(2);
          stack.push(3); stack.push(4);
          stack.push(5); stack.push(6);
  
          while(!stack.isEmpty()){
              System.out.println(stack.pop());
          }
      }
  }​

리스트로 스택 구현

• 머리에 데이터를 삽입하는 연결 리스트와 동일
  

  

구현

• 디렉토리 구조
  

  

• LinkedListStack.java
  

  package Stack.LinkedList;
  import Stack.Stack;
  
  public class LinkedListStack implements Stack {
  
      public class Node {
          Object data;
          Node nextNode;
      }
  
      Node head = null;
  
      @Override
      public void initialize() {
          head = null;
      }
  
      @Override
      public void push(Object data) {
          Node newNode = new Node();
          newNode.data = data;
          newNode.nextNode = head;
          head = newNode;
      }
  
      @Override
      public Object pop() {
          if (isEmpty()){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          Object rData = head.data;
          head = head.nextNode;
  
          return rData;
      }
  
      @Override
      public Object peek() {
          if (isEmpty()) {
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          return head.data;
      }
  
      @Override
      public boolean isEmpty() {
          if (head == null){
              return true;
          }
  
          return false;
      }
  }​

• LinkedListStackMain.java
  

  package Stack.LinkedList;
  
  import Stack.Array.ArrayStack;
  import Stack.Stack;
  
  public class LinkedListStackMain {
      public static void main(String[] args) {
          Stack stack = new LinkedListStack();
          stack.initialize();
  
          stack.push(1); stack.push(2);
          stack.push(3); stack.push(4);
          stack.push(5); stack.push(6);
  
          while(!stack.isEmpty()){
              System.out.println(stack.pop());
          }
      }
  }​