StaticStack.h
#ifndef STATICSTACK_H
#define STATICSTACK_H
#include "Stack.h"
#include "Exception.h"
namespace DTLib
{
template < typename T, int N >
class StaticStack : public Stack<T>
{
protected:
T m_space[N];
int m_top;
int m_size;
public:
StaticStack() // O(1)
{
m_top = -1;
m_size = 0;
}
int capacity() const // O(1)
{
return N;
}
void push(const T& e) // O(1)
{
if( m_size < N )
{
m_space[m_top + 1] = e; // 为了异常安全，先复制后改动标识，因为是类型T可能存在异常
m_top++;
m_size++;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No space in current stack ...");
}
}
void pop() // O(1)
{
if( m_size > 0 )
{
m_top--;
m_size--;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
}
}
T top() const // O(1)
{
if( m_size > 0 )
{
return m_space[m_top];
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
}
}
void clear() // O(1)
{
m_top = -1;
m_size = 0;
}
int size() const // O(1)
{
return m_size;
}
};
}
#endif // STATICSTACK_H
LinkStack.h
#ifndef LINKSTACK_H
#define LINKSTACK_H
#include "Stack.h"
#include "LinkList.h"
namespace DTLib
{
template < typename T >
class LinkStack : public Stack<T>
{
protected:
LinkList<T> m_list; // 组合使用单链表类
public:
void push(const T& e) // O(1)
{
m_list.insert(0, e);
}
void pop() // O(1)
{
if( m_list.length() > 0 )
{
m_list.remove(0);
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
}
}
T top() const // O(1)
{
if( m_list.length() > 0 )
{
return m_list.get(0);
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current stack ...");
}
}
void clear() // O(n)
{
m_list.clear();
}
int size() const // O(1)
{
return m_list.length();
}
};
}
#endif // LINKSTACK_H
使用单链表对象实现链式栈时，为什么选择在单链表的头部进行操作？如果选择在尾部进行操作是否也能实现栈的功能？
先进先出( First In First Out )
StaticQueue.h
#ifndef STATICQUEUE_H
#define STATICQUEUE_H
#include "Queue.h"
#include "Exception.h"
namespace DTLib
{
template < typename T, int N >
class StaticQueue : public Queue<T>
{
protected:
T m_space[N];
int m_front;
int m_rear;
int m_length;
public:
StaticQueue()
{
m_front = 0;
m_rear = 0;
m_length = 0;
}
int capacity() const // O(1)
{
return N;
}
void add(const T& e) // O(1)
{
if( m_length < N )
{
m_space[m_rear] = e;// 为了异常安全，先复制后改动标识，因为是类型T可能存在异常
m_rear = (m_rear + 1) % N;
m_length++;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No space in current queue ...");
}
}
void remove() // O(1)
{
if( m_length > 0 )
{
m_front = (m_front + 1) % N;
m_length--;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
}
}
T front() const // O(1)
{
if( m_length > 0 )
{
return m_space[m_front];
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
}
}
void clear() // O(1)
{
m_front = 0;
m_rear = 0;
m_length = 0;
}
int length() const // O(1)
{
return m_length;
}
};
}
#endif // STATICQUEUE_H
LinkQueue.h
使用LinkList类实现链式队列是否合适，是否有更好的方案？
时间复杂度较高
LinkQueue.h
#ifndef LINKQUEUE_H
#define LINKQUEUE_H
#include "Queue.h"
#include "LinuxList.h"
#include "Exception.h"
namespace DTLib
{
template < typename T >
class LinkQueue : public Queue<T>
{
protected:
struct Node : public Object // 结点类型
{
list_head head; // Linux内核链表结点的结构体成员
T value; // 数据域
};
list_head m_header;// 头结点
int m_length;//当前队列长度
public:
LinkQueue() // O(1)
{
m_length = 0;
INIT_LIST_HEAD(&m_header); // Linux链表头结点初始化
}
void add(const T& e) // O(1)
{
Node* node = new Node();
if( node != NULL )
{
node->value = e;
list_add_tail(&node->head, &m_header); // O(1)插入到链表的尾部
m_length++;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to add new element ...");
}
}
void remove() // O(1)
{
if( m_length > 0 )
{
list_head* toDel = m_header.next;
list_del(toDel);
m_length--;
delete list_entry(toDel, Node, head);
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
}
}
T front() const // O(1)
{
if( m_length > 0 )
{
return list_entry(m_header.next, Node, head)->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No element in current queue ...");
}
}
void clear() // O(n)
{
while( m_length > 0 )
{
remove();
}
}
int length() const // O(1)
{
return m_length;
}
~LinkQueue() // O(n)
{
clear();
}
};
}
#endif // LINKQUEUE_H
栈和队列在实现上非常类似，是否可以用栈实现队列？
用栈实现队列等价于用“后进先出”的特性实现“先进先出”的特性！
反之，是否可以用队列实现栈？
本质为，用队列“先进先出”的特性实现栈“后进先出”的特性！
