【数据结构】链式栈 Linked_stack
08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://blog.****.net/xiaowei_cqu/article/details/7747205
链式栈各种基本运算算法的实现
栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底（push），最后的数据在栈顶（top），需要读数据的时候从栈顶开始弹出数据（top）最后一个数据被第一个读出来。
链式栈中的元素以Node的形式存储，节点Node中存有此节点存于栈中的元素以及指向下个节点的指针。链式栈的数据成员只用保存指向栈顶节点的指针 *top_node.
因为指针的运用，链式栈在实现时尤其重要的一点就是编写自己的析构函数，拷贝构造函数和重载赋值运算符。
链式栈中的元素以Node的形式存储，节点Node中存有此节点存于栈中的元素以及指向下个节点的指针。链式栈的数据成员只用保存指向栈顶节点的指针 *top_node.
因为指针的运用，链式栈在实现时尤其重要的一点就是编写自己的析构函数，拷贝构造函数和重载赋值运算符。
【实验说明】
我选择的题目是测试链式栈的各种功能1.链式栈中元素以节点形式存储，首先编写结构Node的定义和实现。
2.编写栈的定义和实现。栈中数据成员是指向栈顶的指针*top_node。成员函数是实现栈最基本的操作——push()向栈中加入元素，pop()移出栈顶元素,top()得到栈顶元素，empty()判断栈是否为空。
3.编写链式栈的析构函数~Stack()，拷贝构造函数Stack(const Stack &original),重载赋值运算符operator=(const Stack &original)；
4.编写用于测试栈的各种功能的函数 do_comman()和get_command()以及一些辅助的介绍函数introduction(),help()。
5.编写主函数。运行并测试栈的各种功能。
【相关代码】
node.h
#ifndef NODE_H
#define NODE_H
#include<iostream>
using namespace std;
enum Error_code{success,overflow,underflow};
typedef char Node_entry;
struct Node{
//data members
Node_entry entry;
Node *next;
//constructors
Node();
Node(Node_entry item,Node *add_on=NULL);
};
#endifnode.cpp
#include "node.h"
Node::Node()
{
next=NULL;
}
Node::Node(Node_entry item, Node *add_on)
{
entry=item;
next=add_on;
}#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H
#include "node.h"
typedef char Stack_entry;
class Stack{
public:
//constructor
Stack();
//member functions
bool empty()const;
Error_code push(const Stack_entry &item);
Error_code pop();
Error_code top(Stack_entry &item)const;
//destructor
~Stack();
//copy constructor
Stack(const Stack &original);
//overload assignment
void operator=(const Stack &original);
protected:
//data member
Node *top_node;
};
#endif#include "linked_stack.h"
//constructor
Stack::Stack(){
top_node=NULL;
}
//function empty() to check if the stack is empty
bool Stack::empty() const{
if(top_node==NULL)
return true;
else
return false;
}
//function pushh(const Stack_entry &item) to push item into the stack
Error_code Stack::push(const Stack_entry &item)
{
Node *new_top=new Node(item,top_node);
if(new_top==NULL)
return overflow;
top_node=new_top;
return success;
}
//function pop() to pop the last item int the stack
Error_code Stack::pop()
{
Node *old_top=top_node;
if(top_node==NULL)
return underflow;
top_node=old_top->next;
delete old_top;
return success;
}
//function top(Stack_entry &item) to assig item with the top item in the stack
Error_code Stack::top(Stack_entry &item)const{
if(top_node==NULL)
return underflow;
item=top_node->entry;
return success;
}
//destructor
Stack::~Stack()
{
while(!empty())
pop();
}
//overload assignment
void Stack::operator=(const Stack &original)
{
Node *new_top,*new_copy,*original_node=original.top_node;
if(original_node==NULL)new_top=NULL;
else{
new_copy=new_top=new Node(original_node->entry);
while(original_node->next!=NULL){
original_node=original_node->next;
new_copy->next=new Node(original_node->entry);
new_copy=new_copy->next;
}
}
while(!empty())
pop();
top_node=new_top;
}
//copy constructor
Stack::Stack(const Stack &original)
{
Node *new_copy,*original_node=original.top_node;
if(original_node==NULL)
top_node=NULL;
else{
top_node=new_copy=new Node(original_node->entry);
while(original_node->next!=NULL){
original_node=original_node->next;
new_copy->next=new Node(original_node->entry);
new_copy=new_copy->next;
}
}
}【过程记录】
实验截图：
【结果分析】
1.链式栈中以节点的形式存储栈中的元素，每个节点Node由要保存的元素entry和指向下一个节点的指针next组成。这样大大避免了由连续数组实现栈所带来的限制——不用从一开始就限定栈可存储元素的大小，在添加新的元素时再申请空间，而且节省了不必要的空间。因为节点的存储在物理结构上不一定是连续的，只有内存不足时才会达到full的状态（通常情况是够用的）。
2.指针的运用是件巧妙而又危险的工作。在每改变一个元素（添加或删除）都应注意指针知否指向了正确的地址，避免悬空指针和内存泄露。
3.因为指针的运用，编写Stack类时必须编写自己析构函数，拷贝构造函数以及赋值操作符。
2.指针的运用是件巧妙而又危险的工作。在每改变一个元素（添加或删除）都应注意指针知否指向了正确的地址，避免悬空指针和内存泄露。
3.因为指针的运用，编写Stack类时必须编写自己析构函数，拷贝构造函数以及赋值操作符。