栈 C++详解（数据结构）
详解一
像数组或链表一样，栈也是一种数据结构，它包含一系列元素。
但是，与数组和链表不同的是，栈是一个后进先出（LIFO）的结构，这意味着当一个程序从栈中检索元素时，插入到栈中的最后一个元素是第一个被检索的元素（同样，插入的第一个元素是最后一个被检索的元素）。
在想象一个栈的工作方式时，可以想象一下餐厅流水线开始时的一堆盘子。当餐厅的工作人员补充餐盘时，他或她放入的第一个盘子将是最后一个被取走的，如图 1 所示。
图 1 栈的后进先出方式就像餐厅盘子的取用方式
餐厅中一堆盘子的LIFO特性也是栈数据结构的主要特征。放在栈上的最后一个数据元素是从栈中检索的第一个数据。
有以下两种类型的栈数据结构：
- 静态栈：又称"顺序栈"。具有固定大小，并以数组形式实现；
- 动态栈：又称"链栈"。可根据需要增长，并以链表形式实现；
栈的应用
如果某个算法需要首先处理序列中最后保存的元素，那么栈对于这种算法而言是非常有用的数据结构。
例如，计算机系统在执行程序时就会使用栈。当某个函数被调用时，计算机系统会将程序的返回地址、函数的参数以及函数的局部变量保存在栈中。当函数返回时，这些局部变量、参数和返回的地址等都将被从栈上删除。
栈操作
栈有两个主要操作：入栈（push，也被称为压栈）和出栈（pop，也被称为弹栈）。
入栈操作会导致一个值被存储，或者被压入栈。例如，假设有一个空的整数栈，最多可以保存 3 个值。有了这个栈，则可以执行以下入栈操作：
push(5);
push(10);
push(15);
图 2 显示了在执行这些入栈操作之后的栈状态。
图 2 入栈操作图解
出栈操作将从栈中检索（继而删除）一个值。假设要在如图 2 所示的栈上执行 3 个连续的出栈操作，结果将如图 3 所示。
图 3 出栈操作图解
实验二
实验名称：栈的基本操作
实验目的：掌握栈的结构特点并熟悉栈的基本操作。
实验要求：编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能：
1、 采用链式存储实现栈的初始化、判空、入栈、出栈操作。
实验步骤及内容：
1、首先建立一个定义多项式的结构体stacknode，及结构体指针LinkStack，该结构体包含一个数据域data，一个指向下一项的指针*next,代码如下：
typedef struct stacknode
{
int data;
struct stacknode *next;
}stacknode,*LinkStack;
2、栈的初始化，代码如下：
//栈的初始化
void InitStack(LinkStack &top)
{
top = new stacknode;
top ->next = NULL;
}
3、入栈，首先开辟内存空间，并将新开辟的结点插入在此栈的后面。具体的代码如下：
//入栈函数
LinkStack push(LinkStack &top,int value)
{
LinkStack p = new stacknode;
if(p != NULL)
{
p ->data = value;//可以理解为在链表尾部插入一个节点。
p ->next = top ->next;
top ->next = p;
}
else
cout << "没有内存可分配" << endl;
return top;
}
5、出栈，从栈中删除一个结点。首先我们必须开辟一个结点用来存储top结点的下一个结点，然后将top->next 执行下下一个结点，这样就删除了一个结点。
int pop(LinkStack &top)
{
LinkStack temp = new stacknode;
int data;
if(StackEmpty(top))
cout << "该栈为空！" << endl;
else
{
temp = top ->next;//可以理解为删除一个节点
data = temp ->data;
top ->next = temp ->next;
delete(temp);
}
return data;
}
6、打印栈，此函数用来对栈进行输出验证。
//打印函数
void Print(LinkStack &top)
{
LinkStack top1 = top; //时刻要注意，我们不可以改变链表本身的值及指向，不过我们可以找别人来完成此事。
if(top1 ->next == NULL)
cout << "该栈为空！"<< endl;
else
{
while(top1 ->next != NULL)
{
cout << top1->next ->data<< " ";//top本身data为，此为不带头节点的链表
top1 = top1 ->next;
}
}
}
7、去栈顶元素，如果不为空则取出栈顶元素。
//取栈顶元素
int StackTop(LinkStack &top)
{
LinkStack p = top;
if(StackEmpty(p))
cout << "该栈为空！" << endl;
else
{
return p ->next ->data;
}
}
8、获取栈的长度，必须临时开辟一个新的结构体指针，作为top的副本，这样就不会破坏top本身的结构了，而且对于top的副本，我们也不能对其空间进行释放，不然top的最后一个next不会为NULL，而是一个不确定的值，这样对以后的操作造成破坏。
//获得栈的长度
int StackLength(LinkStack &top)
{
int length = 0;
LinkStack q = top;
while(q ->next != NULL)
{
length ++;
q = q ->next;
}
return length;
}
9、销毁栈，就是从栈顶开始一个节点一个节点的释放。
//销毁栈
void DestroyStack(LinkStack &top)
{
LinkStack p;
while(top)
{
p = top ->next;//保存top的下一个位置。
delete top;
top = p;
}
cout << "销毁成功！" << endl;
}
链表可以往后插，也可以往前插。
如果我们用 每次往后用p - > next = NULL;叫做 往后插。
1 // zhan.cpp : 定义控制台应用程序的入口点。2 //3 4 #include "stdafx.h"5 #include 6 using namespace std;7 typedef struct stacknode8 {9 int data;10 struct stacknode *next;11 }stacknode,*LinkStack;12 13 //判断栈为空14 int StackEmpty(LinkStack &top)15 {16 if(top ->next == NULL)17 return 1;18 else 19 return 0;20 }21 22 //入栈函数23 LinkStack push(LinkStack &top,int value)24 {25 LinkStack p = new stacknode;26 if(p != NULL)27 {28 p ->data = value;//可以理解为在链表尾部插入一个节点。29 p ->next = top ->next;30 top ->next = p;31 }32 else 33 cout << "没有内存可分配" << endl;34 return top;35 }36 37 //出栈函数38 int pop(LinkStack &top)39 {40 LinkStack temp = new stacknode;41 int data;42 if(StackEmpty(top))43 cout << "该栈为空！" << endl;44 else 45 {46 temp = top ->next;//可以理解为删除一个节点47 data = temp ->data;48 top ->next = temp ->next;49 delete(temp);50 }51 return data;52 }53 54 //打印函数55 void Print(LinkStack &top)56 {57 LinkStack top1 = top; //时刻要注意，我们不可以改变链表本身的值及指向，不过我们可以找别人来完成此事。58 if(top1 ->next == NULL)59 cout << "该栈为空！"<< endl;60 else61 {62 while(top1 ->next != NULL)63 {64 cout << top1->next ->data<< " ";//top本身data为0，此为不带头节点的链表65 top1 = top1 ->next;66 }67 }68 }69 70 //取栈顶元素71 int StackTop(LinkStack &top)72 {73 LinkStack p = top;74 if(StackEmpty(p))75 cout << "该栈为空！" << endl;76 else 77 {78 return p ->next ->data;79 }80 81 }82 83 //获得栈的长度84 int StackLength(LinkStack &top)85 {86 int length = 0;87 LinkStack q = top;88 while(q ->next != NULL)89 {90 length ++;91 q = q ->next;92 }93 return length;94 }95 96 //销毁栈97 void DestroyStack(LinkStack &top)98 {99 LinkStack p;
100 while(top)
101 {
102 p = top ->next;//保存top的下一个位置。
103 delete top;
104 top = p;
105 }
106 cout << "销毁成功！" << endl;
107 }
108
109 //栈的初始化
110 void InitStack(LinkStack &top)
111 {
112 top = new stacknode;
113 top ->next = NULL;
114 }
115
116 //前导函数
117 void printscreen(void)
118 {
119 cout<<"0------退出程序"<> n;
139 while(n) //输入0也可以退出循环
140 {
141 switch(n)
142 {
143 case 1 : //入栈操作
144 cout << "请输入一个整数" <> value;
146 while(value!=0) //以0作为结束条件
147 {
148 push(top,value);
149 cin >> value;
150 }
151 Print(top); //打印栈
152 cout << endl;
153 break;
154 case 2: //出栈操作
155 if(top ->next != NULL)
156 cout << "弹出的元素是："<< pop(top) << endl;
157 break;
158 case 3: //取栈顶元素
159 cout << StackTop(top) << endl;
160 break;
161 case 4: //判断栈是否为空
162 if(StackEmpty(top))
163 cout << "该栈为空！" << endl;
164 else
165 cout << "该栈不为空！" << endl;
166 break;
167 case 5: //返回栈的元素个数
168 if(StackEmpty(top) == 0)
169 cout << StackLength(top)<> n;
190 }
191 end: ;
192 return 0;
193 } 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！