一膳音、基于deque實現(xiàn)
優(yōu)點：利用deque動態(tài)管理內存召衔，棧的內存無上限，STL中的棧也是基于deque實現(xiàn)的祭陷。
template<class T> class MyStack{
deque<T> dq;
public:
void push(T element){
dq.push_back(element);
}
void pop(){
assert(!empty());
dq.pop_back();
}
bool empty(){
return dq.empty();
}
T& top(){
assert(!empty());
return dq.back();
}
};
二苍凛、基于數(shù)組實現(xiàn)
數(shù)組可選靜態(tài)數(shù)組或動態(tài)數(shù)組，兩種實現(xiàn)方式類似兵志，都需要預選設定一個棧的最大容量醇蝴。優(yōu)點在于：實現(xiàn)簡單，支持隨機存儲想罕；缺點是空間受限悠栓。
typedef int TYPE;
const int STACK_SIZE = 100;
TYPE MysSack[STACK_SIZE];
int top_pos = -1;
bool isEmpty(){
return top_pos == -1;
}
bool isFull(){
return top_pos == STACK_SIZE - 1;
}
void push(TYPE element){
assert(!isFull());
MysSack[++top_pos] = element;
}
void pop(){
assert(!isEmpty());
--top_pos;
}
TYPE& top(){
assert(!isEmpty());
return MysSack[top_pos];
}
3、基于鏈表實現(xiàn)
優(yōu)點是：存儲空間不收限制；缺點是惭适，需要存儲額外的鏈接信息笙瑟，并且
銷毀棧需要O(n)的時間。
typedef int TYPE;
typedef struct STACK_NODE {
TYPE value;
struct STACK_NODE *next;
} StackNode;
static StackNode *MyStack;
int isEmpty(void){
return MyStack == NULL;
}
int isFull(void){
return FALSE;
}
void pop(void) {
StackNode *first_node;
assert(!isEmpty());
first_node = MyStack;
MyStack = first_node->next;
free(first_node);
}
void push(TYPE value) {
StackNode *new_node;
new_node = (StackNode *)malloc(sizeof(StackNode));
if(new_node == NULL)
perror("malloc fail");
new_node->value = value;
new_node->next = MyStack; /* 新元素插入鏈表頭部 */
MyStack = new_node; /* stack 重新指向鏈表頭部 */
}
TYPE top(void) {
assert(!isEmpty());
return MyStack->value;
}
void destroy_stack(void) {
while(!isEmpty())
pop(); /* 逐個彈出元素腥沽，逐個釋放節(jié)點內存 */
}
