[JAVA] 스택(Stack)과 큐(Queue)

//

자바로 배우는 쉬운 자료구조 chap7

//

스택(stack)

• 후입 선출(LIFO : Last In First Out) - 마지막에 삽입된 자료가 가장 먼저 삭제됨.

• top이 가리키고 있는 자료의 위에 새로운 자료가 쌓임 -> top 올라감

• 삭제할 때는 top이 가리키고 있는 스택의 마지막 자료만 삭제.

• top은 0 ~ n-1까지의 인덱스를 저장하므로, 스택이 초기상태(공백 상태)일 때는 -1를 저장함

• push : top을 통한 삽입 연산

• pop : top을 통한 삭제 연산

  package Stack;
  ​
  public interface Stack {
      boolean isEmpty();
      void push(char item);
      char pop();
      void delete();
      char peek();
  }

  
  package Stack;
  ​
  public class ArrayStack implements Stack {
      private int top;
      private int stackSize;
      private char itemArray[];
  ​
      
      public ArrayStack(int stackSize) {
          top = -1;
          this.stackSize = stackSize;
          itemArray = new char[this.stackSize];
      }
  ​
      @Override
      //스택이 공백상태 일 때
      public boolean isEmpty() {
          // TODO Auto-generated method stub
          return (top == -1);
      }
      
      //스택이 가득 찼을 때
      public boolean isFull() {
          // TODO Auto-generated method stub
          return (top == this.stackSize-1);
      }
  ​
      //스택에 데이터 삽입
      @Override
      public void push(char item) {
          // TODO Auto-generated method stub
          if(isFull()){
              System.out.println("Stack is full!!");
          }
          else{
              itemArray[++top] = item;
              System.out.println("Insert item : " + item);
          }
      }
  ​
      //스택에서 삭제할 데이터 반환한 뒤 top--
      @Override
      public char pop() {
          // TODO Auto-generated method stub
          if(isEmpty()){
              System.out.println("Stack is empty!!");
              return 0;
          }
          else{
              return itemArray[top--];
          }
      }
  ​
  ​
      @Override
      public void delete() {
          // TODO Auto-generated method stub
          if(isEmpty()){
              System.out.println("Stack is empty!!");
          }
          else{
              top--;
          }
  ​
      }
  ​
      @Override
      public char peek() {
          // TODO Auto-generated method stub
          if(isEmpty()){
              System.out.println("Stack is empty!!");
              return 0;
          }
          else{
              return itemArray[top];
          }
      }
      
      //출력
      public void printStack(){
          if(isEmpty()){
              System.out.println("Stack is empty!!");
          }
          else{
              System.out.printf("Array Stack>> ");
              for (int i = 0; i <= top; i++){
                  System.out.printf("%c", itemArray[i]);
              }
              System.out.println();
          }
          System.out.println();
      }
  }

  
  package Stack;
  ​
  public class StackMain {
  ​
      public static void main(String[] args) {
          // TODO Auto-generated method stub
          int stackSize = 5;
          char deleteItem;
          
          ArrayStack arr = new ArrayStack(stackSize);
          
          arr.push('A');
          arr.printStack();
          
          arr.push('B');
          arr.printStack();
          
          arr.push('C');
          arr.printStack();
          
          deleteItem = arr.pop();
          System.out.println("deleted item : " +deleteItem);
          arr.printStack();
      }
  }

• 스택의 LIFO 성질을 이용하여 역순 문자열 간단히 만들 수 있음.

//

자바로 배우는 쉬운 자료 구조 chap 8

//

큐(Queue)

• FIFO(First In First Out, 선입선출)

• front : 첫 번째 원소 - 삭제 연산 수행

• rear : 마지막 원소 - 삽입 연산 수행

• 공백 큐 일 때 front = rear, 초기 상태의 공백 큐는 front = rear = -1

  데이터 삽입되면 rear 오른쪽으로 이동, 데이터 삭제되면 front 오른쪽으로 이동

  ​

  package Queue;
  ​
  public interface Queue {
      boolean isEmpty();
      //원소 삽입
      void enQueue(char item);
      //원소 삭제
      char deQueue();
      void delete();
      char peek();
  }

  
  package Queue;
  ​
  public class ArrayQueue {
      private int front;
      private int rear;
      private int queueSize;
      private char[] itemArray;
      
      public ArrayQueue(int queueSize) {
          front = -1;
          rear = -1;
          this.queueSize = queueSize;
          itemArray = new char[this.queueSize];
      }
      
      public boolean isEmpty(){
          return rear == front;
      }
      
      public boolean isFull(){
          return rear == this.queueSize -1;
      }
      
      //삽입
      public void enQueue(char item){
          if(isFull()){
              System.out.println("Array Queue is full!!");
          }
          else{
              itemArray[++rear] = item;
              System.out.println("Inserted Item : "+item);
          }
      }
      
      //삭제
      public char deQueue(){
          if(isEmpty()){
              System.out.println("Array Queue is empty!!");
              return 0;
          }
          else{
              return itemArray[++front];
          }
      }
      
      public void delete(){
          if(isEmpty()){
              System.out.println("Array Queue is empty!!");
          }
          else{
              ++front;
          }
      }
      
      public char peek(){
          if(isEmpty()){
              System.out.println("Array Queue is empty!!");
              return 0;
          }
          else{
              return itemArray[front+1];
          }
      }
      
      public void printQueue(){
          if(isEmpty()){
              System.out.println("Array Queue is empty!!");
          }
          else{
              System.out.println("Array Queue >> ");
              for(int i = front+1; i <= rear; i++){
                  System.out.printf("%c ", itemArray[i]);
              }
              System.out.println();
          }
          System.out.println();
      }
      
  }

  
  package Queue;
  ​
  public class QueueMain {
  ​
      public static void main(String[] args) {
          // TODO Auto-generated method stub
          int queueSize = 3;
          char deletedItem;
          ArrayQueue arr = new ArrayQueue(queueSize);
          
          arr.enQueue('A');
          arr.printQueue();
          
          arr.enQueue('B');
          arr.printQueue();
          
          deletedItem = arr.deQueue();
          if(deletedItem != 0){
              System.out.println("deleted Item :" + deletedItem);
          }
          arr.printQueue();
          
          
          arr.enQueue('C');
          arr.printQueue();
          
          deletedItem = arr.deQueue();
          if(deletedItem != 0){
              System.out.println("deleted Item :" + deletedItem);
          }
          arr.printQueue();
          
          arr.enQueue('C');
          arr.printQueue();
      }
  ​
  }