[JAVA] 자바의 자료구조 스택(Stack) 과 큐(Queue) 구현하기

by
자바에서 스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다. 스택은 데이터를 저장하고 관리하는 데 매우 유용하며, 여러 알고리즘 및 애플리케이션에서 자주 사용됩니다. 자바에서는 java.util.Stack 클래스를 사용하여 스택을 구현할 수 있습니다.

– Stack의 특징

  • 맨 마지막 위치(top)에서만 자료를 추가, 삭제 꺼내올 수 있음 (중간의 자료를 꺼낼 수 없음)
  • Last In First Out (후입선출) 구조
  • 택배 상자가 쌓여있는 모양
  • 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고 이를 무를때 사용할 수 있음
  • 함수의 메모리는 호출 순서에 따른 stack 구조
  • jdk 클래스 : Stack
import ch02.MyArray;

public class MyArrayStack {

    int top;
    MyArray arrayStack;
    public MyArrayStack(){
        top = 0;
        arrayStack = new MyArray();
    }
    public MyArrayStack(int size){
        top = 0;
        arrayStack = new MyArray(size);
    }

    public void push(int data){
        if (isFull()){
            System.out.println("stack is full");
            return;
        }
        arrayStack.addElement(data);
        top++;
    }
    public int pop(){
        if(top == 0){
            System.out.println("stack is empty");
            return MyArray.ERROR_NUM;
        }
        return  arrayStack.removeElement(--top);
    }
    public boolean isFull(){
        if (top == arrayStack.ARRAY_CAPACITY){
            return true;
        }
        else return false;
    }
    public int peek()
    {
        if (top == 0){
            System.out.println("stack is empty");
            return MyArray.ERROR_NUM;
        }
        return arrayStack.getElement(top-1);
    }

    public int getSize()
    {
        return top;
    }

    public boolean isEmpty()
    {
        if (top == 0){
            return true;
        }
        else return false;
    }

    public void printAll()
    {
        arrayStack.printAll();
    }
}

public class MyArrayStackTest {
    public static void main(String[] args) {
        MyArrayStack stack = new MyArrayStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);

        stack.printAll();

        System.out.println("top element is " + stack.pop());
        stack.printAll();
        System.out.println("stack size is " + stack.getSize());
    }
}

– Queue의 특징

  • 맨 앞(front) 에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가 함
  • First In Firts Out (선입선출) 구조
  • 일상 생활에서 일렬로 줄 서 있는 모양
  • 순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용 되는 자료구조
  • 콜센터에 들어온 문의 전화, 메세지 큐 등에 활용됨
  • jdk 클래스 : ArrayList
import ch03.MyLinkedList;
import ch03.MyListNode;

interface IQueue{
    public void enQueue(String data);
    public String deQueue();
    public void printAll();

}
public class MyListQueue extends MyLinkedList implements IQueue {

    MyListNode front;
    MyListNode rear;
    public void MyListQueue(){
        front = null;
        rear = null;
    }
    @Override
    public void enQueue(String data) {
        MyListNode newNode;
        if (isEmpty()){
            newNode = addElement(data);
            front = newNode;
            rear = newNode;
        }
        else {
            newNode = addElement(data);
            rear = newNode;
        }
        System.out.println(newNode.getData() + " added");
    }
    @Override
    public String deQueue() {

        if (isEmpty()){
            System.out.println("Queue is Empty");
            return null;
        }
        String data = front.getData();
        front = front.next;
        if (front == null){
            rear = null;
        }
        return data;
    }
    @Override
    public void printAll(){
      if (isEmpty()){
          System.out.println("Queue is Empty");
          return;
      }
      MyListNode temp = front;
      while (temp != null){
          System.out.print(temp.getData() + ",");
          temp = temp.next;
      }
        System.out.println();
    }
    @Override
    public boolean isEmpty() {
        if (front == null && rear == null){
            return true;
        }
        else return false;
    }
}

public class MyListQueueTest {
    public static void main(String[] args) {
        MyListQueue listQueue = new MyListQueue();
        listQueue.enQueue("A");
        listQueue.enQueue("B");
        listQueue.enQueue("C");
        listQueue.enQueue("D");
        listQueue.enQueue("E");
        listQueue.printAll();

        System.out.println("================");

        System.out.println(listQueue.deQueue());
        System.out.println(listQueue.deQueue());
        System.out.println(listQueue.deQueue());
        System.out.println(listQueue.deQueue());
        System.out.println(listQueue.deQueue());

        listQueue.printAll();

    }
}

1 thought on “[JAVA] 자바의 자료구조 스택(Stack) 과 큐(Queue) 구현하기”

Leave a Comment