10.1 개요
많은 사람들이 stack과 queue 데이터 추상에 대해서는 잘 이해하고 있다. 책상위에 놓은 서류철이나 찬장에 놓인 접시들이 stack의 전형적인 예가 될 것이다. 이들 모두 맨 위쪽에 있는 것들은 접근하기가 가장 쉽다는 특징을 가진다. 콜렉션에 새로운 아이템을 추가하는 가장 쉬운 방법은 맨위에 올려 놓는 것이다. 이런식으로 하면, stack에서 제거되는 아이템은 가장 최근에 stack에 추가된 아이템이 된다.
LIFO와 FIFO
LIFO와 FIFO
한편, 일상생활에서 살펴볼 수 있는 queue의 예로 은행에 선 줄이나 영화관 앞에 선 줄등을 들 수 있다. 여기서 사람이 새로 줄을 설 때처럼 삽입은 queue의 뒤에서 이루어지고, 관객이 영화관에 들어가는 것처럼 아이템의 삭제는 queue의 앞에서 이루어진다. queue에서의 삭제순서는 stack과는 반대이다. queue에서는 삭제된 아이템이 queue에 가장 오랫동안 있었던 원소이다.
표준 라이브러리에서는 stack과 queue가 모두 어댑터(adaptor)이고, 이들은 실질적으로 값을 저장하는데 사용하는 컨테이너를 바탕으로 만들어진다. stack은 vector, list, deque으로부터 만들어지고, queue는 list나 deque으로부터 만들어진다. stack이나 queue가 담고 있는 원소들은 '<'와 '=='연산자를 모두 인식해야 한다.
stack이나 queue는 반복자를 정의하고 있지 않기 때문에, 하나씩 값들을 제거해보지 않고서는 콜렉션의 원소들을 살펴볼 수 없다. 이들이 반복자를 구현하고 있지 않다는 사실은 12장과 13장에 설명된 generic 알고리듬들 중 많은 것들을 사용할 수 없다는 것을 의미한다.
10.2 stack 데이터 추상(data abstraction)
stack은 전통적으로 다음 연산들을 구현한 객체로 정의되어 있다.
| empty() | stack이 비었으면 참(true)을 반환 |
| size() | stack에 담긴 원소의 갯수를 반환 |
| top() | stack의 맨 위에 위치한 원소를 반환(지우지는 않는다) |
| push(newElement) | stack의 맨 위에 원소를 새로 추가 |
| pop() | stack의 맨 위에 위치한 원소를 삭제(반환하지는 않는다) |
10.2.1 Include 화일
front 원소를 접근하는 연산과 삭제하는 연산은 별도의 연산으로 제공된다는 점을 명심해야 한다. stack을 사용하는 프로그램은 stack을 밑받침하고 있는 컨테이너 타입(예를 들면, vector)에 대한 헤더 화일뿐만아니라 stack 헤더화일을 포함해야 한다.
#include <stack> #include <vector>
10.2.2 stack의 선언과 초기화
stack의 선언은 두개의 인자를 명시해야 한다. 하나는 stack이 담게될 원소의 타입이고, 나머지 하나는 원소들을 담는데 사용할 컨테이너이다. stack은 컨테이너로 vector나 deque를 가장 많이 쓰고, list도 컨테이너로 사용할 수 있다. deque를 사용하면 좀 더 빠르고, vector를 사용하면 크기가 좀 작아진다. 다음 예는 stack에 대한 선언이다.
stack<int, vector<int> > stackOne; stack<double, deque<double> > stackTwo; stack<Part*, list<Part* > > stackThree; stack<Customer, list<Customer> > stackFour;
마지막 예는 프로그래머가 정의한 Customer 타입의 stack을 생성한다.
10.2.3 예제 프로그램 - RPN 계산기
A classic application of a stack is in the implementation of calculator. Input to the calculator consists of a text string that represents an expression written in reverse polish notation (RPN). Operands, that is, integer constants, are pushed on a stack of values. As operators are encountered, the appropriate number of operands are popped off the stack, the operation is performed, and the result is pushed back on the stack.
We can divide the development of our stack simulation into two parts, a calculator engine and a calculator program. A calculator engine is concerned with the actual work involved in the simulation, but does not perform any input or output operations. The name is intended to suggest an analogy to a car engine, or a computer processor - the mechanism performs the actual work, but the user of the mechanism does not normally directly interact with it. Wrapped around this is the calculator program, which interacts with the user, and passes appropriate instructions to the calculator engine.
We can use the following class definition for our calculator engine. Inside the class declaration we define an enumerated list of values to represent each of the possible operators that the calculator is prepared to accept. We have made two simplifying assumptions: all operands will be integer values, and we will handle only binary operators.
class calculatorEngine {
public:
enum binaryOperator {plus, minus, times, divide};
int currentMemory () // return current top of stack
{ return data.top(); }
void pushOperand (int value) // push operand value on to stack
{ data.push (value); }
void doOperator (binaryOperator); // pop stack and perform
// operator
protected:
stack< int, vector<int> > data;
};
The member function doOperator() performs the actual work. It pops values from the stack, performs the operation, then pushes the result back onto the stack.
void calculatorEngine::doOperator (binaryOperator theOp)
{
int right = data.top(); // read top element
data.pop(); // pop it from stack
int left = data.top(); // read next top element
data.pop(); // pop it from stack
switch (theOp) {
case plus: data.push(left + right); break;
case minus: data.push(left - right); break;
case times: data.push(left * right); break;
case divide: data.push(left / right); break;
}
}
The main program reads values in reverse polish notation, invoking the calculator engine to do the actual work:
int main() {
int intval;
calculatorEngine calc;
char c;
while (cin >> c)
switch (c) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
cin.putback(c);
cin >> intval;
calc.pushOperand(intval);
break;
case '+': calc.doOperator(calculatorEngine::plus);
break;
case '-': calc.doOperator(calculatorEngine::minus);
break;
case '*': calc.doOperator(calculatorEngine::times);
break;
case '/': calc.doOperator(calculatorEngine::divide);
break;
case 'p': cout << calc.currentMemory() << endl;
break;
case 'q': return; // quit program
}
}
10.3 queue 데이터 추상(data abstraction)
queue는 일반적으로 다음 연산들을 구현한 객체로서 정의된다.
| empty() | queue가 비었으면 참(true)을 반환 |
| size() | queue에 담긴 원소의 갯수를 반환 |
| front() | queue의 맨 앞에 위치한 원소를 반환(삭제는 않는다) |
| back() | queue의 맨 뒤에 위치한 원소를 반환 |
| push(newElement) | queue의 맨 뒤에 원소를 새로 추가 |
| pop() | queue의 맨 앞에 위치한 원소를 삭제(반환하지는 않는다) |
10.3.1 Include 화일
queue의 맨앞에 위치한 원소를 접근하는 연산과 삭제하는 연산은 별도의 연산으로 수행된다는 점을 주목해야 한다. queue를 사용하는 프로그램은 queue의 컨테이너 타입(예를 들어, list)에 대한 헤더파일뿐만 아니라, queue 화일을 포함해야 한다.
#include <queue> #include <list>
10.3.2 queue의 선언과 초기화
queue에 대한 선언은 값을 담고 있는 컨테이너와 원소 타입을 명시해야 한다. queue는 컨테이너 타입으로 list나 deque를 가장 많이 사용한다. list를 사용하면 코드가 작아지는 반면에, deque를 사용하면 코드가 좀 빨라진다. 다음은 queue를 선언하는 예이다.
queue<int, list<int> > queueOne; queue<double, deque<double> > queueTwo; queue<Part*, list<Part* > > queueThree; queue<Customer, list<Customer> > queueFour;
마지막 예는 프로그래머가 정의한 Customer의 queue를 생성한다. stack 컨테이너에서 처럼, queue에 저장된 모든 객체는 '<'와 '==' 연산자를 이해해야 한다.
queue는 반복자를 구현하지 않기 때문에, 13절과 14절에서 설명하는 generic 알고리듬들은 queue에 적용할 수 없다.
10.3.3 예제 프로그램 - Bank Teller 시뮬레이션
Queues are often found in businesses, such as supermarkets or banks. Suppose you are the manager of a bank, and you need to determine how many tellers to have working during certain hours. You decide to create a computer simulation, basing your simulation on certain observed behavior. For example, you note that during peak hours there is a ninety percent chance that a customer will arrive every minute.
We create a simulation by first defining objects to represent both customers and tellers. For customers, the information we wish to know is the average amount of time they spend waiting in line. Thus, customer objects simply maintain two integer data fields: the time they arrive in line, and the time they will spend at the counter. The latter is a value randomly selected between 2 and 8. (See Section 2.2.5 for a discussion of the randomInteger() function.)
class Customer {
public:
Customer (int at = 0) : arrival_Time(at),
processTime(2 + randomInteger(6)) {}
int arrival_Time;
int processTime;
bool done() // are we done with our transaction?
{ return --processTime < 0; }
operator < (const Customer & c) // order by arrival time
{ return arrival_Time < c.arrival_Time; }
operator == (const Customer & c) // no two customers are alike
{ return false; }
};
Because objects can only be stored in standard library containers if they can be compared for equality and ordering, it is necessary to define the < and == operators for customers. Customers can also tell us when they are done with their transactions.
Tellers are either busy servicing customers, or they are free. Thus, each teller value holds two data fields; a customer, and a boolean flag. Tellers define a member function to answer whether they are free or not, as well as a member function that is invoked when they start servicing a customer.
class Teller {
public:
Teller() { free = true; }
bool isFree() // are we free to service new customer?
{ if (free) return true;
if (customer.done())
free = true;
return free;
}
void addCustomer(Customer c) // start serving new customer
{ customer = c;
free = false;
}
private:
bool free;
Customer customer;
};
The main program is then a large loop, cycling once each simulated minute. Each minute a new customer is, with probability 0.9, entered into the queue of waiting customers. Each teller is polled, and if any are free they take the next customer from the queue. Counts are maintained of the number of customers serviced and the total time they spent in queue. From these two values we can determine, following the simulation, the average time a customer spent waiting in the line.
int main() {
int numberOfTellers = 5;
int numberOfMinutes = 60;
double totalWait = 0;
int numberOfCustomers = 0;
vector<Teller> teller(numberOfTellers);
queue< Customer, deque<Customer> > line;
for (int time = 0; time < numberOfMinutes; time++) {
if (randomInteger(10) < 9)
line.push(Customer(time));
for (int i = 0; i < numberOfTellers; i++) {
if (teller[i].isFree() & ! line.empty()) {
Customer & frontCustomer = line.front();
numberOfCustomers++;
totalWait += (time - frontCustomer.arrival_Time);
teller[i].addCustomer(frontCustomer);
line.pop();
}
}
}
cout << "average wait:" <<
(totalWait / numberOfCustomers) << endl;
}
By executing the program several times, using various values for the number of tellers, the manager can determine the smallest number of tellers that can service the customers while maintaining the average waiting time at an acceptable amount.