스택

목차

1.스택?

2.스택 특징

3.스택을 구현하는 방법

 

1.스택?

스택(Stack)은 후입선출(Last In, First Out, LIFO) 방식을 따르는 자료구조입니다. 말 그대로 나중에 삽입된 데이터가 먼저 꺼내지는 구조를 가지고 있습니다.

2.스택 특징

 

• 후입선출(LIFO): 나중에 들어온 데이터가 먼저 처리됩니다.
• 단순성: 삽입과 삭제가 한쪽 끝에서만 이루어져 구조가 단순합니다.
• 제한된 접근: 데이터 접근은 오직 Top에서만 가능합니다.

 

3.스택을 구현하는 방법

스택을 구현하는 방법으로는 배열을 이용한 방법, 리스트를 이용한 방법, 링크드리스트를 이용한 방법이 있습니다. 

각 방법을 사용해서 구현하면 코드는 다음과 같습니다. 

 

1) 배열을 이용한 방법

public class StackSample {
	private int[] stack;
    private int top;
    
    public StackSample(int capacity) {
    	 stack = new int[capacity];
         top = -1;
    }
    
    public void push(int value) {
        if (top == stack.length - 1) {
            System.out.println("스택 오버플로우");
            return;
        }
        stack[++top] = value;
    }

    public int pop() {
        if (top == -1) {
            System.out.println("스택 언더플로우");
            return -1;
        }
        return stack[top--];
    }

    public int peek() {
        if (top == -1) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
    
    public static void main(String[] args) {
    	StackSample arrayStack = new StackSample(5);
        arrayStack.push(10);
        arrayStack.push(20);
        arrayStack.push(30);
        System.out.println("peek(): " + arrayStack.peek());
        System.out.println("pop(): " + arrayStack.pop());
        System.out.println("pop(): " + arrayStack.pop());
	}
}

 

2) 리스트를 활용한 방법

public class StackSample1 {
	private ArrayList<Integer> stack;

    public StackSample1() {
        stack = new ArrayList<>();
    }

    public void push(int value) {
        stack.add(value);
    }

    public int pop() {
        if (stack.isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack.remove(stack.size() - 1);
    }

    public int peek() {
        if (stack.isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack.get(stack.size() - 1);
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
	
	public static void main(String[] args) {
		StackSample1 sample1 = new StackSample1();
		
		sample1.push(10);
		sample1.push(20);
		sample1.push(30);
		
		System.out.println("peek:" + sample1.peek());
		System.out.println("pop:" + sample1.pop());
		System.out.println("pop:" + sample1.pop());
		System.out.println("pop:" + sample1.pop());
	}
}

 

3)링크드 리스트를 활용한 방법

public class StackSample2 {
	 private Node top;
	 
	 private class Node {
        int data;
        Node next;

        Node(int data) {
        	this.data = data;
        }
     }
	 
	 public void push(int value) {
	        Node newNode = new Node(value);
	        newNode.next = top;
	        top = newNode;
	    }

    public int pop() {
        if (top == null) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        	int value = top.data;
	        top = top.next;
        return value;
    }

    public int peek() {
        if (top == null) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
    
    public static void main(String[] args) {
		StackSample2 sample2 = new StackSample2();
		
		sample2.push(60);
		sample2.push(70);
		
		System.out.println(sample2.peek());
		System.out.println(sample2.pop());
		System.out.println(sample2.pop());
	}
}