JAVA - Stack이란? 그리고 구현

스택의 구조

스택 사용법

• 삽입(Push)
  • 어떠한 데이터를 집어 넣는 것을 Push라고 합니다. Push는 스택의 구조상 마지막 데이터 위치에 삽입됩니다.
• 삭제(Pop)
  • Push와 반대로 데이터를 빼는 것을 Pop이라고 합니다.
• 읽기(Peek)
  • 마지막 위치에 해당하는 데이터를 읽습니다.

Stack 구현 코드

public class Stack {
    private int top;
    private int size = 2;
    private int[] elements;

    public Stack() {
        this.elements = new int[size];
    }

    public Stack(int data) {
        this.elements = new int[size];
        this.elements[top++] = data;
    }

    public void push(int data){
        if(this.top == elements.length){
            size = top + 6;
            int [] extendElements = new int [size];

            // migrate
            for (int i = 0; i < top; i++) {
                extendElements[i] = elements[i];
            }
            elements = extendElements;
        }

        elements[top++] = data;
    }

    public int pop(){
        if(this.top == 0){
            return  -1;
        }else{
            return elements[--top];
        }
    }
    
    public int peek(){
        int index = --top;
        return this.elements[index];
    }

    public void print(){
        for(int i=0; i<top; i++){
            System.out.println(elements[i]);
        }
    }
}

 

public class StackExample {
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.pop();
        stack.push(4);
        stack.push(5);

        stack.print();
	//1
	//2
	//4
	//5
	System.out.println("peek : " + stack.peek()); // 5
    }
}

 

 

과제 3. 앞서 만든 ListNode를 사용해서 Stack을 구현하세요.

• https://kdg-is.tistory.com/230

public class ListNodeStack {
    private ListNode head;

    public ListNodeStack() {
        this.head = null;
    }

    public void push(int data){
        ListNode node = head;
        ListNode addNode = new ListNode(data);

        /**
         * head가 null이라면 방금 데이터를 head로 설정
         */
        if(head == null){
            head = addNode;
            return;
        }

        /**
         * 순차탐색하여 정렬
         */
        while (node.next != null) {
            node = node.next;
        }

        node.next = addNode;
    }

    public int pop(){
      ListNode node = head;

     /**
      * 순차탐색하여 정렬
      */
      while (node.next.next != null) {
          node = node.next;
      }

      ListNode result = node.next;
      node.next = null;

      return  result.data;
    }

    public void print(){
        ListNode node = head;

        while (node != null) {
            System.out.println(node.data);
            node = node.next;
        }
    }
}

 

public class ListNodeStackExample {
    public static void main(String[] args) {
        ListNodeStack listNodeStack = new ListNodeStack();
        listNodeStack.push(1);
        listNodeStack.push(2);
        System.out.println("pop --> " + listNodeStack.pop()); // pop --> 2
        listNodeStack.push(3);

        listNodeStack.print();
        // 1
        // 3
    }
}