자바 스택, 큐- Array, ArrayList, LinkedList 로 구현

devdo·2022년 2월 15일
스택자바큐
0

자료구조및알고리즘

목록 보기
4/8

Stack

1) 채우다
2) LIFO : Last-In, First-Out

✔ 자바에서 메서드로 활용하기.
push : 데이터 추가
peak : 데이터 확인
pop : 데이터 추출
empty : 비어있는지 확인, (True, False)
clear : 스택 비우기
size : 스택 사이즈 확인
contains : 해당 데이터가 스택에 존재하는 지 확인 (True, False)

import java.util.Stack;

public class StackRealize {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(8);
        stack.push(1);
        stack.push(6);

        stack.peek();
        stack.pop();
        
        System.out.println(stack.size());
        
        stack.empty();
        
        System.out.println(stack.contains(1));
        
        stack.clear();
    }
}

Array(배열)

public class ArrayStack {
 
 private String[] strArray;
 private int maxCount;
 private int top;
 
 private ArrayStack(int maxCount) {
  strArray = new String[maxCount];
  this.maxCount = maxCount;
  this.top = -1;
 }
 
 private void push(String name) {
  if(top < maxCount - 1) {
   strArray[++top] = name;
  } else {
   System.out.println("Stack Full : " + name);
  }
 }
 
 private String peek() {
  if(isEmpty()) {
   System.out.println("데이터 없음");
   return null;
  }
  
  return strArray[top];
 }
 
 private String pop() {
  String name = peek();
  top--;
  return name;
 }
 
 private boolean isEmpty() {
  if(top == -1) {
   return true;
  }
  
  return false;
 }
 
 private void print() {
  for(int i = 0; i < maxCount; i ++) {
   System.out.println(strArray[i]); 
  }
 }

 public static void main(String[] args) {
  ArrayStack arrayStack = new ArrayStack(5);
  
  System.out.println("### push ###");
  arrayStack.push("심준보");
  arrayStack.push("장영운");
  arrayStack.push("황주연");
  arrayStack.push("조우현");
  arrayStack.push("김규섭");
  arrayStack.push("조정은");
 
  arrayStack.print();
  
  System.out.println("### peek ###");
  System.out.println(arrayStack.peek());
  
  System.out.println("### pop ###");
  System.out.println(arrayStack.pop());
  System.out.println(arrayStack.pop());
  System.out.println(arrayStack.pop());
 }
} 

### push ###
Stack Full : 조정은
심준보
장영운
황주연
조우현
김규섭
### peek ###
김규섭
### pop ###
김규섭
조우현
황주연

Process finished with exit code 0

ArrayList

public class MyStack<T> {

    List<T> stack = new ArrayList<>();

    public void push(T item) {
        stack.add(item);
    }

    public T pop() {
        if (stack.isEmpty()) {
            return null;
        }
        return stack.remove(stack.size() - 1);  // 제일 마지막 인덱스
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        MyStack<Integer> ms = new MyStack<>();
        ms.push(1);
        ms.push(2);
        ms.push(3);
        System.out.println(ms.pop());   // 3
        System.out.println(ms.pop());   // 2
        System.out.println(ms.pop());   // 1
        System.out.println(ms.pop());   // null
    }
}

LinkedList(연결리스트)

public class ListStack {
 
 private Node top;
 
 private ListStack() {
  top = null;
 }
 
 class Node {
  String data;
  Node nextNode;
  
  Node(String data) {
   this.data = data;
   nextNode = null;
  }
 }
 
 private void push(String name) {
  Node nowNode = new Node(name);
  nowNode.nextNode = top;
  top = nowNode;
 }

 private String peek() {
  if(isEmpty()) {
   System.out.println("데이터 없음");
   return null;
  }
  
  return top.data;
 }
 
 private String pop() {
  String name = peek();
  top = top.nextNode;
  return name;
 }
 
 private boolean isEmpty() {
  if(top == null) {
   return true;
  }
  
  return false;
 }
 
 public static void main(String[] args) {
  ListStack listStack = new ListStack();
  
  System.out.println("### push ###");
  listStack.push("심준보");
  listStack.push("장영운");
  listStack.push("황주연");
  listStack.push("조우현");
  listStack.push("김규섭");
  listStack.push("조정은");
  
  System.out.println("### peek ###");
  System.out.println(listStack.peek());
  
  System.out.println("### pop ###");
  System.out.println(listStack.pop());
  System.out.println(listStack.pop());
  System.out.println(listStack.pop());  
 }
} 

### push ###
### peek ###
조정은
### pop ###
조정은
김규섭
조우현

Queue

1) 사전상의 정의는 줄, 줄을 서서 기다리다
2) FIFO - First-In, First-Out이라는 의미

✔ Queue 용어 정리

  • enqueue : Queue에 데이터 추가하기
  • Dequeue : Queue에서 데이터 추출하기
  • peek : Queue에서 데이터 확인하기

자바에서 Queue 사용하기
✔ 자바에서 메서드로 활용하기
Enqueue : offer, add
Dequeue : poll, remove
peek : peek, element
API
◾ java.util.LinkedLists
◾ java.util.Queue

import java.util.LinkedList;
import java.util.Queue;

