강의노트 2강에서는 자료구조 중 Stack과 Queue에 대하여 공부해보고자 합니다.
먼저 Stack에 대하여 알아보겠습니다.
1) 스텍(Stack)
스텍은 자료를 저장하는 방식으로 LIFO 구조를 따릅니다.
LIFO는 Last-In Frist-Out의 약자로 후입선출의 구조입니다.
일상생활에서의 끼우는 형식의 동전지갑이나 트럼프 카드 더미를 생각하시면 이해하시기 편합니다.
출처 : (좌)http://bitly.kr/0jf5lF / (우)http://bitly.kr/TpwPkB
2) Stack Operation
- push(object) : 스텍에 element를 삽입합니다.
- object pop() : 스텍에 있는 element를 제거합니다. // 제일 마지막에 push된 element가 제거됩니다.
- object top() : 스텍 최상단의 element를 보여줍니다.
- integer size() : 스택의 크기를 보여줍니다.
- boolean isEmpty() : 스텍이 비어져있는지 아닌지 판단합니다.
!) Stack Opearation Example
| Operation | Output | In_Stack |
| push(3) | - | (3) |
| push(5) | - | (3, 5) |
| pop() | 5 | (3) |
| push(7) | - | (3, 7) |
| top() | 7 | (3, 7) |
| isEmpty() | false | (3, 7) |
| pop() | 7 | (3) |
| pop() | 3 | () |
| pop() | "error" | () |
자바는 유틸 패키지로 스텍을 지원하기에,
import java.util.Stack; 을 통해 java에서 지원해주는 Stack 자료구조를 사용할 수 있습니다.
하지만 지금은 학습하는 시간이니 Array구조로 된 Stack을 조금 더 공부해보도록 하겠습니다.
* Stack interface
|
1
2
3
4
5
6
7
|
public interface Stack {
public int size();
public boolean isEmpty();
public char top();
public char push(char o);
public char pop();
}
|
cs |
3) Array-based Stack
</alt="JAVA_STACK"p>
위 그림을 예시로 1차원 배열 기반 Stack의 push, pop, size, top에 대하여 알아보겠습니다.
(Stack뿐만 아니라 컴퓨터 자료구조는 0부터 시작함을 유념해야 합니다.)
1차원 배열 Stack은 N을 사이즈로 하는 Array-List를 먼저 선언하여야 합니다.
그리고 Stack에 push될 때마다 element는 0에서부터 N-1까지 자리잡게 됩니다.
반대로 pop될 때는 현재 top의 위치에서 0까지 자료구조에서 빠져나가게 됩니다.
따라서 현재 ArrayList에 Stack이 얼마나 차지하였는지 알기위하여 top의 위치를 반드시 알고있어야 합니다.
top의 위치를 알면 그 다음에 push, pop의 위치를 알 수 있고 Stack의 size도 알 수 있습니다. size = t+1
(Stack이 N-1의 자리까지 모두 차 있을 때 push를 입력한다면 FullStackException, Stack이 현재 비어져있는 상태인데 pop을 입력한다면 EmptyStackException등의 예외처리를 통해 더 좋은 코드를 만들 수 있습니다.)
따라서 Array 기반 Stack을 구축할 때 우리는 처음에 Array의 size를 어떻게 설정할지 고민하여야 합니다.
처음부터 너무 큰 크기의 size를 잡을 경우 메모리 낭비가 심하게 되고,
적은 크기의 size를 잡게 된다면 금방 Stack이 가득 차버려 Resize해줘야하는 번거로움이 생깁니다.
Array-based Stack JAVA Code
|
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
|
public class ArrayStack implements Stack {
private char[] data;
private int top;
public ArrayStack(int size){
this.data = new char[size];
this.top = -1;
}
public int size() {
return this.top +1;
}
public boolean isEmpty() {
return (this.top == -1);
}
public char top() {
return this.data[this.top];
}
public char push(char o) {
this.top++;
this.data[this.top] = 0;
return 0;
}
public char pop() {
char returnC = this.data[this.top];
this.top--;
return returnC;
}
}
|
cs |
4) Linked-List Stack
*Node
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class Node {
private Object data;
private Node nextNode;
public Node(Object data){
this.data = data;
this.nextNode = null;
}
public void linkNode(Node top){
this.nextNode = top;
}
public Object getData(){
return this.data;
}
public Node getNextNode(){
return this.nextNode;
}
}
|
cs |
Linked-List를 활용하여 Stack을 구현할 경우 1차원 배열 기반 Stack에서 가졌던 문제점을 해결할 수 있습니다.
메모리 걱정과 Stack의 용량 걱정을 하지 않는다는 장점을 지닙니다.
연결리스트에서 Stack은 header와 top으로 표현될 수 있습니다.
초기의 header와 top은 아무런 node도 가르키고 있지 않습니다.
이후 첫 번째로 node가 추가되면(push) header와 top모두 push된 node를 가르키게 됩니다.
다음 node가 추가 될 때에는 top은 추가된 node를 가르키고 header는 꼬리에 꼬리를 무는 식으로 가르키게 됩니다.
이후 node가 삭제되면(pop) top과 삭제된 node의 연결관계를 끊고, 이전 header의 node를 가르키게 됩니다.
Linked-List Stack Push&Pop
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public void push(Object item){
Node newNode = new Node(item);
newNode.linkNode(top);
top = newNode;
}
public Object pop(){
if(isEmpty()) {
return 0; // throw Exception
}
else{
Object item = peek();
top = top.getNextNode();
return item;
}
}
|
cs |
5) Parentheses Matching
Stack을 이용하여 괄호 짝 검사를 할 수 있습니다.
괄호 열을 지나며 열린괄호는 stack에 push하고, 닫힌 괄호가 만났을 때 stack을 pop한 후 그 타입을 확인하여 줍니다.
즉, 괄호 짝 검사에서 Stack에 가장 최근에 들어간 열린 괄호와 현재 들어가는 닫힌 괄호는 같은 타입이어야 합니다.
-
{ ( [ ] ) }
-
( ( ) ) ) { ( ) }
-
( { ( ) ] )
-
{ ( ) } [
2번의 경우는 소괄호의 open이 없고, 3번의 경우는 괄호가 맞지 않으며, 4번의 경우는 대괄호의 close가 없습니다.
따라서 1번을 제외하고 모두 Incorrect Parentheses Matching입니다.
!) Case1. Stack Example
괄호 열 : { ( [ ] ) }
| 괄호 | 수행되는 Operation | Stack |
| { | S.push( { ) | ( { ) |
| ( | S.push( ( ) | ( { , ( ) |
| [ | S.push( [ ) | ( { , ( , [ ) |
| ] | S.pop() | ( { , ( ) |
| ) | S.pop() | ( { ) |
| } | S.pop() | - |
Stack이 비어져있는데 pop 명령이 날 경우 : 2번 에러
Stack에서 pop된 결과가 괄호와 타입이 다를 경우 : 3번 에러
괄호 순회가 끝났음에도 불구하고 Stack에 element가 남아있는 경우 : 4번 에러
등의 방식으로 Stack을 활용하여 괄호쌍검사를 진행할 수 있습니다.
Stack : Parentheses Matching Code
|
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
|
// importe java.util.Stack
// 혹은 Stack 직접 구현
public class pM {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
Stack stack = new Stack(input.length());
// 괄호 열 Count
int Count = 0;
for (Count = 0; loopCount < input.length(); Count++) {
char ch = input.charAt(Count);
// isIncorrect = true라면 괄호 짝 매칭 실패
boolean isIncorrect = false;
switch (ch) {
//open 괄호일 경우 stack에 push합니다.
case '(': case '{': case '[':
stack.push(ch);
break;
case ')':
if (stack.isEmpty() || (ch = stack.pop()) != '(') {
isIncorrect = true; // 2,3번 경우의 error
}
break;
case '}':
if (stack.isEmpty() || (ch = stack.pop()) != '(') {
isIncorrect = true; // 2,3번 경우의 error
}
break;
case ']':
if (stack.isEmpty() || (ch = stack.pop()) != '(') {
isIncorrect = true; // 2,3번 경우의 error
}
break;
}
// isIncorrect가 true일 경우 괄호짝 매칭 실패
if(isIncorrect) {
break;
}
}
if(stack.isEmpty() && loopCount == input.length()) {
System.out.println("correct");
}
else {
System.out.println("incorrect"); // 4번 경우의 error
}
}
}
|
cs |
최근댓글