[자료구조] Java 스택(Stack) 정리 (배열, 연결 리스트)

Java 스택(Stack) 정리

1. 스택(Stack)의 개요

스택(Stack)은 사전적으로 '더미', '쌓아 올림' 이라는 의미를 가진다. '더미'란 '많은 물건이 한데 모여 쌓인 큰 덩어리'를 의미한다. 

스택(Stack)은 데이터를 쌓아올리는 형태로 저장하여 추출할때는 맨 위에 있는 데이터를 먼저 꺼내는 형태이기 때문에 제일 마지막에 저장한 데이터를 제일 먼저 꺼내는 후입선출(LIFO - Last In First Out) 형태의 자료구조이다.

스택(Stack)은 가장 마지막의 데이터의 위치에 대해 삽입이나 삭제가 발생하므로, 이러한 구조에 사용될 때 간단하며, 더욱 효율적이고 쉽게 사용이 가능하다.

가장 최근에 입력된 데이터를 top 이라고 하며 스택은 top에서만 삽입, 삭제, 읽기 동작이 발생할 수 있다.

top은 데이터의 수에 따라 유동적으로 변하며 데이터가 하나 삽입될 경우 하나 증가하고 데이터가 하나 삭제될 경우 하나 감소하도록 작성한다.

그리고 가장 먼저 입력되에 바닥에 깔린 데이터를 bottom이라고 하며 다중 스택 같은 특별한 구조가 아니라면 이 값은 0으로 고정되어 있다.

2. 스택(Stack)의 동작

(1) 삽입 - Push

스택(Stack)에 새로운 데이터를 삽입하는 작업을 push라고 한다. 이는 top 값을 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

(2) 삭제(추출) - Pop

스택(Stack)에서 데이터를 제거하는 작업을 pop이라고 하며 이는 top이 가리키고 있는 자료를 삭제한 후 top 값을 하나 감소 시키도록 구현한다.

(3) 읽기 - peek

스택에서 top이 가리키는 데이터를 읽는 작업을 peek이라고 하며 top 값의 변화는 없다.

3. 배열을 이용한 구현

리스트와 마찬가지로 스택을 구현하는 방법은 배열과 연결 리스트가 있는데 먼저 배열을 이용하여 구현해본다.

배열에 실제 데이터를 저장하기 때문에 데이터를 저장할 배열이 하나 필요하며 스택의 최대 크기를 저장할 변수와 스택의 입출력 데이터를 가리키는 top을 관리하기 위한 변수가 필요하다.