public class Que {
    public static void main(String[] args) {
    
        Queue<String> q = new LinkedList<String>();
        q.offer("강감찬");  // Queue에 데이터 추가							
        q.offer("홍길동");  // Queue에 데이터 추가
        System.out.println(q.size());  // Queue사이즈 확인하기
        
        System.out.println(q.peek()); // Queue에서 데이터 확인하기 (데이터가 Queue에서 꺼내지는 않는다.)
        System.out.println(q.poll()); // Queue에서 데이터 추출하기 (데이터가 Queue에서 꺼내져, Queue에서는 존재하지 않는다.)
		System.out.println(q.size());

        q.offer("이순신");
        q.offer("김구");
        System.out.println(q.size());
        
        // Queue에서 전체 데이터 추출하기 
        while(!q.isEmpty()) {
            System.out.println(q.poll());
        }

    }
}

Array(배열)

public class ArrayQueue {

    private int front;
    private int rear;
    private int maxCount;
    private String[] strArray;

    public ArrayQueue(int maxCount) {
        this.front = 0;
        this.rear  = -1;
        this.maxCount = maxCount;
        strArray = new String[maxCount];
    }

    private void insert(String name) {
        if(isFull()) {
            System.out.println("Queue Full : " + name);
            return;
        }

        strArray[++rear] = name;
    }

    private String peek() {
        if(isEmpty()) {
            System.out.println("데이터 없음");
            return null;
        }
        return strArray[front];
    }

    private String remove() {
        String name = peek();
        front++;

        return name;
    }

    private boolean isFull() {
        if(maxCount == rear + 1) {
            return true;
        }

        return false;
    }

    private boolean isEmpty() {
        if(front == rear + 1 ) {
            return true;
        }

        return false;
    }

    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(5);

        System.out.println("## insert ##");
        arrayQueue.insert("심준보");
        arrayQueue.insert("황주연");
        arrayQueue.insert("장영운");
        arrayQueue.insert("김규섭");

        System.out.println("## peek ##");
        System.out.println(arrayQueue.peek());

        System.out.println("## remove ##");
        System.out.println(arrayQueue.remove());
        System.out.println(arrayQueue.remove());
    }
}


## insert ##
## peek ##
심준보
## remove ##
심준보
황주연

ArrayList

class MyQueue<T> {
    List<T> queue = new ArrayList<>();

    public void enqueue(T item) {
        queue.add(item);
    }

    public T dequeue() {
        if (queue.isEmpty()) {
            return null;
        }
        return queue.remove(0);
    }

    public static void main(String[] args) {
        MyQueue<Integer> mq = new MyQueue<>();
        mq.enqueue(1);
        mq.enqueue(2);
        mq.enqueue(3);

        System.out.println("dequeue check: "+ mq.dequeue());
        System.out.println("dequeue check: "+ mq.dequeue());
        System.out.println("dequeue check: "+ mq.dequeue());
        System.out.println("dequeue check: "+ mq.dequeue());

    }
}

/*
dequeue check: 1
dequeue check: 2
dequeue check: 3
dequeue check: null
*/

LinkedList(연결리스트)

public class ListQueue {

    private Node front;
    private Node rear;

    public class Node {
        String data;
        Node nextNode;

        public Node(String data) {
            this.data = data;
            Node nextNdoe = null;
        }
    }

    public ListQueue() {
        front = null;
        rear  = null;
    }

    private void insert(String data) {
        Node newNode = new Node(data);
        newNode.nextNode = null;

        if(isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.nextNode = newNode;
            rear = newNode;
        }
    }

    private String peek() {
        if(isEmpty()) {
            return null;
        }

        return front.data;
    }

    private String remove() {
        String name = peek();
        front = front.nextNode;

        if(front == null) {
            rear = null;
        }
        return name;
    }

    private boolean isEmpty() {
        if(front == null) {
            return true;
        }

        return false;
    }

    public static void main(String[] args) {
        ListQueue listQueue = new ListQueue();

        System.out.println("## insert ##");
        listQueue.insert("심준보");
        listQueue.insert("황주연");
        listQueue.insert("장영운");
        listQueue.insert("김규섭");
        listQueue.insert("김규섭");

        System.out.println("## peek ##");
        System.out.println(listQueue.peek());

        System.out.println("## remove ##");
        System.out.println(listQueue.remove());
        System.out.println(listQueue.remove());
    }
}


## insert ##
## peek ##
심준보
## remove ##
심준보
황주연

MessageQueue 구현

Message

public class Message {

    private final String command;
    private final String userName;

    public Message(String command, String userName) {
        this.command = command;
        this.userName = userName;
    }

    public String getCommand() {
        return command;
    }

    public String getUserName() {
        return userName;
    }
}

MessageQueue

public class MessageQueue {

    public static void main(String[] args) {
        Queue<Message> mq = new LinkedList<>();

        mq.offer(new Message("sendMail", "dsg1"));
        mq.offer(new Message("sendSMS", "dsg2"));
        mq.offer(new Message("sendKakaotalk", "dsg3"));

        while (!mq.isEmpty()) {
            Message msg = mq.poll();
            switch (msg.getCommand()) {
                case "sendMail":
                    System.out.println(msg.getUserName() + "님에게 메일을 보냅니다.");
                    break;
                case "sendSMS":
                    System.out.println(msg.getUserName() + "님에게 SMS 메시지를 보냅니다.");
                    break;
                case "sendKakaotalk":
                    System.out.println(msg.getUserName() + "님에게 카카오톡 메시지를 보냅니다.");
                    break;
            }
        }
    }
}
profile
devdo
배운 것을 기록합니다.
이전 포스트

Hash(HashTable)의 개념 및 설명

다음 포스트

[알고리즘] 자료구조 시간복잡도 정리

0개의 댓글