자료구조 09 - 스택과 큐(1)

 스택(Stack) - 데이터를 임시저장 하기위한 것으로

LIFO(Last In First Out) - 마지막에 집어넣은 데이터를 가장먼저 뽑아 오는것

(자바 프로그램에서 메소드 호출하고 실행할때 프로그램 내부에선 스택을 사용함)

 

큐 (Queue) - 데이터 임시저장 하기위한것으로

FIFO(First In First Out) - 처음에 집어넣은 데이터가 제일먼저 나옴 

 

스택의 대표적 예시 로는

실행취소(ctrl + z) , 인터넷 이전페이지로 이동 등이 있음

 

아래는 스택과 큐를 그림으로 설명해 본것이다.

다음은 스택클래스를 구현하기위해 필요한 것들이다.

-인스턴스 변수

pointer - index의 위치  

max - 스택 용량

 

-클래스 메소드

생성자

 

-인스턴스 메소드

push  - 데이터 입력

pop - 데이터 출력

peek - 스택의 꼭대기 데이터

index - 검색을 통한 key값의 index찾기

clear - 스택 모든요소 제거 -> 데이터를 지우는게 아니라 스택을지운다.

capacity - 스택의 용량확인

size - 데이터의 수 확인

 

위의 것을 기반으로 스택클래스를 구현해 보겠다

 

public class stack_exercise{

           int pointer;

           int max;                                인스턴스 변수

           int[] stack;

 

           public stack_exercise(int pointer, int max, int[] stack){

                     this.pointer = pointer;

                     this.max = max;                                            생성자

                     this.stack = stack;

           }

 

           public void push(int x){

                     stack[pointer++] = x;

           }

 

           public void pop(){

                      pointer--;

           }

 

           public int peek(){

                     pointer--;

           }

 

           public int index(int key){

                     for(int i = 0; i<=pointer; i++){

                                if(stack[i] == key)

                                          return i;

                    }

 

                     return -1;  ==> 예외처리를 위한 결과값 

           }

 

           public void clear(){

                     pointer = 0;

           }

 

           public int capacity(){

                     return max;

           }

 

           public int size(){

                      return pointer;

           }

           

           public void show_stack(){

                     if(pointer<=0)  

                                System.out.println("스택 비어있음" )  ==> 예외처리로 사용함

                     else{

                               for(int i =0; i<pointer; i++){

                                           System.out.print(stack[i] + " ");

                                }

                                System.out.println(" ");

                   }

           }

           public static void main(Strings[] args){

                     int[] A = new int[32];

                     stack_exercise test_Stack = new stack_exercise(0,A.legnth,A);

                     test_stack.push(1);

                     test_stack.show_stack();

                     test_stack.push(2);

                     test_stack.show_stack();

                     test_stack.push(3);

                     test_stack.show_stack();

                     System.out.println("peek = " + test_stack.peek());

                     System.out.println("size = " + test_stack.size());

                     test_stack.pop();

                     test_stack.show_stack();

                     System.out.println("");

                     test_stack.clear();

                     test_stack.show_stack();

           }

}

 

아래는 위코드의 실행 결과를 보여준다.

stack_exercise.java

0.00MB

 

 

스택 코드를 작성해 보았다

pointer가 중요한 역활을 한다 -> pointer의 위치가 데이터의 삽입위치를 말해주고 MAX 크기와 비교해 용량까지 체크하는데 쓰이기 때문

 

하지만 위의 코드는 문제가 있는데 

push, pop, peek 메소드에 문제가 존재한다

-> 위의코드에서 push pop peek메소드 내부에 스택이 비어있는경우 꽉찬경우에 대한 예외처리를 해주지 않았기 떄문이다

그래서 아래에 메소드를 다시 수정한것을 나타낸 것이다.

 

 

다음시간은 큐(Queue)에 대해서 코드를 작성해보겠다.