- 栈的定义:只能在表的一端进行插入和删除元算的线性表,后进先出的规则,凡是在逻辑上需要“后进先出”的操作和过程都能用上栈。一些具体应用有:函数的求值,过程的调用与返回,递归过程的实现
- 栈的基本运算:入栈(插入)、出栈(删除)、置栈空、判断是否为空、取栈顶元素
//stack chain storage structure
#include<iostream>
using namespace std;
class stack_chain;
class node{
public:
friend class stack_chain;
private:
char _data;
node* _next;
};
class stack_chain{
public:
stack_chain(){_top=0;}
~stack_chain(); //release memory
bool push(char& c); //push c into stack
bool pop(); //remove an element from stack
bool get_top(char& c); //get top element
void clear(); //clear stack
void display();
private:
node* _top;
int _length;
};
stack_chain::~stack_chain(){
clear();
}
bool stack_chain::push(char& c){
node* tmp = new node;
tmp->_data = c;
tmp->_next=_top;
_top= tmp;
_length++;
return true;
}
bool stack_chain::pop(){
if(_top==0) return false;
node* tmp=_top;
_top=tmp->_next;
delete tmp;
_length--;
return true;
}
bool stack_chain::get_top(char& c){
if(_top==0) return false;
c=_top->_data;
return true;
}
void stack_chain::clear(){
node* tmp;
while(_top!=0){
tmp=_top;
_top=_top->_next;;
delete tmp;
}
}
void stack_chain::display(){
node* tmp=_top->_next;
while(tmp!=0){
cout << tmp->_data;
tmp= tmp->_next;
}
cout << endl;
}
int main(){
char str[]="stack chain test...";
stack_chain link;
for(int i=0; str[i]!=0; i++) link.push(str[i]);
link.display();
link.pop();
char t;
link.get_top(t);
cout << t << endl;
link.clear();
return 0;
}