(TIL) C++ Stack, Queue, …
업데이트:
오늘은 본격적으로 스택, 큐, Double-ended 큐에 대해서 배워보았다.
Stack
스택은 last-in first-out의 원칙을 가지고 있는 자료구조이다. 스택 속에 자료는 언제나 추가될 수 있지만 반드시 가장 마지막에 추가된 자료부터 불러올 수 있다. 이 연산들을 각각 push/pop이라고 부른다. top은 가장 마지막에 추가된, 개념적으로는 가장 위에 있는 원소를 가리킨다. C++의 STL에서는 stack의 구현을 제공한다. C++에서 Stack을 쓰려면 다음과 같이 코드를 작성하면 된다.
#include <stack>
using std::stack;
stack<T> myStack;
다만 개념적인 stack 구현과 STL의 stack 구현의 다른 점은 STL의 stack에서는 빈 스택에 대한 top이나 pop 연산에 대한 결과가 정의되어 있지 않다는 것이다. 그래서 빈 스택에 저 연산을 쓰더라도 예외가 발생하지 않는다. 그러나 이 stack을 쓰고 있는 프로그램 자체는 에러를 뿜어낼 것이다. 그래서 예외 처리에 신경 써야 한다.
C++에서의 Stack 구현
C++에서 Stack을 구현하는 방법은 2가지가 있다.
- 단순 배열로 구현
- 연결 리스트로 구현
먼저 단순 배열로 구현하는 법에 대해서 살펴보겠다.
template <typename E>
class ArrayStack {
enum { DEF_CAPACITY = 100 }; // default stack capacity
public:
ArrayStack(int cap = DEF CAPACITY); // constructor from capacity
int size() const; // number of items in the stack
bool empty() const; // is the stack empty?
const E& top() const throw(StackEmpty); // get the top element
void push(const E& e) throw(StackFull); // push element onto stack
void pop() throw(StackEmpty); // pop the stack
// . . .housekeeping functions omitted
private: // member data
E* S; // array of stack elements
int capacity; // stack capacity
int t; // index of the top of the stack
};
template <typename E> ArrayStack<E>::ArrayStack(int cap)
: S(new E[cap]), capacity(cap), t(−1) { } // constructor from capacity
template <typename E> int ArrayStack<E>::size() const
{ return (t + 1); } // number of items in the stack
template <typename E> bool ArrayStack<E>::empty() const
{ return (t < 0); } // is the stack empty?
template <typename E> // return top of stack
const E& ArrayStack<E>::top() const throw(StackEmpty) {
if (empty()) throw StackEmpty("Top of empty stack");
return S[t];
}
template <typename E> // push element onto the stack
void ArrayStack<E>::push(const E& e) throw(StackFull) {
if (size() == capacity) throw StackFull("Push to full stack");
S[++t] = e;
}
template <typename E> // pop the stack
void ArrayStack<E>::pop() throw(StackEmpty) {
if (empty()) throw StackEmpty("Pop from empty stack");
−−t;
}
stack의 추상 자료형의 정의와 달리 여기엔 StackFull 예외가 있는데 이것은 배열을 사용했기 때문이다. 배열은 크기를 임의로 변경할 수 없다. 그러나 이 구현의 문제점은 배열의 문제점과 같다. stack의 크기가 꽉 찼을 때 크기를 늘리는 비용이 너무 비싸다. 이 단점을 극복할 수 있는 방법이 바로 stack을 일반화 연결리스트로 구현하는 것이다. 코드는 아래와 같다.
typedef string Elem; // stack element type
class LinkedStack { // stack as a linked list
public:
LinkedStack(); // constructor
int size() const; // number of items in the stack
bool empty() const; // is the stack empty?
const Elem& top() const throw(StackEmpty); // the top element
void push(const Elem& e); // push element onto stack
void pop() throw(StackEmpty); // pop the stack
private: // member data
SLinkedList<Elem> S; // linked list of elements
int n; // number of elements
};
LinkedStack::LinkedStack()
: S(), n(0) { } // constructor
int LinkedStack::size() const
{ return n; } // number of items in the stack
bool LinkedStack::empty() const
{ return n == 0; } // is the stack empty?
const Elem& LinkedStack::top() const throw(StackEmpty) {
if (empty()) throw StackEmpty("Top of empty stack");
return S.front();
}
void LinkedStack::push(const Elem& e) { // push element onto stack
++n;
S.addFront(e);
}
// pop the stack
void LinkedStack::pop() throw(StackEmpty) {
if (empty()) throw StackEmpty("Pop from empty stack");
−−n;
S.removeFront();
}
이 코드에서 주의할 점은 연결리스트를 직접 구현하지는 않았다는 것이다. 대신 string 타입을 원소 자료형으로 지정했다. string 말고 진짜 연결리스트를 쓰고 싶다면 직접 구현하여 사용하면 된다. 모든 stack의 구현의 모든 연산의 시간복잡도는 O(1)이고 공간복잡도는 O(N) (N은 stack의 크기)이다.
Queues
queue는 first-in first-out의 원칙을 가진 자료형이다. 모든 원소는 큐의 마지막 원소인 rear 뒤에 삽입되고 맨 앞 원소인 front부터 삭제된다. 삽입 연산을 enqueue라고 부르고 삭제 연산을 dequeue라고 부른다. queue 역시 STL에서 기본적인 구현을 제공한다. 이를 사용하고 싶다면 아래와 같이 하면 된다.
#include <queue>
using std::queue;
queue<T> myQueue;
queue를 단순 배열로 구현하게 되면 문제가 생긴다. front와 rear를 어떻게 추적하고 유지할 것인가이다. queue는 원소를 맨 앞에서부터 삭제하기 때문에 배열이 overflow되지 않게 하려면 삭제할 때마다 원소들을 한 칸씩 옮겨줘야 한다. 이렇게 되면 dequeue 연산의 시간복잡도가 O(N) (N은 원소의 개수)이 될 것이다. 이 문제를 해결하려면 다른 방법이 필요하다.
해법은 다음과 같다. front 원소의 현재 index를 저장하고 있는 f라는 변수와 rear 원소의 현재 index를 저장하고 있는 r이라는 변수, 그리고 현재 원소의 개수를 나타내는 N이라는 변수를 선언한다. 그리고 원소가 추가되면 r과 N을 1씩 증가시키고 원소가 제거되면 f를 증가시키고 N을 1 감소시키는 것이다. 그런데 이렇게 해도 f, r, N이 배열의 마지막 인덱스에 도달했을 때 극복할 방법이 없다. 이때 f와 r을 그냥 증가시키지 말고 증가시킨 뒤에 N으로 나눈 나머지를 대입하여 배열을 순환적으로 사용하면 된다.
비슷한 이유로 단순연결리스트를 통한 구현도 어렵다. 그래서 이때는 단순연결리스트가 아니라 순환연결리스트를 사용하여 queue를 구현한다. 그리고 책에서는 구현의 복잡함을 덜기 위하여 일반화 템플릿을 만들지 않고 string을 사용했다.
typedef string Elem; // queue element type
class LinkedQueue { // queue as doubly linked list
public:
LinkedQueue(); // constructor
int size() const; // number of items in the queue
bool empty() const; // is the queue empty?
const Elem& front() const throw(QueueEmpty); // the front element
void enqueue(const Elem& e); // enqueue element at rear
void dequeue() throw(QueueEmpty); // dequeue element at front
private: // member data
CircleList C; // circular list of elements
int n; // number of elements
};
LinkedQueue::LinkedQueue() // constructor
: C(), n(0) { }
int LinkedQueue::size() const // number of items in the queue
{ return n; }
bool LinkedQueue::empty() const // is the queue empty?
{ return n == 0; }
// get the front element
const Elem& LinkedQueue::front() const throw(QueueEmpty) {
if (empty())
throw QueueEmpty("front of empty queue");
return C.front(); // list front is queue front
}
void LinkedQueue::enqueue(const Elem& e) {
C.add(e); // insert after cursor
C.advance(); // . . .and advance
n++;
}
// dequeue element at front
void LinkedQueue::dequeue() throw(QueueEmpty) {
if (empty())
throw QueueEmpty("dequeue of empty queue");
C.remove(); // remove from list front
n−−;
}
Double-Ended Queues
Double-ended queue는 queue와 비슷하지만 삽입과 삭제가 front와 back 모두에서 가능한 자료구조이다. 역시 deque에 대해서도 C++에서는 STL에서 구현을 제공해주고 있다. 사용하려면 다음과 같이 코드를 적으면 된다.
#include <deque>
using std::deque;
deque<T> myDeque;
이전의 두 자료구조와 같이 배열로 구현하는 것은 의미가 없는지 교재에서 다루지 않고 있다. 다만 이중연결리스트로 구현하는 법에 대해서 소개하고 있다. 코드는 다음과 같다.
typedef string Elem; // deque element type
class LinkedDeque { // deque as doubly linked list
public:
LinkedDeque(); // constructor
int size() const; // number of items in the deque
bool empty() const; // is the deque empty?
const Elem& front() const throw(DequeEmpty); // the first element
const Elem& back() const throw(DequeEmpty); // the last element
void insertFront(const Elem& e); // insert new first element
void insertBack(const Elem& e); // insert new last element
void removeFront() throw(DequeEmpty); // remove first element
void removeBack() throw(DequeEmpty); // remove last element
private: // member data
DLinkedList D; // linked list of elements
int n; // number of elements
};
void LinkedDeque::insertFront(const Elem& e) {
D.addFront(e);
n++;
}
// insert new last element
void LinkedDeque::insertBack(const Elem& e) {
D.addBack(e);
n++;
}
// remove first element
void LinkedDeque::removeFront() throw(DequeEmpty) {
if (empty())
throw DequeEmpty("removeFront of empty deque");
D.removeFront();
n−−;
}
// remove last element
void LinkedDeque::removeBack() throw(DequeEmpty) {
if (empty())
throw DequeEmpty("removeBack of empty deque");
D.removeBack();
n−−;
}
오늘은 여기까지…. 내일은 리스트와 반복자 추상 데이터 타입에 대해서 배운다. 반복자에 대한 개념이 좀 애매했는데 이번 기회에 개념을 확실히 잡아야겠다.
댓글남기기