这篇是继线性表，链表，哈夫曼树后的第四篇，数据结构复习性随笔。
本篇将带您重温栈模型的魅力。栈简单说就是“后进先出”。
本篇给出两了完美运行的程序，分别是：栈结构和链栈结构。偶觉得熟练运用这两了程序栈基本也就掌握了。
下面是源码：
#define MAX 1024
#define dataType int
using namespace std;
// 栈结构
typedef struct {
dataType data[MAX];
int top;
}SeqStack, * s;
// 栈的初始化
SeqStack * Init_SeqStack(){
SeqStack * s;
s = (SeqStack * )malloc( sizeof (SeqStack));
if ( ! s){
cout << " 空间不足 " << endl;
return NULL;
}
else {
s -> top =- 1 ;
return s;
}
}
// 判别栈空
int Empty_SeqStack(SeqStack * s){
if (s -> top ==- 1 )
return 1 ;
else
return 0 ;
}
// 入栈
int Push_SeqStack(SeqStack * s,dataType x){
if (s -> top == MAX - 1 )
return 0 ;
else {
s -> top ++ ;
s -> data[s -> top] = x;
return 1 ;
}
}
// 查询栈中是否存在元素值
int Check_SeqStack(SeqStack * s,dataType x){
if (Empty_SeqStack(s))
return 0 ;
else {
for ( int i = s -> top;i >- 1 ;i -- ){
if (s -> data[i] == x)
return 1 ;
}
return 0 ;
}
}
// 头元素出栈
int Pop_SeqStack(SeqStack * s){
if (Empty_SeqStack(s))
return 0 ;
else {
s -> top -- ;
return 1 ;
}
}
// 读取栈内信息
void Read_SeqStack(SeqStack * s){
if (Empty_SeqStack(s))
cout << " 栈中没有元素! " << endl;
else {
cout << endl;
cout << " 栈内元素有： " << endl;
for ( int i = s -> top;i >- 1 ;i -- ){
cout << s -> data[i] << " " ;
}
}
}
// 借助另一个栈实现删除站内任意元素
int Delete_SeqStack(SeqStack * s,dataType x){
if (Check_SeqStack(s,x)){
SeqStack * tool;
tool = Init_SeqStack();
if (Empty_SeqStack(s))
return 0 ;
else {
for ( int i = s -> top;i >- 1 ;i -- ){
if (s -> data[i] != x){
Push_SeqStack(tool,s -> data[i]);
Pop_SeqStack(s);
} else {
Pop_SeqStack(s);
for ( int j = tool -> top;j >- 1 ;j -- ){
Push_SeqStack(s,tool -> data[j]);
Pop_SeqStack(tool);
}
break ;
}
}
return 1 ;
}
} else {
cout << " 该数值在栈中不存在! " << endl;
}
}
// 取栈顶元素
dataType Top_SeqStack(SeqStack * s){
if (Empty_SeqStack(s))
return 0 ;
else
return s -> data[s -> top];
}
int main(){
cout << " 初始化栈
.
"
<<
endl;SeqStack * s;
s = Init_SeqStack();
cout << " 建立空栈完成! " << endl;
dataType num;
cout << " 开始入栈(如果操作完毕请输入'00') " << endl;
bool over = true ;
while (over){
cout << " 请输入您要入栈的元素： " << endl;
cin >> num;
if (num != 00 ){
if (Push_SeqStack(s,num))
cout << " 入栈成功! " << endl;
else
cout << " 入栈失败! " << endl;
} else {
over = false ;
}
}
Read_SeqStack(s);
cout << " 元素出栈(如果操作完毕请输入'00') " << endl;
over = true ;
while (over){
cout << " 请输入您要出栈的元素值： " << endl;
cin >> num;
if (num != 00 ){
if (Delete_SeqStack(s,num))
cout << " 元素出栈成功! " << endl;
else
cout << " 元素出栈失败! " << endl;
} else {
over = false ;
}
}
Read_SeqStack(s);
return 0 ;
}
下面是链栈源码：是借助头结点操作的。说起来也挺郁闷的，这个程序的删除链栈任意元素的算法，我写了好久，
看来指针的使用还是很生啊。我尝试了很多方法，但是指针总是乱指，出一些莫名其妙的数，真是让我郁闷了好久。
不过总算是让我调试好了，其实开着也挺简单的，但是就是写起来总出错。看来代码是靠写的，不是靠看的。
#define dataType int
using namespace std;
// 链栈结构
typedef struct Node{
dataType data;
struct Node * next;
}StackNode, * LinkStack;
LinkStack top;
// 置空栈
LinkStack Init_LinkStack(){
return NULL;
}
// 判别栈空
int Empty_LinkStack(LinkStack top){
if (top == NULL)
return 1 ;
else
return 0 ;
}
// 链栈入栈
LinkStack Push_LinkStack(LinkStack top,dataType x){
StackNode * s;
s = new StackNode;
s -> data = x;
s -> next = top;
top = s;
return top;
}
// 头元素出栈
LinkStack Pop_LinkStack(LinkStack top){
StackNode * p;
if (top == NULL)
return NULL;
else {
p = top;
top = top -> next;
delete p;
return top;
}
}
// 查找数值是否寻在
int Check_LinkStack(LinkStack top,dataType x){
if (top == NULL)
cout << " 栈内没有元素 " << endl;
else {
StackNode * s;
for (s = top;s != NULL;){
if (s -> data == x)
return 1 ;
else
s = s -> next;
}
return 0 ;
}
}
// 输出链栈
void Read_LinkStack(LinkStack top){
if (top == NULL)
cout << " 栈内元素为空 " << endl;
else {
StackNode * s;
cout << endl;
cout << " 栈内元素为: " << endl;
for (s = top;s != NULL;){
cout << s -> data << " " ;
s = s -> next;
}
}
}
// 借助一个链栈实现删除栈内任意元素
LinkStack Delete_LinkStack(LinkStack top,dataType x){
if (Check_LinkStack(top,x)){
LinkStack tool;
tool = Init_LinkStack();
if (Empty_LinkStack(top))
// return 0;
cout << " 链栈是空栈 " << endl;
else {
StackNode * s, * k, * p;
for (;top != NULL;){
if (top -> data != x){
tool = Push_LinkStack(tool,top -> data);
top = Pop_LinkStack(top);
} else {
top = Pop_LinkStack(top);
for (;tool != NULL;){
top = Push_LinkStack(top,tool -> data);
tool = Pop_LinkStack(tool);
}
break ;
}
}
return top;
}
} else {
cout << " 该数值在栈中不存在! " << endl;
}
}
// 主函数
int main(){
int num;
bool over = true ;
cout << " 建立链栈
.
"
<<
endl;LinkStack top;
top = Init_LinkStack();
cout << " 链栈初始化完成 " << endl;
cout << " ----入栈操作(如果操作完毕请输入'00')---- " << endl;
while (over){
cout << " 请输入您要入栈的元素： " << endl;
cin >> num;
if (num != 00 ){
top = Push_LinkStack(top,num);
cout << " 入栈成功! " << endl;
}
else {
cout << " ----停止入栈---- " << endl;
over = false ;
}
}
Read_LinkStack(top);
cout << " ----出栈操作(如果操作完毕请输入'00')---- " << endl;
over = true ;
while (over){
cout << " 请输入您要出栈的元素值： " << endl;
cin >> num;
if (num != 00 ){
if (top = Delete_LinkStack(top,num))
cout << " 元素出栈成功! " << endl;
else
cout << " 元素出栈失败! " << endl;
} else
over = false ;
}
Read_LinkStack(top);
return 0 ;
}
以上两个程序都完美运行，而且用的C++标准写法。
本文转自施杨博客园博客，原文链接：http://www.cnblogs.com/shiyangxt/archive/2008/12/19/1358111.html，如需转载请自行联系原作者
