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

자바에서 스택(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());

}

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()); } }

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());

listQueue.printAll();

}

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(); } }

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();

    }
}

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

– Stack의 특징

– Queue의 특징

“[JAVA] 자바의 자료구조 스택(Stack) 과 큐(Queue) 구현하기”에 대한 1개의 생각

댓글 남기기 응답 취소