본문 바로가기
전산 기초/자료구조

[자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현

은져미 2015. 10. 31. 17:44


[ 스택 (Stack) - 1차원 배열, 연결리스트를 이용한 구현]


"접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조를 말한다"

 

따라서 스택은 시간순서에 따라 자료가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는

후입선출(LIFO, Last-In-First-Out)의 구조를 갖는다.


 


* push 삽입 연산

(1) top = top+1; 으로 삽입 될 위치를 확보

(2) S(top) 가 overflow 가 아니라면 top의 위치에 삽입


* pop 삭제 연산

(1) return S(top); 스택이 공백이 아니라면 top의 위치에 있는 원소 반환

(2) top = top - 1; 제일 위의 원소가 삭제되어 top이 한칸 줄었음을 표시



* 스택을 구현하기 전에 설명할 것이 있다.

Stack 클래스는 LIFO 자료구조를 구현한 클래스로 JAVA에서 '컬렉션 프레임워크' 로 이미 제공해 주고 있다.

JAVA 에는 원하는 타입에 맞게 객체를 생성하여 강제 형변환 문제를 해결해주는 제네릭 <E> 을 제공해 주고 있는데 Stack은 제네릭을 사용한다.


 리턴타입

메소드 

설명 

E

push(E item)

 주어진 객체를 스택에 넣는다. 

E

peek()

 스택의 맨 위 객체를 가져온다. 객체를 스택에서 제거하지 않는다. 

E

pop()

 스택의 맨 위 객체를 가져온다. 객체를 스택에서 제거한다. 


Stack 객체를 생성하기 위해서 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 된다.

Stack<E> stack = new Stack<E>();


하지만 미리 구현되어 있는 Stack 클래스를 사용하지 않고, Stack을 직접 구현해 보도록 하자.

배열과 연결리스트가 공통으로 필요하는 함수들을 interface로 먼저 정의하여 사용한다.



① Stack 인터페이스
1
2
3
4
5
6
7
8
9
10
11
12
Stack.java
 
package Stack;
 
public interface Stack {
    boolean isEmpty();
    void push(char item);
    char pop();
    void delete();
    char peek();
}
 



② 1차원 배열로 구현한 스택

     @Override 가 없는. 즉, 인터페이스에 선언되어 있지 않고 새롭게 작성된 메서드들은 Stack을 배열로 구현할경우에만 필요한 메서드 들이다.
     isFull() 메서드는 배열로 구현하는 경우 배열의 크기가 항상 고정적이기 때문에 스택이 꽉차있는지를 확인하기 위한 메서드 이다.
     연결리스트로 구현하는 경우 스택의 크기를 계속해서 늘릴 수 있기 때문에 isFull() 메서드는 필요하지 않게 된다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
ArrayStack.java
 
package Stack;
 
public class ArrayStack implements Stack{
    private int top;
    private int stackSize;
    private char itemArray[];
    
    public ArrayStack(int stackSize) {
        this.top = -1;
        this.stackSize = stackSize;
        this.itemArray = new char[this.stackSize];
    }
    
    @Override
    public boolean isEmpty() {
        return (top==-1);
    }
    
    public boolean isFull() {
        return (top==stackSize-1);
    }
    
    @Override
    public void push(char item) {
        if(isFull()){
            System.out.println("스택이 꽉차있음");
        }else{
            itemArray[++top] = item;
        }
    }
 
    @Override
    public char pop() {
        if(isEmpty()){
            System.out.println("스택이 비어있음");
            return 0;
        }else{
            return itemArray[top--];
        }
    }
 
    @Override
    public void delete() {
        if(isEmpty()){
            System.out.println("삭제할 요소가 존재하지 않음");
        }else{
            top--;
        }
    }
 
    @Override
    public char peek() {
        if(isEmpty()){
            System.out.println("스택이 비어있음");
        }else{
            return itemArray[top];
        }
        return 0;
    }
    
    public void printStack() {
        if(isEmpty()){
            System.out.println("스택이 비어있음");
        }else{
            System.out.println("<<Stack>>");
            for(int i=top; i>-1; i--){
                System.out.println(itemArray[i]);
            }
            System.out.println();
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Test.java
 
package Stack;
 
public class Test {
    public static void main(String[] args) {
        int stackSize = 5;
        char deletedItem;
        ArrayStack S = new ArrayStack(stackSize);
        
        S.push('A');
        S.printStack();
        
        S.push('B');
        S.printStack();
        
        S.push('C');
        S.printStack();
        
        deletedItem = S.pop();
        if(deletedItem != 0){
            System.out.println("deleted Item : " + deletedItem);
        }
        S.printStack();
    }
}

 



③ 연결리스트로 구현한 스택

     배열로 구현한 스택의 경우 스택의 크기를 변경하기 어렵고, 메모리의 낭비가 생길 수 있다는 단점이 있다.
     연결리스트를 사용하면 이러한 문제점을 해결할 수 있다.

1
2
3
4
5
6
7
8
StackNode.java
 
package Stack;
 
public class StackNode {
    char item;
    StackNode next;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
LinkedStack.java
 
package Stack;
 
public class LinkedStack implements Stack{
    StackNode top;
    
    public LinkedStack() {
        this.top = null;
    }
 
    @Override
    public boolean isEmpty() {
        return (top==null);
    }
 
    @Override
    public void push(char item) {
        StackNode node = new StackNode();
        node.item = item;
        node.next = top;
        top = node;
    }
 
    @Override
    public char pop() {
        if(isEmpty()){
            System.out.println("스택이 비어있습니다.");
            return 0;
        }else{
            StackNode node = top;
            top = node.next;            
            return node.item;
        }
    }
 
    @Override
    public void delete() {
        if(isEmpty()){
            System.out.println("스택이 비어있습니다.");
        }else{
            top = top.next;
        }
    }
 
    @Override
    public char peek() {
        if(isEmpty()){
            System.out.println("스택이 비어있습니다.");
            return 0;
        }else{
            return top.item;
        }
    }
    
    public void printStack() {
        if(isEmpty()){
            System.out.println("스택이 비어있습니다.");
        }else{
            StackNode node = top;
            System.out.println("<<Stack>>");
            while(node.next!=null){
                System.out.println(node.item);
                node = node.next;
            }
            System.out.println(node.item);
            System.out.println();
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LinkedTest.java
 
package Stack;
 
public class LinkedTest {
    public static void main(String[] args) {
        char deletedItem;
        LinkedStack LS = new LinkedStack();
 
        LS.push('A');
        LS.printStack();
 
        LS.push('B');
        LS.printStack();
 
        LS.push('C');
        LS.printStack();
 
        deletedItem = LS.pop();
        if(deletedItem != 0){
            System.out.println("deleted Item : " + deletedItem);
        }
        LS.printStack();
    }
}

 

저작자표시 비영리 동일조건

'전산 기초 > 자료구조' 카테고리의 다른 글

[자료구조/java] 스택의 응용 - 수식의 괄호 검사 (java)  (0) 2015.10.31
[자료구조/java] 스택의 응용 - 역순 문자열 만들기  (0) 2015.10.31
[자료구조/java] 다항식의 연결 자료구조 표현  (0) 2015.10.30
[자료구조/java] 이중 연결 리스트 (Doubly Linked List)  (0) 2015.10.27
[자료구조/java] 원형 연결 리스트 (Circular Linked List)  (0) 2015.10.26

'전산 기초/자료구조' Related Articles

티스토리툴바