03-3 스택의 구현(연결 자료구조 방식)

※ 순차 자료구조를 이용해 구현한 스택과 차이점

배열을 사용하여 구현하기는 쉽지만 물리적 크기가 고정되어 있는 배열을 사용하기 때문에 스택의 크기를 변경하기 어렵고

물리적인 공간 낭비가 생길 수 있다. 이러한 문제를 연결 자료구조를 이용함으로써 해결할 수 있다.

※ 연결 자료구조를 통한 구현

1. 스택 초기 상태(공백 스택)는 참조변수 top을 null로 설정.
2. 스택이 push되면 새로 push된 노드는 이전 노드를 가르키고 top은 새로 들어온 노드를 가르킨다.

※ 연결 자료구조를 통한 구현 소스

Interface Stack

interface Stack{

     boolean isEmpty(); //스택이 공백스택인지 확인하는 함수

     void push(char item); //문자를 push하는 함수

     char pop(); //pop 하는 함수(top에 있는 원소를 삭제하고 반환하는 연산)

     void delete(); //top에있는 원소를 삭제한느 연산

     char peek(); //top에 있는 원소를 반환하는 연산

}

StackNode

public class StackNode {

       public StackNode link;

       private char data;

       public StackNode(char item) {

              this.data = item;

              this.link =null;

       }

       public char getData(){

              return this.data;

       }

}

LinkedStack

public class LinkedStack implements Stack {

       private StackNode top;

       public LinkedStack() {

              this.top =null;

       }

       @Override

       public boolean isEmpty() {

              if(top==null){

                     return true;

              }else{

                     return false;

              }

       }

       @Override

       public void push(char item) {

              StackNode node = new StackNode(item);

              if(isEmpty()){

                     top = node;

              }else{

                     node.link= top;

                     top= node;

              }

       }

       @Override

       public char pop() {

              if(isEmpty()){

                     System.out.println("stack is empty");

                     return 0;

              }else{

                     StackNode node = top;

                     top = node.link;

                     return node.getData();

              }

       }

       @Override

       public void delete() {

              if(isEmpty()){

                     System.out.println("stack is empty");

              }else{

                     StackNode node = top;

                     top = node.link;

              }

       }

       @Override

       public char peek() {

              if(isEmpty()){

                     System.out.println("stack is empty");

                     return 0;

              }else{

                     return top.getData();

              }

       }

       public void printStack(){

              if(isEmpty()){

                     System.out.println("stack is empty");

              }else{

                     StackNode node = top;

                     int idx =1;

                     while(node.link != null){

                           System.out.print("index : " + idx + " value : " + node.getData() + " / ");

                           node = node.link;

                           idx++;

                     }

                     System.out.println("index : " + idx + " value : " + node.getData());

              }

       }

}

Main

public class Main {

       public static void main(String[] args) {

              char deletedItem;

              LinkedStack stack = new LinkedStack();

              stack.push('A');

              stack.printStack();

              stack.push('B');

              stack.printStack();

              stack.push('C');

              stack.printStack();

              deletedItem = stack.pop();

              System.out.println("deleteItem : "+ deletedItem);

              System.out.println("peek top value : " + stack.peek());

       }

}