2023. 12. 20. 22:02ㆍ프로그래밍 공부/Data Structure
5.1 스택
스택(stack): 선출후입(LIFO, Last-in First-out) 원리에 따라 삽입되고 제거되는 객체들의 집합
객체들은 언제든지 스택에 삽입될 수 있지만,
가장 최근에 삽입된 객체(즉, "마지막" 객체)만 언제든지 제거될 수 있다.
"스택"이라는 이름은 스프링이 장착된 구내식당 접시 디스펜서에 접시를 쌓아놓은 은유에서 유래되었다.
이 경우 기본적인 작업은 스택에 있는 접시들의 "pushing"와 "popping"를 포함한다.
우리가 디스펜서에서 새 접시가 필요할 때,
우리는 위의 접시를 "pop"하고, 접시를 추가할 때,
우리는 그것을 스택에서 "push" 내려 새로운 위의 접시가 된다.
아마도 더 재미있는 비유는 PEZ®캔디 디스펜서일 것인데,
이것은 민트 사탕을 스프링이 장착된 용기에 저장하고 디스펜서의 상단이 들어올려지면
가장 많은 사탕을 "pops"한다.
(그림 5.1 참조) 스택은 기본적인 자료 구조이다.
스택은 다음을 포함한 많은 응용 분야에서 사용된다.
그림 5.1: PEZ® 디스펜서의 개략도;
스택 ADT의 물리적 구현(PEZ®는 PEZ Candy, Inc.의 등록 상표임)
예 5.1: 인터넷 웹 브라우저는 최근에 방문한 사이트의 주소를 스택에 저장한다.
사용자가 새로운 사이트를 방문할 때마다, 그 사이트의 주소는 주소 스택에 "push"된다.
그리고 나서 브라우저는 사용자가 "뒤로" 버튼을 사용하여
이전에 방문한 사이트로 "pop" 다시 돌아갈 수 있도록 허용한다.
예제 5.2: 텍스트 편집기는 일반적으로 최근 편집 작업을 취소하고
문서의 이전 상태로 되돌리는 "undo" 메커니즘을 제공한다.
이 언도 작업은 텍스트 변경 사항을 스택에 유지함으로써 수행할 수 있다.
5.1.1 스택 추상 데이터 타입
스택은 모든 데이터 구조 중에서 가장 단순하지만
더 복잡한 데이터 구조를 포함하는 다양한 응용 분야에서 사용되기 때문에
가장 중요한 구조 중 하나이기도 한다.
형식적으로 스택은 다음 두 가지 방법을 지원하는 추상 데이터 타입(ADT)이다:
push(e) : e 요소를 삽입하여 스택의 상단이 되도록 한다.
pop(): 스택에서 제거하고 스택의 맨 위 요소를 반환힌다.
스택이 비어 있으면 오류가 발생한다.
추가적으로 다음과 같은 방법도 정의해 보겠다:
size(): 스택의 요소 수를 반환한다.
is Empty(): 스택이 비어 있는지를 나타내는 부울을 반환한다.
top(): 스택의 맨 위 요소를 제거하지 않고 반환한다.
스택이 비어 있으면 오류가 발생한다.
예제 5.3: 다음 표는 일련의 스택 연산과 초기 빈 정수 스택 S에 대한 영향을 보여준다.
| 연산 | 출력 | 스택 내용물 |
| push(5) | - | (5) |
| push(3) | - | (5, 3) |
| pop() | 3 | (5) |
| push(7) | - | (5, 7) |
| pop() | 7 | (5) |
| top() | 5 | (5) |
| pop() | 5 | () |
| pop() | "error" | () |
| isEmpty() | true | () |
| push(9) | - | (9) |
| push(7) | - | (9, 7) |
| push(3) | - | (9, 7, 3) |
| push(5) | - | (9, 7, 3, 5) |
| size() | 4 | (9, 7, 3, 5) |
| pop() | 5 | (9, 7, 3) |
| push(8) | - | (9, 7, 3, 8) |
| pop() | 8 | (9, 7, 3) |
| pop() | 3 | (9, 7) |
자바의 스택 인터페이스
그 중요성 때문에 스택 자료 구조는 자바의 java.util 패키지에 "built-in" 클래스로 포함된다.
class java.util.Stack은 일반적인 자바 개체를 저장하는 자료 구조로서
메소드 push(), pop(), peek()(top()과 동일함), size(), empty() 등을 포함한다.
메소드 pop()과 peek()은 빈 스택에서 호출되는 경우 예외 EmptyStackException을 던진다.
기본 제공 클래스 java.util.Stack을 사용하는 것이 편리하지만
"처음부터" 스택을 설계하고 구현하는 방법을 배우는 것이 유용한다
자바에서 추상적인 데이터 타입을 구현하는 것은 두 단계를 포함한다.
1. 단순히 인터페이스인
자바 응용 프로그램 프로그래밍 인터페이스
(Application Programming Interface, API)의 정의로,
ADT가 지원하는 메소드의 이름과 이를 선언하고 사용하는 방법을 설명한다.
2. 발생할 수 있는 모든 오류 조건에 대한 예외를 정의해야 한다.
예를 들어 빈 스택에서 메소드 pop() 또는 top()을 호출할 때
발생하는 오류 조건은 코드 조각 5.1에 정의된
EmptyStackException 타입의 예외를 던져서 시그널링된다.
코드 조각 5.1: 빈 스택에서 호출될 때
스택 인터페이스의 메소드 pop() 및 top()에 의해 버려지는 예외.
/**
* Runtime exception thrown when one tries to perform operation top ㅐㄱ
* pop on an empty stack.
*/
public class EmptyStackException extends RuntimeException {
public EmptyStackException(String err) {
super(err);
}
}
스택 ADT에 대한 완전한 자바 인터페이스는 코드 조각 5.2에 나와 있다.
이 인터페이스는 임의의 주어진 클래스(및 그 서브클래스)의 요소를
스택에 삽입할 수 있음을 지정하기 때문에 매우 일반적이다.
일반성(generic)의 개념을 사용하여 이 일반성을 달성한다(섹션 2.5.2).
주어진 ADT가 어떤 용도로 쓰이려면,
우리는 그 ADT와 관련된 인터페이스의 방법들을 구현하는 구체적인 클래스를 제공해야 한다.
우리는 Stack 인터페이스의 간단한 구현을 다음 하위 절에서 제공한다.
코드 조각 5.2: 자바독 스타일로 주석이 달린 인터페이스 Stack(섹션 1.9.3).
또한 일반 매개 변수화된 타입 E를 사용하는 것을 참고하자.
스택은 지정된 클래스의 요소를 포함할 수 있음을 의미한다.
/**
* Interface for a stack: a collection of objects that are inserted
* and removed according to the last-in first-out principle. This
* interface includes the main methods of java.util.Stack.
*
* @author Roberto Tamassia
* @author Michael Goodrich
* @see EmptyStackException
*/
public interface Stack<E> {
/**
* Return the number of elements in the stack.
* @return number of elements in the stack.
*/
public int size();
/**
* Return whether the stack is empty.
* @return true if the stack is empty, false otherwise.
*/
public boolean isEmpty();
/**
* Inspect the element at the top of the stack.
* @return the top element in the stack.
* @exception EmptyStackException if the stack is empty.
*/
public E top()
throws EmptyStackException;
/**
* Insert an element at the top of the stack.
* @param element to be inserted.
*/
public void push (E element);
/**
* Remove the top element from the stack.
* @return element removed.
* @exception EmptyStackException if the stack is empty.
*/
public E pop()
throws EmptyStackException;
}
5.1.2 간단한 배열 기반 스택 구현
우리는 스택의 요소들을 배열에 저장함으로써 스택을 구현할 수 있다.
구체적으로, 이 구현에서의 스택은
N개의 요소 배열 S와 배열 S의 최상위 요소의 인덱스를 제공하는 정수 변수 t로 구성된다(그림 5.2 참조)
그림 5.2: 배열 S로 스택 구현. 스택의 최상위 요소는 셀 S[t]에 저장된다.
자바에서 배열이 인덱스 0에서 시작한다는 것을 상기시켜 보면,
우리는 t를 -1로 초기화하고, 우리는 이 값을 t에 사용하여 빈 스택을 식별한다.
마찬가지로, 우리는 t를 사용하여 요소의 수 (t + 1)를 결정할 수 있다.
또한 FullStackException이라는 새로운 예외를 도입하여
새 요소를 가득 찬 배열에 삽입하려고 할 때 발생하는 오류를 알려쥰다.
예외 FullStackException은 이 구현에만 해당되며 스택 ADT에는 정의되지 않는다.
저희는 코드 조각 5.3에 배열 기반 스택 구현에 대한 자세한 내용을 제공한다.
코드 조각 5.3: 주어진 크기 N의 배열을 사용하여 스택을 구현하는 것.
Algorithm size():
return t + 1
Algorithm isEmpty():
return (t < 0)
Algorithm top():
if isEmpty() then
throw a EmptyStackException
return S[t]
Algorithm push(e):
if size() = N then
throw a FullStackException
t ← t + 1
S[t] ← e
Algorithm pop():
if isEmpty() then
throw a EmptyStackException
e ← S[t]
S[t] ← null
t ← t - 1
return e
배열 기반 스택 구현 분석
배열 기반 구현에서 메소드의 정확성은 메소드 자체의 정의로부터 바로 이어진다.
그럼에도 불구하고 여기서 pop 메소드의 구현과 관련된 약간의 흥미로운 점이 있다.
이전 S[t]를 null로 재설정하는 것을 피할 수 있었지만 여전히 올바른 메소드가 있을 것이다.
그러나 이러한 알고리즘을 자바로 구현하는 것을 고려하고 있다면
이 할당을 피할 수 있다는 상충 관계가 있다.
상충 관계에는 자바 가비지 컬렉션(garbage collection) 메커니즘이 포함된다.
가비지 컬렉션: 활성 객체가 더 이상 참조하지 않는 객체에 대한 메모리를 검색하고 나중에 사용할 수 있도록 공간을 재확보한다.
(자세한 내용은 14.1.3절 참조)
pop 메소드를 호출하기 전에 e = S[t]를 최상위 요소로 설정한다.
S[t]를 null 참조로 지정함으로써
스택이 더 이상 객체 e에 대한 참조를 보유할 필요가 없음을 나타낸다.
실제로 e에 대한 다른 활성 참조가 없으면 가비지 컬렉터가 e가 사용한 메모리 공간을 회수한다.
표 5.1은 배열에 의한 스택의 구현에서 메소드들의 실행 시간을 보여준다.
배열 구현에서 각 스택 메소드들은
산술 연산, 비교, 할당 등을 포함하는 일정한 수의 문들을 실행한다.
또한 pop은 isEmpty를 호출하며, 이 자체는 일정한 시간 안에 실행된다.
따라서 이번 스택 ADT 구현에서는
각 메소드들이 일정한 시간 안에 실행되며, 즉 O(1) 시간 안에 실행된다.
표 5.1: 배열로 구현된 스택의 성능.
공간 사용량은 O(N)이며,
여기서 N은 배열의 크기로 스택을 인스턴스화할 때 결정된다.
공간 사용량은 실제로 스택에 있는 요소의 수 n ≤ N 과는 무관하다는 점에 유의하자.
| 메소드 | 시간 |
| size | O(1) |
| isEmpty | O(1) |
| top | O(1) |
| push | O(1) |
| pop | O(1) |
코드 조각 5.3의 의사 코드와 자바 클래스 ArrayStack이
Stack 인터페이스를 구현하는
구체적인 자바 구현은 코드 조각 5.4 및 5.5에 나와 있다.
안타깝게도 공간 문제로 인해 이 부분과 이 책의 나머지 부분에 나와 있는
대부분의 자바 코드 조각에 대한 대부분의 자바독 코멘트는 생략한다.
배열의 용량을 지정하기 위해 CAPACITY라는 기호 이름을 사용한다.
이를 통해 코드 한 곳에 배열의 용량을 지정하고 전체에 해당 값을 반영할 수 있다.
코드 조각 5.4-5.5:
스택 인터페이스의 배열 기반 자바 구현
/**
* Implementation of the stack ADT using a fixed-length array. An
* exception is thrown if a push operation is attempted when the size
* of the stack is equal to the length of the array. This class
* includes the main methods of the built-in class java.util.Stack.
*/
public class ArrayStack<E> implements Stack<E> {
protected int capacity; // The actual capacity of the stack array
public static final int CAPACITY = 1000; // default array capacity
protected E S[]; // Generic array used to implement the stack
protected int top = -1; // index for the top of the stack
public ArrayStack() {
this(CAPACITY); // default capacity
}
public ArrayStack(int cap) {
capacity = cap;
S = (E[]) new Object[capacity]; // compiler may give warning, but this is ok
}
public int size() {
return (top + 1);
}
public boolean isEmpty() {
return (top < 0);
}
public void push(E element) throws FullStackException {
if (size() == capacity)
throw new FullStackException("Stack is full.");
S[++top] = element;
}
public E top() throws EmptyStackException {
if (isEmpty())
throw new EmptyStackException("Stack is empty.");
return S[top];
}
public E pop() throws EmptyStackException {
E element;
if (isEmpty())
throw new EmptyStackException("Stack is empty.");
element = S[top];
S[top--] = null; // dereference S[top] for garbage collection.
return element;
}
public String toString() {
String s;
s = "[";
if (size() > 0) s += S[0];
if (size() > 1)
for (int i = 1; i <= size()-1; i++) {
s += ", " + S[i];
}
return s + "]";
}
// Prints status information about a recent operation and the stack.
public void status(String op, Object element) {
System.out.print("------> " + op); // print this operation
System.out.println(", returns " + element); // What was returned
System.out.print("result: size = " + size() + ", isEmpty = " + isEmpty());
System.out.println(", stack: " + this); // contents of the stack
}
/**
* Test our program by performing a series of operations on stacks,
* printing the operations performed, the returned elements and the
* contents of the stack involved, after each operation.
*/
public static void main(String[] args) {
Object o;
ArrayStack<Integer> A = new ArrayStack<Integer>();
A.status("new ArrayStack<Integer> A", null);
A.push(7);
A.status("A.push(7)", null);
o = A.pop();
A.status("A.pop()", o);
A.push(9);
A.status("A.push(9)", null);
o = A.pop();
A.status("A.pop()", o);
ArrayStack<Integer> B = new ArrayStack<Integer>();
B.status("new ArrayStack<Integer> B", null);
B.push("Bob");
B.status("B.push(\"Bob\")", null);
B.push("Alice");
B.status("B.push(\"Alice\")", null);
o = B.pop();
B.status("B.pop()", o);
B.push("Eve");
B.status("B.push(\"Eve\")", null);
}
}
예제 출력
아래는 위의 ArrayStack 프로그램의 출력을 보여준다.
일반적인 타입을 사용하여 정수를 저장하는 ArrayStack A와
문자열을 저장하는 ArrayStack B를 만들 수 있다.
------> new ArrayStack<Integer> A, returns null
result: size = 0, isEmpty = true, stack: []
------> A.push(7), returns null
result: size = 1, isEmpty = false, stack: [7]
------> A.pop(), returns 7
result: size = 0, isEmpty = true, stack: []
------> A.push(9), returns null
result: size = 1, isEmpty = false, stack: [9]
------> A.pop(), returns 9
result: size = 0, isEmpty = true, stack: []
------> new ArrayStack<String> B, returns null
result: size = 0, isEmpty = true, stack: []
------> B.push("Bob"), returns null
result: size = 1, isEmpty = false, stack: [Bob]
------> B.push("Alice"), returns null
result: size = 2, isEmpty = false, stack: [Bob, Alice]
------> B.pop(), returns Alice
result: size = 1, isEmpty = false, stack: [Bob]
------> B.push("Eve"), returns null
result: size = 2, isEmpty = false, stack: [Bob, Eve]
배열 기반 스택 구현의 단점
스택의 배열 구현은 간단하고 효율적이다.
그럼에도 불구하고 이 구현에는 한 가지 부정적인 측면이 있다.
스택의 궁극적인 크기에 고정된 상한인 CAPICTY를 가정해야 한다.
코드 조각 5.4에서는 용량 값을 1,000개 이상 또는 그 이하로 임의로 선택했다.
애플리케이션은 실제로 이보다 훨씬 적은 공간을 필요로 하기 때문에 메모리를 낭비하게 될 수 있다.
또는 이보다 더 많은 공간이 필요한 애플리케이션은
클라이언트 프로그램이 1,001번째 개체를 스택에 푸시하려고 시도하는 즉시 예외가 발생할 수 있다.
따라서 단순성과 효율성에도 불구하고 배열 기반 스택 구현이 반드시 이상적인 것은 아니다.
다행히 다음에 논의할 또 다른 구현예는 크기 제한이 없고
실제 스택에 저장된 요소의 수에 비례하는 공간을 사용하는 것이다.
하지만 스택에 필요한 항목의 수를 충분히 추정한 경우에는 배열 기반 구현을 능가하기 어렵다.
스택은 여러 컴퓨팅 애플리케이션에서 중요한 역할을 하므로
간단한 배열 기반 구현과 같이 빠른 스택 ADT 구현이 도움이 된다.
5.1.3 일반 연결 리스트를 통한 스택 구현
이 절에서는 스택 ADT를 구현하기 위해 단일 연결 리스트를 사용하는 방법을 알아본다.
그런 구현을 설계할 때 스택의 맨 위가 리스트의 맨 위에 있는지 아니면 맨 뒤에 있는지 결정해야 한다.
하지만 일정한 시간에 요소를 삽입하고 삭제할 수 있기 때문에
여기서는 분명히 최선의 선택이 있다.
따라서 스택의 맨 위가 리스트의 맨 위에 있는 것이 더 효율적이다.
또한 일정한 시간에 연산 크기를 수행하기 위해 인스턴스 변수의 현재 요소 수를 추적한다.
3.2절에서 보여준 것처럼
특정 종류의 객체만 저장할 수 있는 연결 리스트를 사용하는 것보다는
일반(generic) 연결 리스트를 사용하여 일반 스택을 구현하고자 한다.
따라서 이 연결 리스트를 구현하기 위해서는 일반적인 종류의 노드를 사용해야 한다.
코드 조각 5.6에서 이러한 Node 클래스를 보여준다.
코드 조각 5.6: 클래스 Node. 단일 연결 리스트에 대한 일반 노드를 구현한다.
public class Node<E> {
// Instance variables:
privae E element;
private Node<E> next;
/** Creates a node with null references to its element and next node */
public Node() {
this(null, null);
}
/** Creates a node with the given element and next node */
public Node(E e, Node<E> n) {
element = e;
next = n;
}
// Accessor methods:
public E getElement() {
return element;
}
public Node<E> getNext() {
return next;
}
// Modifier methods:
public void setElement(E newElem) {
element = newElem;
}
public void setNext(Node<E> newNext) {
next = newNext;
}
}
일반 NodeStack 클래스
일반적인 단일 연결 리스트를 통한 스택의 자바 구현은 코드 조각 5.7에 나와 있다.
Stack 인터페이스의 모든 메소드는 일정한 시간에 실행된다.
이 연결 리스트 구현에는 시간 효율적일 뿐만 아니라 공간 요구 사항인 O(n)이 있으며,
여기서 n은 스택의 현재 요소 수이다.
따라서 이 구현에서는 크기 오버플로우 문제를 처리하기 위해
새로운 예외를 만들 필요가 없다.
인스턴스 변수 top을 사용하여
리스트의 헤드 부분을 참조한다.
(리스트가 비어 있으면 null 개체를 가리킨다)
스택에서 새 요소 e를 푸시(push)할 때
e에 대한 새 노드 v를 생성하고
v에서 참조한 다음 리스트의 맨 위에 v를 삽입한다.
마찬가지로, 스택에서 요소를 팝(pop)할 때
단순히 리스트의 맨 위에 있는 노드를 제거하고 해당 요소를 반환한다.
따라서 리스트의 맨 위에 모든 요소를 삽입하고 제거한다.
코드 조각 5.7: 클래스 NodeStack.
단일 연결 리스트을 사용하여 Stack 인터페이스를 구현하는 클래스 NodeStack.
노드는 코드 조각 5.6의 클래스 Node 객체이다.
public class NodeStack<E> implements Stack<E>{
private Node<E> top; // reference to the head node
protected int size; // number of elements in the stack
public NodeStack() { // constructs an empty stack
top = null;
size = 0;
}
public int size() { return size; }
public boolean isEmpty() {
if (top = null) return true;
return false;
}
public void push(E elem) {
Node<E> v = new Node<E>(elem, top); // create and link-in a new node
top = v;
size++;
}
public E top() throws EmptyStackException{
if (isEmpty()) throw new EmptyStackException("Stack is empty.");
return top.getElement();
}
public E pop() throws EmptyStackException{
if (isEmpty()) throw new EmptyStackException("Stack is empty.");
E temp = top.getElement();
top = top.getNext(); //link-out the former top node
size--;
return temp;
}
}
5.1.4 스택을 이용한 배열 반전
스택을 사용하여 배열의 원소들을 역방향으로 되돌릴 수 있으며,
따라서 3.5.1절에서 소개한 배열-역방향 문제에 대한 비재귀적 알고리즘을 생성할 수 있다.
기본 아이디어는 단순히 배열의 모든 원소들을 순서대로 스택에 밀어 넣은 다음,
그 원소들을 스택에서 터뜨려 배열을 다시 채우는 것이다.
코드 조각 5.8에서는 이 알고리즘을 자바로 구현한 것을 소개한다.
또한 이 메소드는 일반 스택을 사용하는 간단한 응용 프로그램에서
일반 타입을 사용하는 메소드도 보여준다.
특히 이 예제에서 요소들이 스택에서 pop되면
E 타입의 요소로 자동 반환되므로 즉시 입력 배열로 반환될 수 있다.
코드 조각 5.9에서는 이 메소드의 예제를 보여준다.
코드 조각 5.8: Stack<E> 인터페이스를 사용하여 선언된 스택을 사용하여
E 타입 객체 배열의 요소를 반전시키는 제너릭 메소드.
/** A nonrecursive generic method for reversing an array */
public static <E> void reverse(E[] a) {
Stack<E> S = new ArrayStack<E>(a.length);
for (int i = 0; i < a.length; i++)
S.push(a[i]);
for (int i = 0; i < a.length; i++)
a[i] = S.pop();
}
코드 조각 5.9: 두 개의 배열을 사용한 reverse 메소드의 테스트.
/** Tester routine for reversing arrays */
public static void main(String[] args) {
Integer[] a = {4, 8, 15, 16, 23, 42}; // autoboxing allows this
String[] s = {"Jack", "Kate", "Hurley", "Jin", "Boone"};
System.out.println("a = " + Arrays.toString(a));
System.out.println("s = " + Arrays.toString(s));
System.out.println("Reversing...");
reverse(a);
reverse(s);
System.out.println("a = " + Arrays.toString(a));
System.out.println("s = " + Arrays.toString(s));
}The output from this method is the following:
a = [4, 8, 15, 16, 23, 42]
s = [Jack, Kate, Hurley, Jin, Michael]
Reversing...
a = [42, 23, 16, 15, 8, 4]
s = [Michael, Jin, Hurley, Kate, Jack]
5.1.5 괄호와 HTML 태그 일치
이 하위 섹션에서는 스택의 두 가지 관련 응용 프로그램을 살펴보며,
첫 번째는 산술 표현에서 괄호를 일치시키고 기호를 그룹화하기 위한 것이다.
산술 표현식에는 다음과 같은 다양한 그룹화 기호 쌍이 포함될 수 있다
• 소괄호 : "(" 및 ")"
• 중괄호: "{" 및 "}"
• 대괄호: "[" 및 "]"
• 바닥 함수 기호: "⌊" 및 "⌋"
• 천장 함수 기호: "⌈" 및 "⌉",
그리고 각 열림 기호는 해당 닫힘 기호와 일치해야 한다.
예를 들어, 왼쪽 괄호 "["는 해당 오른쪽 괄호 "]"와 일치해야 한다:
[(5 + x) - (y + z)].
다음 예에서는 이 개념에 대해 자세히 설명한다:
• 정답: ( )(( )){([( )])}
• 정답: ((( )(( )){([( )])}))
• 틀렸다: )(( )){([( )])}
• 틀렸다: ({[])}
• 틀렸다: (.
괄호 일치 알고리즘
산술 식을 처리할 때 중요한 문제는 그룹화 기호들이 정확하게 일치하는지 확인하는 것이다.
우리는 스택 S를 사용하여 한 번의 좌우 스캔으로 산술식을 그룹화 기호들의 일치를 수행할 수 있다.
알고리즘은 왼쪽과 오른쪽 기호가 일치하는지,
또한 왼쪽과 오른쪽 기호가 모두 같은 타입인지 테스트한다.
우리에게 수열 X = x0x1x2...xn-1이 주어졌다고 하자.
여기서 각 xi는 그룹화 기호, 변수 이름, 연산자 또는 숫자가 될 수 있는 토큰이다.
S의 그룹화 기호들이 정확하게 일치하는지 확인하는 기본 아이디어는
순서대로 토큰을 처리하는 것이다.
여는 기호를 만날 때마다 S 위로 밀고,
닫는 기호를 만날 때마다 스택 S에서 맨 위 기호를 터뜨려
이 두 기호가 같은 종류인지 확인한다
(S는 비어 있지 않고 추정한다).
전체 수열을 처리한 후 스택이 비어 있으면 X의 기호들이 일치한다.
push와 pop 연산이 일정한 시간에서 실행되도록 구현되었다고 가정하면,
이 알고리즘은 O(n), 즉 선형 시간에서 실행된다.
코드 조각 5.10에서 이 알고리즘에 대한 의사 코드 설명을 제공한다.
코드 조각 5.10: 산술식에서 그룹화 기호를 일치시키는 알고리즘.
Algorithm ParanMatch(X, n):
Input: An array X of n tokens, each of which is either a grouping, a variable, an arithmetic operator, or a number
Output: true if and only if all the grouping symbols in X match
Let S be an empty stack
for i ← 0 to n - 1 do
if X[i] is an opening grouping symbol then
S.push(X[i])
else if X[i] is a closing grouping symbol then
if S.isEmpty() then
return false {nothing to match with}
if S.pop() does not match the type of X[i] then
return false {wrong type}
if S.isEmpty() then
return true {every symbol matched}
else
return false {some symbols were never matched}
HTML 문서의 태그 일치
매칭이 중요한 또 다른 응용 프로그램은 HTML 문서의 유효성 검사이다.
HTML: 인터넷 상에서 하이퍼링크된 문서의 표준 형식
HTML 문서에서 텍스트의 일부는 HTML 태그(HTML tag)로 구분된다.
간단히 여는 HTML 태그는 "<name>" 형태를 가지며,
해당 닫는 HTML 태그는 "</name>" 형태를 갖는다.
일반적으로 사용되는 HTML 태그는 다음을 포함한다
• body : 문서 본문
• h1: 단면 머리글
• center: 중심 정당화
• p: 단락
• ol: 번호부(주문) 리스트
• li: 항목을 나열한다.
대부분의 브라우저가 특정 개수의 일치하지 않는 태그를 허용하지만
HTML 문서에는 일치하는 태그가 있어야 한다.
우리는 샘플 HTML 문서와 가능한 렌더링을 그림 5.3에 보여준다.
그림 5.3: HTML 태그를 보여준다.
(a) HTML 문서; (b) 렌더링.
다행히 코드 조각 5.10과 거의 동일한 알고리즘을 사용하여
HTML 문서의 태그를 일치시킬 수 있다.
코드 조각 5.11 및 5.12에서는
표준 입력에서 읽은 HTML 문서의 태그를 일치시키기 위한 자바 프로그램을 제공한다.
단순화를 위해 모든 태그는 위에서 정의한 간단한 열림 또는 닫힘 태그이며
잘못 형성된 태그는 없다고 가정한다.
코드 조각 5.11-5.12:
HTML 문서에 완전히 일치하는 태그가 있는지 테스트하기 위한 완전한 Java 프로그램이다.
메소드 isHTMLMatched는
코드 조각 5.10에서 스택이 사용된 것과 유사하게 스택을 사용하여
지금까지 표시된 시작 태그의 이름을 저장한다.
메소드 parseHTML은
Scanner s를 사용하고
HTML 문서에서 패턴 <[^>]*>을 사용하여
태그를 추출한다
패턴 <[^>]*>을 사용하여,
이 패턴은 '<'로 시작하는 문자열을 의미하며,
'>'가 아닌 0개 이상의 문자가 뒤따르고
'>'로 마친다.
import java.io.*;
import java.util.Scanner;
import net.datastructure.*;
/** Simplified test of matching tags in an HTML document. */
public class HTML {
/** Strip the first and last characters off a <tag> string. */
public static String stripEnds(String t) {
if (t.length() <= 2) return null; // this is a degenerate tag
return t.substring(1,t.length()-1);
}
/** Test if a stripped tag string is empty or a true opening tag. */
public static boolean isOpeningTag(String tag) {
return (tag.length() == 0) || (tag.charAt(0) != '/');
}
/** Test if a stripped tag1 matches closing tag2 (first character is '/'). */
public static boolean isOpeningTag(String tag1, String Tag2) {
return tag1.equals(tag2.substring(1)); // test against name after '/'
}
/** Test if every opening tag has a matching closing tag. */
public static boolean isOpeningTag(String[] tag) {
Stack<String> S = new NodeStack<String>(); // Stack for matching tags
for (int i = 0; (i < tag.length) && (tag[i] != null); i++) {
if (isOpeningTag(tag[i]))
S.push(tag[i]); // opening tag; push it on the stack
else {
if (S.isEmpty())
return false; // nothing to match
if (!areMatchingTags(S.pop(), tag[i]))
return false; // wrong match
}
}
if (S.isEmpty()) return true; // we matched everything
return false; // we have some tags that never were matched
}
public final static int CAPACITY = 1000; // Tag array size
/* Parse an HTML document into an array of html tags */
public static String[] parseHTML(Scanner s) {
String[] tag = new String[CAPACITY]; // our tag array (initially all null)
int count = 0; // tag counter
String token; // token returned by the scanner s
while(s.hasNextLine()) {
while((token = s.findInLine("<[^>]*>")) ! = null) // find the next tag
tag[count++] = stripEnds(token); //strip the ends off this tag
s.nexLine(); // go to the next line
}
return tag; // our array of (stripped) tags
}
public static void main(String[] args) throws IOException { // tester
if (isHTMLMatched(parseHTML(new Scanner(System.in))))
System.out.println("The input file is a matched HTML document.");
else
System.out.println("The input file is not a matched HTML document.");
}
}
5.2 큐
또 다른 기본적인 자료 구조는 큐(Queue)이다.
큐(Queue): 선출선입(FIFO, First-in First-Out) 원칙에 따라 삽입되고 제거되는 개체들의 집합
즉, 요소는 언제든지 삽입될 수 있지만,
큐에 가장 오래 있었던 요소만 언제든지 제거될 수 있다.
우리는 보통 요소들이 맨 뒤에 줄을 서서 앞에서 치워진다고 말한다.
5.2.1 큐 추상 데이터 타입
형식적으로 큐 추상 데이터 타입은 개체를 시퀀스로 유지하는 컬렉션을 정의한다.
요소 접근 및 삭제 - 시퀀스의 첫 번째 요소(큐의 front이라고 함)
요소 삽입 - 시퀀스의 끝부분(큐의 rear이라고 함)
이 제한은 FIFO(First-in First-Out) 원칙에 따라 항목이 큐에 삽입되고 삭제되는 규칙을 적용한다.
큐 추상 데이터 타입(ADT)은 다음 두 가지 기본 방법을 지원한다:
enqueue(e): 요소 e를 큐의 rear에 삽입한다.
dequeue(): front에 있는 개체를 큐에서 제거하고 반환한다;
큐가 비어 있으면 오류가 발생한다.
또한 스택 ADT의 경우와 마찬가지로 큐 ADT는 다음과 같은 지원 방법을 포함한다:
size(): 큐의 객체 수를 반환한다.
is Empty(): 큐가 비어있는지 여부를 나타내는 부울 값을 반환한다
front(): 큐의 front 객체를 반환하지만 제거하지 않는다. 큐가 비어 있으면 오류가 발생한다.
예제 5.4: 다음 표는 일련의 큐 연산과 정수 객체의
처음에 빈 큐 Q에 대한 효과를 보여준다.
단순화를 위해 정수 객체 대신 정수를 연산의 인수로 사용한다.
| 연산 | 출력 | 전면 ← Q ← 후면 |
| enqueue(5) | - | (5) |
| enqueue(3) | - | (5, 3) |
| dequeue() | 5 | (3) |
| enqueue(7) | - | (3, 7) |
| dequeue() | 3 | (7) |
| front() | 7 | (7) |
| dequeue() | 7 | () |
| dequeue() | "error" | () |
| isEmpty() | true | () |
| enqueue(9) | - | (9) |
| enqueue(7) | - | (9, 7) |
| size() | 2 | (9, 7) |
| enqueue(3) | - | (9, 7, 3) |
| enqueue(5) | - | (9, 7, 3, 5) |
| dequeue() | 9 | (7, 3, 5) |
예제 응용프로그램
큐에는 여러 가지 응용프로그램이 있을 수 있다.
상점, 극장, 예약 센터 및 이와 유사한 서비스는
일반적으로 FIFO 원칙에 따라 고객 요청을 처리한다.
그러므로 큐는 자료 구조가 그러한 응용 프로그램에 대한
거래 처리를 처리하는 데 논리적인 선택이 될 것이다.
예를 들어 항공사의 예약 센터나 극장의 박스 오피스로 가는
전화를 처리하는 데 자연스러운 선택이 될 것이다.
자바의 큐 인터페이스
큐 ADT를 위한 자바 인터페이스는 코드 조각 5.13에 제공된다.
이 일반 인터페이스는 임의의 객체 타입의 객체를 큐에 삽입할 수 있음을 지정한다.
따라서 요소를 제거할 때 명시적인 캐스팅을 사용할 필요가 없다.
size 및 isEmpty 메소드는 스택 ADT의 메소드와 동일한 의미를 갖는다.
이 두 메소드와 front 메소드는 접근자 메소드라고 한다.
접근자(acessor) 메소드: 값을 반환하고 자료 구조의 내용을 변경하지 않는 메소드
코드 조각 5.13: 자바독 스타일로 코멘트가 포함된 인터페이스 Queue 문서화.
public interface Queue<E> {
/**
* Return the number of elements in the queue.
* @return number of elements in the queue.
*/
public int size();
/**
* Return whether the queue is empty.
* @return true if the queue is empty, false otherwise.
*/
public boolean isEmpty();
/**
* Inspect the element at the top of the queue.
* @return the top element in the queue.
* @exception EmptyQueueException if the queue is empty.
*/
public E front() throws EmptyQueueException;
/**
* Insert an element at the top of the queue.
* @param element to be inserted.
*/
public void enqueue (E element);
/**
* Remove the top element from the stack.
* @return element removed.
* @exception EmptyQueueException if the queue is empty.
*/
public E dequeue() throws EmptyQueueException;
}
5.2.2 간단한 배열 기반 큐 구현
우리는 큐의 요소를 저장하는 고정된 용량의 배열 Q를 통해
큐를 간단히 구현하는 방법을 제시한다.
큐 ADT의 주된 규칙은 FIFO 원리에 따라 객체를 삽입하고 삭제하는 것이므로,
우리는 큐의 앞(front)과 뒤(rear)를 어떻게 추적할지 결정해야 한다.
한 가지 가능성은 스택 구현에 사용한 접근 방식을 적용하여
Q[0]을 큐의 front에 두고 거기에서 큐가 커지도록 하는 것이다.
그러나 dequeue 연산을 수행할 때마다
모든 요소를 하나의 배열 셀 앞으로 이동시켜야 하기 때문에 효율적인 해결책은 아니다.
따라서 이러한 구현은 dequeue 메소드를 수행하는 데 O(n) 시간이 걸릴 것이다.
(n은 큐의 현재 객체 수이다.)
각 큐 메소드에 대해 일정한 시간을 달성하려면 다른 접근 방식이 필요하다.
원형으로 배열 사용
객체가 Q에 놓이면 움직이지 않도록 두 개의 변수 f와 r을 정의한다.
이 변수의 의미는 다음과 같다:
• f: 큐가 비어 있지 않은 경우 큐의 첫 번째 요소를 저장하는 Q의 셀에 대한 인덱스
큐가 비어 있는 경우 f = r이다.
큐의 첫 번째 요소 = dequeue 연산으로 제거할 다음 후보
• r: Q에서 사용 가능한 다음 배열 셀에 대한 인덱스
처음에 우리는 f = r = 0을 할당하는데,
이것은 큐가 비어 있다는 것을 나타낸다.
이제 우리가 큐 앞에서 어떤 요소를 제거할 때,
우리는 다음 셀을 색인하기 위해 f를 증가시킨다.
마찬가지로, 우리는 요소를 추가할 때,
우리는 그것을 셀 Q[r]에 저장하고 r을 증가시켜
Q에 있는 다음 사용 가능한 셀을 색인한다.
이 방식을 사용하면 일정한 시간,
즉 O(1) 시간에 메소드 front, enqueue 및 dequeue를 구현할 수 있다.
그러나 이 방식에는 여전히 문제가 있다.
예를 들어, 하나의 원소 N을
여러 번 반복적으로 enqueue와 dequeue하면
어떤 일이 발생하는지 생각해 보자.
우리는 f = r = N을 가질 것이다.
만약 원소를 한 번만 더 삽입하려고 한다면,
큐에 많은 공간이 있음에도 불구하고
(Q의 N개의 유효한 위치가 Q[0]에서 Q[N - 1]이므로)
배열에서 범위를 벗어난 오류가 발생할 것이다.
이 문제를 피하고 모든 배열 Q를 사용할 수 있도록 하기 위해,
우리는 f와 r 인덱스가 Q의 끝에 "wrap around" 한다(둘러싸게 한다).
즉, 이제 Q를 원형 배열로 간주한다.
원형 배열(circular array): Q[0]에서 Q[N - 1]로 갔다가 바로 Q[0]으로 되돌아오는 배열
(그림 5.4 참조)
그림 5.4: 배열 Q를 원형 방식으로 사용:
(a) f ≤ r인 "정상" 구성;
(b) r < f인 "wrapped around" 구성.
큐 요소를 저장하는 셀이 강조 표시된다.
모듈로 연산자를 사용하여 원형 배열 구현
Q에 대한 이 원형의 관점을 구현하는 것은 사실 꽤 쉽다.
우리는 for를 증분할 때마다
이 증분을 각각 "(f + 1) mod N" 또는 "(r + 1) mod N"으로 계산한다.
연산자 "mod"
= 모듈로(modulo) 연산자
= 정수 나눗셈에 나머지를 취함으로써 계산된다
예를 들어 14 ÷ 4 = 3 ⋯ 2이므로 14 mod 4 = 2이다.
구체적으로 x ≥ 0과 y >0 같은 정수 x와 y가 주어졌을 때, x mod y = x- x/y · y를 가진다.
즉, 만약 r = x mod y이면 x = qy + r 같은 음이 아닌 정수 q가 있다.
자바는 모듈로 연산자를 나타내기 위해 "%"를 사용한다.
모듈로 연산자를 사용하면
Q를 원 배열로 보고 일정한 시간(즉, O(1)시간)으로
각각의 큐 메소드를 구현할 수 있다.
코드 조각 5.14에서 큐를 구현하기 위해 이 접근법을 사용하는 메소드를 설명한다.
코드 조각 5.14: 원형 배열을 사용한 큐의 구현.
구현은 모듈로 연산자를 사용하여
배열의 끝 주위의 인덱스를 "감싸고(wrap)"
또한 두 개의 인스턴스 변수를 포함한다.
f: 큐의 front의 인덱스
r: 큐의 rear 뒤의 첫 번째 빈 셀의 인덱스
Algorithm size():
return (N - f + r) mod N
Algorithm isEmpty():
return (f = r)
Algorithm top():
if isEmpty() then
throw a QueueEmptyException
return Q[f]
Algorithm dequeue():
if isEmpty() then
throw a QueueEmptyException
temp ← Q[f]
Q[f] ← null
f ← (f + 1) mod N
return temp
Algorithm dequeue(e):
if size() = N - 1 then
throw a FullQueueException
Q[r] ← e
r ← (r + 1) mod N
위의 구현은 중요한 세부사항을 포함하고 있으며, 이는 처음에는 놓쳤을 수도 있다.
N개의 객체 중 어느 것도 dequeue하지 않고 Q에 큐를 넣을 때 발생하는 상황을 생각해 보자.
우리는 f = r을 가질 것인데, 이는 큐가 비어 있을 때 발생하는 것과 같은 조건이다.
따라서 이 경우 전체 큐와 빈 큐의 차이를 구별할 수 없을 것이다.
다행히 이 문제는 큰 문제가 아니며,
이 문제를 처리하기 위한 여러 가지 방법이 존재한다.
여기서 우리가 설명하는 해결책은 Q는
결코 N - 1개 이상의 개체를 가질 수 없다고 주장하는 것이다.
전체 큐를 처리하는 이 간단한 규칙은 구현의 마지막 문제를 해결하고
코드 조각 5.14에 주어진 큐 방법에 대한 의사 코드화된 설명으로 이어진다.
큐에 더 이상 요소를 삽입할 수 없음을 알리기 위해
FullQueueException이라는 구현별 예외를 도입했다.
또한 "일반(normal)" 구성(f ≤ r인 경우)과
"둘러싸인(wrapped around)" 구성(r < f인 경우)
모두에서 올바른 결과를 제공하는 (N - f + r) mod N을 통해
큐의 크기를 계산하는 방법도 주목하자.
표 5.2는 배열에 의한 큐의 구현에서 메소드의 실행 시간을 보여준다.
배열 기반 스택 구현에서와 마찬가지로
배열 구현의 각 큐 메소드는
산술 연산, 비교 및 할당을 포함하는 일정한 수의 문을 실행한다.
따라서 이 구현의 각 메소드는 O(1) 시간으로 실행된다.
표 5.2: 배열로 구현된 큐의 성능.
공간 사용량은 O(N)이며,
여기서 N은 배열의 크기로 큐가 생성될 때 결정된다.
공간 사용량은 실제로 큐에 있는 요소의 수 n < N과는 무관하다.
| 메소드 | 시간 |
| size | O(1) |
| isEmpty | O(1) |
| front | O(1) |
| enqueue | O(1) |
| dequeue | O(1) |
배열 기반 스택 구현과 마찬가지로 배열 기반 큐 구현의 유일한 실제 단점은
인위적으로 큐의 용량을 일부 고정된 값으로 설정한다는 것이다.
실제 애플리케이션에서는 실제로 이보다 더 많거나 적은 큐 용량이 필요할 수 있지만,
용량 추정치가 좋으면 배열 기반 구현이 상당히 효율적이다.
5.2.3 일반 연결 리스트를 통한 큐 구현
일반적으로 단일 연결 리스트를 사용하여 효율적으로 큐 ADT를 구현할 수 있다.
효율성을 위해
큐의 front을 리스트의 헤드에 두고,
큐의 rear을 리스트의 테일에 두도록 선택한다.
이러한 방식으로 저희는 헤드에서 제거하고 테일에서 삽입한다.
(헤드에서 삽입하고 테일에서 제거하는 것이 좋지 않은 이유는 무엇일까?)
리스트의 헤드와 테일 노드에 대한 참조를 유지해야 한다.
이 구현의 모든 세부 사항을 설명하는 대신
코드 조각 5.15의 기본적인 큐 메소드에 대한 자바 구현을 제공한다.
코드 조각 5.15: 코드 조각 5.6 클래스
코드 조각 5.6의 클래스 Node를 사용하여
단일 연결 리스트를 통해 큐 ADT를 구현할 때의 방법.
public void enqueue(E elem) {
Node<E> node = new Node<E>():
node.setElement(elem);
node.setNext(null); // node will be new tail node
if (size == 0)
head = node; // special case of a previously empty queue
else
tail.setNext(node); // add node at the tail of the list
tail = node; // update the reference to the tail node
size++;
}
public E enqueue() throws EmptyQueueException {
if (size == 0)
throws new EmptyQueueException("Queue is empty.");
E tmp = head.getElement();
head = head.getNext();
size--;
if (size == 0)
tail = null; // the queue is now empty
return tmp;
}
큐 ADT의 단일 연결 리스트 구현의 각 메소드는 O(1) 시간 내에 실행된다.
또한 배열 기반 큐 구현에서와 같이 큐의 최대 크기를 지정할 필요가 없지만,
이 이점은 요소당 사용되는 공간을 늘리는 대신에 발생한다.
그러나 단일 연결 리스트 큐 구현에서의 메소드는 우리가 원하는 것보다 복잡한데,
왜냐하면 우리는 큐가 대기열 이전에 비어 있거나
또는 대기열 이후에 대기열이 비어 있는
특별한 경우에 대처하는 방법에 특별히 주의를 기울여야 하기 때문이다.
5.2.4 라운드 로빈 스케줄러
큐 자료 구조의 일반적인 용도는 라운드 로빈 스케줄러를 구현하는 것이다.
라운드 로빈 스케줄러(round robin scheduler):
순환 방식으로 요소들의 집합을 반복하고 각 요소에 대해 주어진 동작을 수행하여 "서비스"한다.
예를 들어, 이러한 스케줄은 클라이언트들의 집합에 의해 공유되어야 하는 자원을 공정하게 할당하는 데 사용된다.
예를 들어 라운드 로빈 스케줄러를 사용하여
컴퓨터에서 동시에 실행되는 다양한 응용 프로그램에 CPU 시간 조각을 할당할 수 있다.
다음 단계를 반복적으로 수행하여
큐 Q를 사용하여 라운드 로빈 스케줄러를 구현할 수 있다(그림 5.5 참조):
1. e ← Q.dequeue()
2. 서비스 요소 e
3. 3. Q.enqueue(e)
그림 5.5: 큐를 사용하여 라운드 로빈 스케줄러를 구현하는 세 번의 반복 단계.
요세푸스 문제
어린이 게임인 "뜨거운 감자"에서 n명의 어린이들이
원을 중심으로 "감자"라고 불리는 물체를 지나가는 원을 따라 앉는다.
감자는 원 안에 시작하는 어린이와 함께 시작하고,
어린이들은 지도자가 종을 울릴 때까지 계속해서 감자를 건네고,
이 시점에서 감자를 들고 있는 어린이는
원 안의 다음 어린이에게 감자를 건넨 후 게임을 떠나야 한다.
선택된 어린이가 떠난 후, 다른 어린이들은 원을 닫는다.
그리고 나서 이 과정은 오직 한 명의 어린이가 남을 때까지 계속되는데,
그 어린이가 우승자로 선언된다.
만약 지도자가 감자를 k번 통과한 후에 항상 종을 울리는 전략을 사용한다면,
어떤 고정된 값인 k에 대해,
주어진 어린이 리스트의 우승자를 결정하는 것은
요세푸스 문제(Josephus problem)라고 알려져 있다.
큐를 이용한 요세푸스 문제 해결
감자를 행렬의 맨 앞에 있는 원소와 연결하고
원소들을 원을 중심으로 순서에 따라 행렬에 저장함으로써
행렬을 사용하여 n개 원소의 집합에 대한 요세푸스 문제를 풀 수 있다.
⇒ (감자를 통과시키는 것) = (원소를 큐에서 제거하고 즉시 다시 큐에 올리는 것)
이 과정이 k번 수행된 후에는
앞 원소를 큐에서 해제하고 폐기함으로써 제거한다.
우리는 O(nk) 시간 내에 실행되는 해를 설명하는 코드 조각 5.16에서 이 접근법을 사용하여
요세푸스 문제를 해결하기 위한 완전한 자바 프로그램을 보여준다.
(이 책의 범위를 넘어서는 기술을 사용하여 이 문제를 더 빨리 해결할 수 있다.)
코드 조각 5.16: 큐를 이용하여 요세푸스 문제를 해결하기 위한 완전한 자바 프로그램.
코드 조각 5.15에 클래스 NodeQueue가 나와 있다.
import net.datastructures.*;
public class Josephus {
/** Solution the Josephus problem using a queue. */
public static <E> E Josephus(Queue<E> Q, int k) {
if (Q.isEmpty() return null;
while (Q.size() > 1) {
System.out.println(" Queue: " + Q + " k = " + k);
for (int i =0; i < k; i++)
Q.enqueue(Q.dequeue()); // move the front element to the end
E e = Q.dequeue(); // remove the front element from the collection
System.out.println(" " + e + " is out");
}
return Q.dequeue(); // the winner
}
/** Build a queue from an array of objects */
public static <E> Queue<E> () buildQueue(E a[]) {
Queue<E> Q = new NodeQueue<E>();
for (int i =0; i < a.length; i++)
Q.enqueue(a[i]);
return Q;
}
/** Tester method */
public static void main(String[] args) {
String[] a1 = {"Alice", "Bob", "Cindy", "Doug", "Ed", "Fred"};
String[] a2 = {"Gene", "Hope", "Irene", "Jack", "Kim", "Lance"};
String[] a3 = {"Mike", "Roberto"};
System.out.println("First winner is " + Josephus(buildQueue(a1), 3));
System.out.println("Second winner is " + Josephus(buildQueue(a2), 10));
System.out.println("First winner is " + Josephus(buildQueue(a3), 7));
}
}
5.3 이중 종단 큐
더블 엔드 큐(double-ended queue) 또는 데크(deque):
큐의 앞쪽과 뒤쪽에서 모두 삽입과 삭제를 지원하는 큐와 같은 자료 구조
일반 큐 ADT의 디큐 메소드와의 혼동을 피하기 위해 보통 "데크"라고 발음하는데,
이는 약어 "D.Q"처럼 발음된다.
5.3.1 데크 추상 데이터 타입
데크 추상 데이터 타입은 스택 및 큐 ADT보다 더 풍부하다.
데크 ADT의 기본 방법은 다음과 같다:
addFirst(e): 데크의 시작 부분에 새 요소 e를 삽입한다.
addLast(e): 데크의 끝 부분에 새 요소 e를 삽입한다.
removeFirst(): deque의 첫 번째 요소를 제거하고 반환한다.
deque가 비어 있으면 오류가 발생한다.
removeLast(): deque의 마지막 요소를 제거하고 반환한다.
deque가 비어 있으면 오류가 발생한다.
또한 deque ADT는 다음과 같은 지원 방법도 포함할 수 있다:
getFirst(): 데크의 첫 번째 요소를 반환한다.
데크가 비어 있으면 오류가 발생한다.
getLast(): 데크의 마지막 요소를 반환한다.
데크가 비어 있으면 오류가 발생한다.
size(): 데크의 요소 수를 반환한다.
isEmpty(): 데크가 비어 있는지 확인한다.
예제 5.5: 다음 표는 일련의 연산들과 그것들이
정수 객체들의 처음에 비어있는 데크 D에 미치는 영향을 보여준다.
단순화를 위해, 우리는 연산의 인수로서 정수 객체 대신 정수를 사용한다.
| 연산 | 출력 | D |
| addFirst(3) | - | (3) |
| addFirst(5) | - | (5, 3) |
| removeFirst() | 5 | (3) |
| addLast(7) | - | (3, 7) |
| removeFirst() | 3 | (7) |
| removeLast() | 7 | () |
| removeFirst() | "error" | () |
| isEmpty() | true | () |
5.3.2 데크 구현
데크는 리스트의 양쪽 끝에 삽입과 제거가 필요하기 때문에
데크를 구현하기 위해 단일 연결 리스트를 사용하는 것은 비효율적일 것이다.
하지만 데크를 효율적으로 구현하기 위해 이중 연결 리스트를 사용할 수 있다.
3.3절에서 설명한 바와 같이
헤더와 트레일러에 센티넬 노드를 사용하면
O(1) 시간에 이중 연결 리스트의 양쪽 끝에
요소를 삽입하거나 제거하는 것은 간단하다.
새로운 요소 e를 삽입하는 경우,
e가 가야 할 곳 이전의 노드 p와
e가 가야 할 곳 이후의 노드 q에 접근할 수 있다.
두 노드 p와 q 사이에 새로운 요소를 삽입하기 위해
(둘 중 하나 또는 둘 다 센티넬이 될 수 있는)
새로운 노드 t를 만들고,
t의 prev와 next 링크가 각각 p와 q를 나타내고,
p의 next 링크가 t를 가리키도록 하고,
q의 prev 링크가 t를 가리키도록 한다.
마찬가지로, 노드 t에 저장된 요소를 제거하기 위해,
우리는 t의 양쪽에 있는 노드 p와 q에 접근할 수 있다.
노드 p와 q 사이의 노드 t를 제거하기 위해,
우리는 단순히 t 대신에 p와 q가 서로를 가리키고 있다.
아무도 t를 가리키지 않기 때문에,
이제 t는 가비지 컬렉터에 의해 회수될 수 있으므로,
우리는 t에 있는 어떤 필드도 바꿀 필요가 없다.
표 5.3은 이중 연결 리스트로 구현된 데크에 대한 메소드의 실행 시간을 보여준다.
모든 메소드는 O(1) 시간 내에 실행된다는 점에 유의하자.
표 5.3: 이중 연결 리스트로 실현된 데크의 성능.
| 메소드 | 시간 |
| size, isEmpty | O(1) |
| getFirst, getLast | O(1) |
| addFirst, addLast | O(1) |
| removeFirst, removeLast | O(1) |
따라서 이중 연결 리스트를 사용하여
데크 ADT의 각 메소드를 일정한 시간으로 구현할 수 있다.
덧붙여서, 위에서 설명한 바와 같이 데크 ADT의 모든 메소드는
java.util.LinkedList<E> 클래스에 포함되어 있다.
따라서, 만약 우리가 데크를 사용해야 하고 처음부터 구현하지 않는 것이 좋다면,
단순히 내장된 java.util.LinkedList<E> 클래스를 사용하면 된다.
어쨌든 코드 조각 5.17에서 Deque 인터페이스를 보여주고
코드 조각 5.18에서 이 인터페이스의 구현을 보여준다.
코드 조각 5.17:
인터페이스 데크가 자바독 스타일로 주석을 달면서 문서화되었다(섹션 1.9.3).
일반 매개변수화된 타입 E의 사용도 참고하자.
데크는 임의의 지정된 클래스의 요소를 포함할 수 있음을 의미한다.
/**
* Interface for a deque: a collection of objects that are inserted
* and removed at both ends;a subset of java.util.LinkedList methods.
*
* @author Roberto Tamassia
* @author Michael Goodrich
*/
public interface Deque<E> {
/**
* Return the number of elements in the queue.
*/
public int size();
/**
* Return whether the queue is empty.
*/
public boolean isEmpty();
/**
* Returns the first element; an exception is thrown if deque is empty.
*/
public E getFirst() throws EmptyDequeException;
/**
* Returns the last element; an exception is thrown if deque is empty.
*/
public E getLast() throws EmptyDequeException;
/**
* Inserts an element to be the first in the deque.
*/
public void addFrist (E element);
/**
* Inserts an element to be the last in the deque.
*/
public void addLast (E element);
/**
* Removes the first element; an exception is thrown if deque is empty.
*/
public E removeFirst() throws EmptyDequeException;
/**
* Removes the last element; an exception is thrown if deque is empty.
*/
public E removeLast() throws EmptyDequeException;
}
코드 조각 5.18:
일반 이중 연결 리스트 노드인 클래스 DLNode를 보여주지 않았으며
getLast, addLast 및 removeFirst 메소드를 보여주지 않았다는 점을 제외하고는
Deque 인터페이스를 구현하는 클래스 NodeDeque이다.
public class NodeDeque implements Deque<E> {
protected DLNode<E> header, trailer; // sentinels
protected int size; // number of elements
public NodeDeque() { // initialize an empty deque
header = new DLNode<E>();
trailer = new DLNode<E>();
header.setNext(trailer); // make header point to trailer
trailer.setPrev(header); // make trailer point to header
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty() {
if (size == 0)
return true;
return false;
}
public E getFirst() throws EmptyDequeException {
if (isEmpty())
throw new EmptyDequeException("Deque is empty.");
return header.getNext().getElement();
}
public void addFrist (E element) {
DLNode<E> second = header.getNext();
DLNode<E> first = new DLNode<E>(o, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
public E removeLast() throws EmptyDequeException {
if (isEmpty())
throw new EmptyDequeException("Deque is empty.");
DLNode<E> last = trailer.getPrev();
E o = last.getElement();
DLNode<E> secondtolast = last.getPrev();
trailer.setPrev(secondtolast);
secondtolast.setNext(trailer);
size--;
}
}'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 7장 트리(1) (2) | 2023.12.29 |
|---|---|
| 6장 리스트와 반복자 (1) | 2023.12.22 |
| 4장 분석 도구 (1) | 2023.12.19 |
| 3장 배열, 연결 리스트, 재귀(2) (1) | 2023.12.17 |
| 3장 배열, 연결 리스트, 재귀(1) (0) | 2023.12.16 |