public class ArrayStack {          private int top;     private int maxSize;     private Object[] stackArray;          // 배열 스택 생성,  스택의 최대 크기로 생성     public ArrayStack(int maxSize){                  this.maxSize = maxSize;         this.stackArray = new Object[maxSize];         this.top = -1;     }          // 스택이 비어있는지 체크     public boolean empty(){         return (top == -1);     }          // 스택이 꽉찼는지 체크     public boolean full(){         return (top == maxSize-1);     }          // 스택에 item 입력     public void push(Object item){                  if(full()) throw new ArrayIndexOutOfBoundsException((top+1)+">=" + maxSize);                  stackArray[++top] = item;     }          // 스택의 가장 위의 데이터 반환     public Object peek(){                  if(empty()) throw new ArrayIndexOutOfBoundsException(top);                  return stackArray[top];     }          // 스택의 가장 위의 데이터 제거     public Object pop(){                  Object item = peek();                  top--;                  return item;     } }

생성자를 통해 스택(Stack)의 최대 크기를 입력받아 데이터를 저장할 배열을 생성하고 top 값은 초기값으로 -1을 지정한다. 이는 스택에 데이터가 없다는 의미이다.

그리고 스택이 비었는지 여부를 반환하는 empty() 메소드와 스택이 다 찼는지 여부를 반환하는 full() 메소드를 정의한다. 

top 값은 맨 위에 위치한 데이터의 index 값이 되므로 top 값이 초기값(-1)일 경우에는 빈 스택이 되며 top 값이 배열의 크기 -1일 경우에는 스택에 데이터가 꽉 찼다는 의미이다.

push() 메소드는 top을 하나 증가 시킨 후 top 위치에 지정한 데이터를 삽입하면 되고,

peek() 메소드는 top 위치의 데이터를 반환하며,

pop() 메소드는 peek()를 호출하여 top 위치의 데이터를 반환하고 top 값을 하나 감소시킨다.

4. 연결 리스트를 이용한 구현

배열을 이용한 스택 구현의 가장 큰 단점은 처음 생성한 크기를 바꿀 수 없다는 것이다.

이를 해결하기 위하여 연결 리스트를 이용하여 구현하는 방법을 알아본다.

연결 리스트를 이용하여 스택을 구현하기 위해서는 리스트와 마찬가지로 실제 저장될 데이터와 다음 데이터의 참조를 가리키는 참조자를 추가한 Node 클래스가 필요하며 노드 클래스는 단순 연결 리스트와 같다.

[자료구조] Java 단순 연결 리스트(simple linked list) 정리

그리고 리스트와 헤더 대신 top 노드를 가리키는 top 변수를 하나 선언하여 삽입, 삭제 작업을 할 노드를 지정하면 된다.

public class ListStack {          private Node top;          // 노드 class 단순연결리스트와 같다.     private class Node{                  private Object data;         private Node nextNode;                  Node(Object data){             this.data = data;             this.nextNode = null;         }     }          // 생성자, stack이 비어있으므로 top은 null이다.     public ListStack(){         this.top = null;     }          // 스택이 비어있는지 확인     public boolean empty(){         return (top == null);     }          // item 을 스택의 top에 넣는다.     public void push(Object item){                  Node newNode = new Node(item);         newNode.nextNode = top;         top = newNode;              }          // top 노드의 데이터를 반환한다.     public Object peek(){         if(empty()) throw new ArrayIndexOutOfBoundsException();         return top.data;     }          // top 노드를 스택에서 제거한다.     public Object pop(){                  Object item = peek();         top = top.nextNode;         return item;     } }

Node 클래스는 데이터를 저장할 data와 다음 노드를 지정할 nextNode가 선언되었다.

ListStack의 top은 스택에서 자료를 처리할 위치인 top 노드를 나타내며 초기값이 null인 경우 빈 스택이 되며 전체 길이가 정해져 있지 않기 때문에 스택이 다 찼는지 여부는 체크할 필요가 없다.

push() 메소드는 새로운 노드를 하나 생성 한 후 삽입되기 이전의 top 노드를 nextNode로 참조하고 top은 새로 생성한 노드로 지정한다.

peek() 메소드는 top 노드의 데이터를 반환하며

 pop() 메소드는 peek()를 호출하여 top 노드와 데이터를 반환하고 top 노드를 예전 top 노드의 nextNode 값으로 변경한다.

즉, 위에서 두번째 노드를 top 노드로 변경한다.

5. 스택(Stack) 테스트

public class StackTest {          public static void main(String[] args){                           // 크기 5의 배열 스택 생성         ArrayStack arrayStack = new ArrayStack(5);                  System.out.println("Array Stack 테스트");                  // 스택에 데이터 삽입         for(int i=1; i<=5; i++){             arrayStack.push("ArrayStack 데이터-" + i);         }                  System.out.println(arrayStack.pop());         System.out.println(arrayStack.pop());         System.out.println(arrayStack.peek());         System.out.println(arrayStack.peek());         System.out.println(arrayStack.pop());         System.out.println(arrayStack.pop());         System.out.println(arrayStack.pop());              System.out.println();                  // 연결리스트 스택 생성         ListStack listStack = new ListStack();                  System.out.println("List Stack 테스트");                  // 스택에 데이터 삽입         for(int i=1; i<=5; i++){             listStack.push("ListStack 데이터-"+i);         }                  listStack.push("ListStack 데이터-6");                  System.out.println(listStack.pop());         System.out.println(listStack.pop());         System.out.println(listStack.peek());         System.out.println(listStack.peek());             System.out.println(listStack.pop());         System.out.println(listStack.pop());         System.out.println(listStack.pop());         System.out.println(listStack.pop());              } }

Stack.zip

출처: https://hyeonstorage.tistory.com/262?category=578561 [개발이 하고 싶어요]