[Data Structure] 자료구조 - 스택 (Stack)

스택(Stack)

개념: 스택은 같은 구조와 크기의 자료를 top 이라고 정한 한 곳에만 쌓을 수 있고, 

top으로만 접근하도록 제한하여 만든 자료구조

스택에서 top을 통해 들어온 자료가 일정한 방향으로 차곡차곡 쌓입니다.

마치 뷔페식당의 쌓인 접시나

책상위에 차곡차곡 쌓아 둔 책

과 같이 말이죠~

스택에서 자료를 삭제할 때도 top을 통해서만 가능하기 떄문에 

top이 가리키고 있는 스택의 마지막 자료만 삭제할 수 있습니다.

따라서, 스택은 시간순서에 따라 자료가 쌓이고, 

삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 

후입선출(LIFO: Last In First Out)의 구조를 갖습니다.

스택의 구조

 

위처럼 data1,2,3이 차곡차곡 쌓이고 stack에서 top의 위치는 data 3을 가리키는 겁니다!

절대로 스택에서 data3이 먼저 제거되지 않는 한, data2와 data1을 꺼낼수 없습니다!!!

자 그럼 소스 코드를 통해 스택에 대해 알아보도록 합시다!

먼저 

순차 자료구조(배열)로 구현한 스택을 살펴보겠습니다!!!

클래스다이어그램으로 먼저 프리뷰하죠~

 

스택은 크게 4개의 연산을 가지고 있습니다!

Push: 스택안에 데이터를 집어 넣는 연산

Pop: 스택안의 데이터를 끄집어 내는 연산

Top: 스택의 상위 데이터를 반환하는 연산(Pop과는 다른 용도입니다!!!)

Empty: 스택이 비어있는지 불리언 값 반환하는 연산

그럼 소스코드를 보시지요~

stack.java

 

package Stack;
 
public interface Stack {
    public boolean isEmpty();
    public void push(String item);
    public String pop();
    public void delete();
    public String top();
}
 

ArrayStack.java

 

 
package Stack;
 
public class ArrayStack implements Stack {
    private int top;
    private int stackSize;
    private String[] itemArray;
 
    public ArrayStack(int stackSize) {
        this.top = -1;
        this.stackSize = stackSize;
        itemArray = new String[this.stackSize];
    }
 
    public boolean isEmpty() {
        return (top == -1);
    }
 
    public boolean isFull() {
        return (top == this.stackSize - 1);
    }
 
    public void push(String item) {
        if (isFull()) {
            System.out.println("Stack is Overflow!");
        } else {
            itemArray[++top] = item;
            ;
            System.out.println("Inserted Item : " + item);
        }
    }
 
    public String pop() {
        if (isEmpty()) {
            System.out.println("Stack is Underflow!");
            return null;
        } else {
            return itemArray[top--];
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("Deleting fail! Stack is Empty!");
        } else {
            top--;
        }
    }
 
    public String top() {
        if (isEmpty()) {
            System.out.println("top fail! stack is Empty!");
            return null;
        } else {
            return itemArray[top];
        }
    }
 
    public void printStack() {
        if (isEmpty()) {
            System.out.println("Stack is empty!");
        } else {
            System.out.print("Array Stack >> ");
            for (int i = 0; i <= top; i++) {
                System.out.print(itemArray[i] + " ");
            }
            System.out.println();
        }
    }
}
 

StackMain.java

 

 
package Stack;
 
public class StackMain {
    public static void main(String[] args) {
        int stackSize = 5;
        String deleteItem = null;
        ArrayStack stack = new ArrayStack(stackSize);
 
        stack.push("S");
        stack.printStack();
 
        stack.push("T");
        stack.push("A");
        stack.push("C");
        stack.push("K");
        stack.printStack();
 
        deleteItem = stack.pop();
 
        if (!deleteItem.isEmpty()) {
            System.out.println("deleted Item: " + deleteItem);
        }
 
        stack.printStack();
    }
}
 

결과는 아래와 같습니다!!

 

다음은!

연결 자료구조(배열)로 구현한 스택

을 구현해보겠습니다!

클래스다이어그램부터 보시자.

 

Stack Interface는 위에서 만든 거 고대로 썼어요~

StackNode.java

 

 
package Stack;
 
public class StackNode {
    private String data;
    private StackNode link;
 
    public StackNode() {
        this.data = "";
        this.link = null;
    }
 
    public StackNode(String data) {
        this.data = data;
        this.link = null;
    }
 
    public StackNode(String data, StackNode link) {
        this.data = data;
        this.link = link;
    }
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public StackNode getLink() {
        return link;
    }
 
    public void setLink(StackNode link) {
        this.link = link;
    }
}
 

LinkedStack.java

 

 
package Stack;
 
public class LinkedStack implements Stack {
    private StackNode top;
 
    public boolean isEmpty() {
        return (top == null);
    }
 
    public void push(String item) {
        StackNode newNode = new StackNode(item, top);
        top = newNode;
        System.out.println("Inserted data: " + item);
    }
 
    public String pop() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!! ");
            return null;
        } else {
            String item = top.getData();
            top = top.getLink();
            return item;
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!! ");
        } else {
            top = top.getLink();
        }
    }
 
    public String top() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!");
            return null;
        } else {
            return top.getData();
        }
    }
 
    public void printStack() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!!");
        } else {
            StackNode tmp = top;
            System.out.println("Linked Stack >> ");
            while (tmp != null) {
                System.out.print("  " + tmp.getData() + "   ");
                tmp = tmp.getLink();
            }
            System.out.println();
        }
    }
 
}
 

StackMain.java

 

 
package Stack;
 
public class StackMain {
    public static void main(String[] args) {
        String deleteItem = null;
        LinkedStack lStack = new LinkedStack();
 
        lStack.push("I");
        lStack.push("AM");
        lStack.push("A");
        lStack.push("BOY");
 
        lStack.printStack();
 
        deleteItem = lStack.pop();
        if (!deleteItem.isEmpty()) {
            System.out.println("deleted Item : " + deleteItem);
        }
 
        lStack.printStack();
 
    }
}
 

결과 화면은 아래와 같습니다!!!