[Exercises 1]
/*
Extend the stack ADT by adding functions to output a stack;
스택 추상자료형을 출력하도록 확장시킨다;
split a stack into two stacks with one containing the bottom half elements and the second the remaining elements;
스택을 두개로 나누어서 하나는 밑에 절반을 소장하고 다른 하나는 나머지를 소장하도록 한다;
and to combine two stacks into one by placing all elements of the second stack on top of those of the first stack.
그리고 두번째 스택을 첫번째 스택 위에 위치시키면서 하나로 만든다.
Write C++ code for your new functions
위의 조건을 만족시키도록 C++ 코드를 작성한다
*/
#include <iostream>
#include <algorithm>
using namespace std;
template <typename T>
class Stack
{
private:
T *stack; //스택배열
int top1, top2; //제일 마지막에 삽입된 원소
int capacity; //배열 크기
public:
Stack(int stackCapacity = 10) :capacity(stackCapacity)
{
if (capacity < 1)
throw "Stack capacity must be >0";
stack = new T[capacity];
top1 = -1;
top2 = capacity;
}
~Stack()
{
delete[]stack;
}
bool IsEmpty() const
{
return (top1 == -1 && top2 == capacity);
}
T &Top1() const
{
if (IsEmpty())
throw "Stack is empty";
return stack[top1];
}
T &Top2() const
{
if (IsEmpty())
throw "Stack is empty";
return stack[top2];
}
void Push1(const T &x)
{
if (top1 < top2 - 1)
{
stack[++top1] = x;
}
else
{
cout << "스택 오버플로우";
return;
}
}
void Push2(const T &x)
{
if (top1 < top2 - 1)
{
stack[--top2] = x;
}
else
{
cout << "스택 오버플로우";
return;
}
}
void Pop1()
{
if (top1 >= 0)
{
stack[top1--].~T(); //destructor for T(처음보는 활용법)
}
else
{
cout << "스택 오버플로우";
return;
}
}
void Pop2()
{
if (top2 < capacity)
{
stack[top2++].~T();
}
else
{
cout << "스택 오버플로우";
return;
}
}
template <typename T> //이걸 추가하지 않으면 basic operator<< 라고 여겨져 오류가 납니다(중요!!!)
friend ostream &operator<<(ostream &os, Stack<T> &s); //출력
};
template <typename T>
ostream &operator<<(ostream &os, Stack<T> &s)
{
os << "첫 번째 스택 Top: " << s.Top1() << endl;
for (int i = 0; i <= s.top1; i++)
os << i+1 << ": " << s.stack[i] << endl;
os << "두 번째 스택 Top: " << s.Top2() << endl;
for (int i = 1; i <= s.capacity - s.top2; i++)
os << s.top2 + i << ": " << s.stack[s.top2+i-1] << endl;
return os;
}
template <typename T>
void ChangeSize1D(T *&a, const int oldSize, const int newSize)
{
if (newSize < 0)
throw "New length must be >=0";
T *temp = new T[newSize];
int number = min(oldSize, newSize);
copy(a, a + number, temp);
delete[]a;
a = temp;
}
int main(void)
{
Stack<int> intStack;
for (int i = 0; i < 5; i++)
intStack.Push1(i + 1);
for (int i = 0; i < 5; i++)
intStack.Push2(i * 2);
cout << "스택출력" << endl;
cout << intStack << endl;
cout << "Pop1" << endl;
intStack.Pop1();
cout << intStack << endl;
cout << endl << "Pop2" << endl;
intStack.Pop2();
cout << intStack << endl;
return 0;
}
[Exercises 2]
/*
Consider the railroad switching network given in Figure 3.3.
Figure 3.3에 주어진 철로 바꾸기 네트워크를 확인하라.
Railroad cars numbered 1, 2, 3, ..., n are initially in the top right track segment.
기차들은 오른쪽 철로에 배치되어있으며 왼쪽부터 오른쪽 순서로 1부터 n의 숫자가 적혀있다.
Railroad cars can be moved into the vertical track segement one at a time from either of the horizontal segments and then moved from the vertical segment to any one of the horizontal segments.
기차들은 왼쪽 혹은 오른쪽에 있는 가로 철선에서 하나씩 세로로 되어있는 철선으로 옮겨질 수 있으며 세로로 되어있는 철선에서는 왼쪽 혹은 오른쪽에 있는 가로 철선으로 다시 옮겨질 수 있다.
The vertical segment operates as a stack as new cars enter at the top and cars depart the vertical segment from the top.
세로로 되어있는 철선에서는 마지막으로 옮겨진 기차가 먼저 옮겨질 수 있으므로 '스택'이라고 볼 수 있다.
For instance, if n=3, we could move car 1 into the vertical segment, move 2 in, move 3 in, and then take the cars out producing the new order 3, 2, 1.
예를 들자면 n이 3일 때, 오른쪽 철선에 있는 1번 차부터 3번차까지 세로철선으로 옮겼다가 순서대로 왼쪽 철선으로 옮기면 새로운 순서인 3, 2, 1 순서로 배치시킬 수 있다.
For n=3 and 4 what are possible permutations of the cars that can be obtained? Are any permutations not possible?
n이 3이고 4일 때 나올 수 있는 순서를 모두 구하여라
*/
n=3
->
1. 1 2 3
2. 1 3 2
3. 2 1 3
4. 2 3 1
5. 3 2 1
6. 3 1 2
n=4
->
1. 1 2 3 4
2. 1 2 4 3
3. 1 3 2 4
4. 1 3 4 2
5. 1 4 2 3
6. 1 4 3 2
7. 2 1 3 4
8. 2 1 4 3
9. 2 3 1 4
10. 2 3 4 1
11. 2 4 1 3
12. 2 4 3 1
13. 3 1 2 4
14. 3 1 4 2
15. 3 2 1 4
16. 3 2 4 1
17. 3 4 1 2
18. 3 4 2 1
19. 4 1 2 3
20. 4 1 3 2
21. 4 2 1 3
22. 4 2 3 1
23. 4 3 1 2
24. 4 3 2 1
결국 순열과 같다
[n=4인 경우도 똑같은 방식으로 하면 됩니다]
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.4 연습문제 (2) | 2017.08.13 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.3 연습문제 (0) | 2017.08.11 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 5~9 (0) | 2017.08.04 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 1~4 (0) | 2017.08.03 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.6 연습문제 (0) | 2017.07.31 |