用栈记录回滚步骤

㈠ 什么是栈回溯

一、栈回溯的概念：
栈回溯就是回溯法，是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

二、算法框架：
1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

㈡ 数据结构实验（用c语言写） 栈的基本操作

//顺序栈
#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#define STACK_INIT_SIZE 100;

#define STACKINCREMENT 10;

typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;

typedef int ElemType;

int InitStack(SqStack &S) //为栈S分配存储空间，并置S为空栈
{
int size = STACK_INIT_SIZE;
S.base=(int *)malloc(size*sizeof(ElemType));
if(!S.base)
return 0;
S.top=S.base; //置栈S为空栈
S.stacksize=STACK_INIT_SIZE;
return 1;
}

int GetTop(SqStack S,int &e) //若栈不空，则用e返回S的栈顶元素
{
if(S.top==S.base) return 0;
e=*(S.top-1);
return 1;

}

int Push(SqStack &S, int e) /*进栈函数,将e插入栈S中,并使之成为栈顶元素*/
{ if(S.top-S.base>=S.stacksize) /*栈满，追加存储空间*/
{
int stackinvrement = STACKINCREMENT;

S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType));
if(!S.base)
return 0; /*存储分配失败*/
S.stacksize+=STACKINCREMENT;
}

*S.top++=e;
return 1;
}

int Pop(SqStack &S,int &e)/*出栈函数,若栈S不空,则删除S的栈顶元素,用e返回其值*/

{ if(S.top==S.base) return 0;

e=*--S.top;
return 1;
}

void OutputStack(SqStack &S)

{int *q;
q=S.top-1;
for(int i=0;i<S.top-S.base;i++)
{

printf("%3d ",*q);q--;}

}

void main()

{

int a,b,c ;
char m;

SqStack s;

InitStack(s);
printf("请输入要进栈的元素个数是:");

scanf("%d",&a);

printf("\n请输入要进栈的%d个元素:",a);

for(b=0;b<a;b++) {
scanf("%d",&c);
Push(s,c); }
do { printf("\n");
printf("*********** 1.输出栈的元素**********\n");
printf("*********** 2.取栈顶元素************\n");
printf("*********** 3.删除栈顶元素**********\n");
printf("*********** 4.退出程序**********\n");
printf("\n请选择一个字符:");
getchar();
scanf("%c",&m);
switch(m) {
case '1': printf("\n输出的栈为:");
OutputStack(s);
break;

case '2': GetTop(s,c);
printf("\n栈顶元素为:%d",c);
printf("\n输出的栈为:");
OutputStack(s);
break;
case '3': Pop(s,c);
printf("\n删除的栈顶元素:%d",c);
printf("\n输出的栈为:");
OutputStack(s);
printf("\n");
break;
case '4':break;
default: printf("输入的数字有错，请重新选择!\n"); break;

}

}while(m!='4');

}
//链栈

#include<stdio.h>
#include<stdlib.h>
typedef struct SNode
{
int data;
struct SNode *next;
}SNode,*LinkStack;
LinkStack top;
LinkStack PushStack(LinkStack top,int x) //入栈
{
LinkStack s;
s=(LinkStack)malloc(sizeof(SNode));
s->data=x;
s->next=top;
top=s;
return top;
}
LinkStack PopStack(LinkStack top) //退栈
{
LinkStack p;
if(top!=NULL)
{
p=top;
top=top->next;
free(p);
printf("退栈已完成\n");
return top;
}
else printf("栈是空的，无法退栈！\n"); return 0;
}
int GetStackTop(LinkStack top) //取栈顶元素
{
return top->data;

}
bool IsEmpty()//bool取值false和true，是0和1的区别,bool只有一个字节,BOOL为int型,bool为布尔型

{
return top==NULL ? true:false;
}
void Print()
{
SNode *p;
p=top;
if(IsEmpty())
{
printf("The stack is empty!\n");
return;
}
while(p)
{
printf("%d ", p->data);
p=p->next;
}
printf("\n");
}

void main()
{

int x,a,b;
char m;
do { printf("\n");
printf("###############链栈的基本操作##################\n");
printf("××××××××1.置空栈××××××××××\n");
printf("××××××××2.进栈×××××××××××\n");
printf("××××××××3.退栈×××××××××××\n");
printf("××××××××4.取栈顶元素××××××××\n");
printf("××××××××5.退出程序×××××××××\n");
printf("##############################################\n");
printf("\n请选择一个字符:");
scanf("%c",&m);
switch(m){
case '1':
top=NULL;
printf("\n栈已置空!");
break;
case '2':
printf("\n请输入要进栈的元素个数是:");
scanf("%d",&a);
printf("\n请输入要进栈的%d个元素:",a);
for(b=0;b<a;b++) {
scanf("%d",&x);
top=PushStack(top,x); }
printf("进栈已完成！\n");
printf("\n输出栈为:");
Print();
break;
case '3':
printf("\n操作之前的输出栈为:");
Print();
top=PopStack(top);
printf("\n操作过后的输出栈为:");
Print();
break;
case '4':
printf("\n输出栈为:");
Print();
if(top!=NULL)
printf("\n栈顶元素是：%d\n",GetStackTop(top));
else
printf("\n栈是空的，没有元素！");
break;
case '5':break;
default:
printf("\n输入的字符不对，请重新输入!");
break;

}
getchar();
}while(m!='5');

}

㈢ 数据结构--用栈实现汉诺塔

递归和堆栈是相通的，能够用递归实现的程序就一定能用堆栈来实现，而用递归实际上是利用了系统的堆栈，把一切责任都推给了操作系统来完成，但是有个问题就是如果我们用堆栈的话我们就必须先定义一个堆栈的数据结构，还是比较麻烦，这样的话，代码量还是比较大的，不过STL可以帮我们解决这个问题。
需要说明的是，这里尽管没有用递归，但是还是没有脱离递归的思想。
在这里我们总是假定盘子的编号从顶端重小到大开始，如图

首先引入一个概念，移动操作，指把一个盘子从一个杆上移动到另外一个杆上的动作，或者把一叠连续放者的盘子整体从一个杆上移动到另外一个杆上的动作。为了便于在计算机中表示我定义了一个class如下：

1 #include <iostream>
2 #include <stack>

3 using namespace std;
4 //define the operation
5 class oprt
6 {
7 public:
8 int begin,end;
9 char src,dst,bri;
10 oprt(){};
11 oprt(int rbegin,int rend,char rsrc,char rdst,char rbri):
12 begin(rbegin),end(rend),src(rsrc),dst(rdst),bri(rbri){}
13 };

为了简化，我把其中的成员都定义成了public(当然了，这不是个好习惯)。Begin,end是指一叠盘子的开始和结束的盘子的标号，begin是标号比较小的盘子，而end是标号比较大的盘子。当begin == end时，表示移动的只是一个盘子。
Src,dst,bri,分别代表3个杆，src:source，dst:destination，bri:bridge。看名字就知道，这3个成员代表什么意思了吧。
同时来定义了一个构造函数用来初始化对象。
14 #define print_oprt(op) cout<<"move disk "<<(op).begin<<" from \'"<<(op).src<<"\' to \'"<<(op).dst<<"\'"<<endl;

为了打印这个移动操作我定义了一个宏，至于为什么是个宏而不是个member function看看后面就知道了。

15 typedef stack<oprt> oprt_stack;

这行没有问题，用oprt_stack来表示堆栈。

16 int hanoi_s(int size,char src,char dst,char bri)
17 {
18 oprt_stack ostack;
19 oprt tmp;
20 ostack.push(oprt(1,size,src,dst,bri));
21 while (!ostack.empty())
22 {
23 tmp = ostack.top();
24 ostack.pop();
25 if (tmp.begin != tmp.end)
26 {
27 ostack.push(oprt(tmp.begin,tmp.end-1,tmp.bri,tmp.dst,tmp.src));
28 ostack.push(oprt(tmp.end,tmp.end,tmp.src,tmp.dst,tmp.bri));
29 ostack.push(oprt(tmp.begin,tmp.end-1,tmp.src,tmp.bri,tmp.dst));
30 }
31 else
32 print_oprt(tmp);
33 }
34 }

接下来，具体说一下工作原理。首先把整个开始的塔的全部盘子作为一个整体移动到目标杆上，也就是行20的代码。
然后我们要做的工作就是用递归的思想，依次弹出堆栈顶部的操作，把堆栈里面的操作依次给它拆开,分2种情况。
1．如果弹出的操作本来就是个原子操作（判断begin 和 end是否相等），也就是说这个操作只移动了一个盘子，那么就把它打印出来(行32)
2. 如果这个不是个原子操作，那么就把它分成3个小的移动操作，然后把这3个小的移动操作分别再压入堆栈（行27-29）。注意压堆栈的顺序和我们移动的操作要相反，因为堆栈是FILO,所以，先移动要后入栈这样才能够保证我们输出的顺序和自然的顺序相同
一直重复上面的步骤，直到堆栈中的每个操作都被分成原子操作然后被弹出为止。这样最后的输出序列就是我们移动盘子的序列。

㈣ 在什么情况下可以用栈来存储数据

堆栈的特点是先进后出，速度快！在单片机设计中主要用于保留现场和恢复现场。在函数的跳转和中断中，堆栈的优点表现得淋漓尽致。

下面是关于堆栈的一些详细讲述：
堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。
要点：
堆：顺序随意
栈：后进先出(Last-In/First-Out)
编辑本段堆和栈的区别
一、预备知识—程序的内存分配
一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后由系统释放。
4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放 。
5、程序代码区—存放函数体的二进制代码。
二、例子程序
这是一个前辈写的，非常详细
//main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[] = "abc"; 栈
char *p2; 栈
char *p3 = "123456"; 123456\0在常量区，p3在栈上。
static int c =0； 全局（静态）初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
}
分配得来得10和20字节的区域就在堆区。
strcpy(p1, "123456"); 123456\0放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。
编辑本段堆和栈的理论知识
1.申请方式

stack:
由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
heap:
需要程序员自己申请，并指明大小，在c中malloc函数
如p1 = (char *)malloc(10);
在C++中用new运算符
如p2 = new char[20];//(char *)malloc(10);
但是注意p1、p2本身是在栈中的。
2.申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。
3.申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
4.申请效率的比较
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈,而是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活
5.堆和栈中的存储内容
栈： 在函数调用时，第一个进栈的是主函数中函数调用后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
6.存取效率的比较

char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的；
而bbbbbbbbbbb是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
比如：
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
}
对应的汇编代码
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中，而第二种则要先把指针值读到edx中，在根据edx读取字符，显然慢了。
7.小结：
堆和栈的区别可以用如下的比喻来看出：
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。
编辑本段堆和栈的区别主要分：
操作系统方面的堆和栈，如上面说的那些，不多说了。
还有就是数据结构方面的堆和栈，这些都是不同的概念。这里的堆实际上指的就是（满足堆性质的）优先队列的一种数据结构，第1个元素有最高的优先权；栈实际上就是满足先进后出的性质的数学或数据结构。
虽然堆栈，堆栈的说法是连起来叫，但是他们还是有很大区别的，连着叫只是由于历史的原因。

㈤ 一、 栈的基本操作 实验目的：了解栈逻辑结构的特点，掌握栈的基本操作，为应用奠定基础。

#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct Stack{
int*base;
int*top;
int size;
}Stack;

void init(Stack*S)
{
S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
S->top=S->base;
S->size=STACK_INIT_SIZE;
}
Stack pushstack(Stack S,int e)
{
if (S.top-S.base==S.size)
{S.base=(int*)realloc(S.base,(S.size+STACKINCREMENT)*sizeof(int));
if(!S.base)
{printf("存储分配失败！");
exit(1);
}
S.top=S.base+S.size;
S.size+=STACKINCREMENT;
}
*S.top++=e;
return S;
}
Stack popstack(Stack S)
{
if(S.top==S.base)exit(1);
--S.top;
return S;
}
int main()
{
int i;
Stack S;
init(&S);
scanf("%d",&i);
S=pushstack(S,i);
printf("%d\n",*(S.top-1));
S=popstack(S);
if(S.top==S.base)
printf("栈为空");
system("pause");
return 0;
}

㈥ 数据结构实验：栈的基本操作

#include<iostream>
using namespace std;

class Stack
{
public:
int size;
int top;
char *stack;
Stack(int m);
bool push(char item);//入栈
bool pop();//出栈
bool isempty();//是否为空
void clear();//清空栈
int Size();//栈中元素个数
~Stack();
char Top();
};
#include<iostream>
#include"Stack.h"
using namespace std;

Stack::Stack(int m){
top=-1;
stack=new char[m];
size = 0;
}

void Stack::clear(){
delete []stack;
size = 0;
stack=NULL;
}

Stack::~Stack(){
clear();
}

bool Stack ::push(char item){
top++;
stack[top]=item;
size++;
return true;
}

bool Stack::isempty(){
if(stack == NULL)
return true;
else
return false;
}

bool Stack::pop(){
if(isempty()){
cout<<"栈为空，不能执行出栈操作！"<<endl;
return false;
}
else{
top--;
size--;
return true;
}
}

int Stack::Size(){
return size;
}
char Stack::Top()
{
return stack[top];
}
#include<iostream>
#include"Stack.h"
using namespace std;
int main()
{
Stack s(20);
char a[50];
char *st = a;
int b=0;
cout<<"请输入你要检查的字符串："<<endl;
cin>>a;
while((*st)!='\0'){b++;
if((*st) == '('||(*st) == '{'||(*st) == '['){
cout<<endl;
cout<<*st<<" 为分隔符左半边"<<endl;
s.push((*st));
}
else if((*st) == '/'&&(*(st+1)) == '*'){
cout<<endl;
cout<<*st<<*(st+1)<<" 为分隔符左半边"<<endl;
s.push((*st));
s.push(*(st+1));
}

else if((*st) == ')'||(*st) == '}'||(*st) == ']'){
if(((*st) ==')'&& (s.Top() =='('))||((*st) =='}'&& (s.Top() =='{'))||((*st) ==']'&& (s.Top() =='['))){
cout<<*st<<" 为分隔符右半边"<<endl;
s.pop();
cout<<"匹配"<<endl;
cout<<endl;}
else {
cout<<*st<<" 为分隔符右半边"<<endl;
cout<<"但 "<<(*st)<<"不匹配"<<endl;
cout<<"第"<<b<<"位"<<endl<<endl;
}
}
else {if((*st) == '*'&&(*(st+1)) == '/'){
if(((*st)=='*')&&((s.Top())=='*')&&((*(st+1))=='/')){
cout<<*st<<*(st+1)<<" 为分隔符左半边"<<endl;
s.pop();
s.pop();
cout<<"匹配"<<endl;}
else{
cout<<*st<<*(st+1)<<" 为分隔符右半边"<<endl;
cout<<"但 "<<(*st)<<*(st+1)<<"不匹配"<<endl;
cout<<"第"<<b<<"位"<<endl<<endl;
}
}
}
st++;
}
if(s.size == 0){
cout<<"====================================="<<endl;
cout<<"分隔符匹配正确！"<<endl;
cout<<"====================================="<<endl;}
else
{
cout<<"====================================="<<endl;
cout<<"分隔符不匹配，请检查输入字符！"<<endl;
cout<<"====================================="<<endl;
}
return 0;
}
自己编的，复杂版，可以检查{}（）【】/* */等符号的匹配
你看看有用不

㈦ 基本运算的栈的定义及基本运算

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除
【示例】元素是以a1，a2，…，an的顺序进栈，退栈的次序却是an，an-1，…，a1。 （1）InitStack（S）
构造一个空栈S。
（2）StackEmpty（S）
判栈空。若S为空栈，则返回TRUE，否则返回FALSE。
（3）StackFull（S）
判栈满。若S为满栈，则返回TRUE，否则返回FALSE。
注意：
该运算只适用于栈的顺序存储结构。
（4）Push（S，x）
进栈。若栈S不满，则将元素x插入S的栈顶。
（5）Pop（S）
退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。
（6）StackTop（S）
取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
顺序栈
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
1、顺序栈的类型定义
#defineStackSize100//假定预分配的栈空间最多为100个元素
typedefcharDataType;//假定栈元素的数据类型为字符
typedefstruct{
DataTypedata[StackSize];
inttop;
}SeqStack;
注意：
①顺序栈中元素用向量存放
②栈底位置是固定不变的，可设置在向量两端的任意一个端点
③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
2、顺序栈的基本操作
前提条件：
设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S->data[0]是栈底元素。
（1）进栈操作
进栈时，需要将S->top加1
注意：
①S->top==StackSize-1表示栈满
②上溢现象--当栈满时，再做进栈运算产生空间溢出的现象。
上溢是一种出错状态，应设法避免。
（2）退栈操作
退栈时，需将S->top减1
注意：
①S->toptop=-1;
}
（2）判栈空
intStackEmpty（SeqStack*S）
{
returnS->top==-1;
}
（3）判栈满
intStackFull（SeqStack*SS）
{
returnS->top==StackSize-1;
}
（4）进栈
voidPush（S，x）
{
if(StackFull(S))
Error(Stackoverflow);//上溢，退出运行
S->data[++S->top]=x;//栈顶指针加1后将x入栈
}
（5）退栈
DataTypePop（S）
{
if(StackEmpty(S))
Error(Stackunderflow);//下溢，退出运行
returnS->data[S->top--];//栈顶元素返回后将栈顶指针减1
}
（6）取栈顶元素
DataTypeStackTop（S）
{
if(StackEmpty(S))
Error(Stackisempty);
returnS->data[S->top];
}
4、两个栈共享同一存储空间
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为└m/2┘和┌m/2┐的向量空间比较，前者发生上溢的概率比后者要小得多。
链栈
栈的链式存储结构称为链栈。
1、链栈的类型定义
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
链栈的类型说明如下：
typedefstructstacknode{
DataTypedata
structstacknode*next
}StackNode;
typedefstruct{
StackNode*top;//栈顶指针
}LinkStack;
注意：
①LinkStack结构类型的定义是为了方便在函数体中修改top指针本身
②若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。
2、链栈的基本运算
（1）置栈空
VoidInitStack(LinkStack*S)
{
S->top=NULL;
}
（2）判栈空
intStackEmpty(LinkStack*S)
{
returnS->top==NULL;
}
（3）进栈
voidPush(LinkStack*S,DataTypex)
{//将元素x插入链栈头部
StackNode*p=(StackNode*)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;//将新结点*p插入链栈头部
S->top=p;
}
（4）退栈
DataTypePop(LinkStack*S)
{
DataTypex;
StackNode*p=S->top;//保存栈顶指针
if(StackEmpty(S))
Error(Stackunderflow.);//下溢
x=p->data;//保存栈顶结点数据
S->top=p->next;//将栈顶结点从链上摘下
free(p);
returnx;
}
（5）取栈顶元素
DataTypeStackTop(LinkStack*S)
{
if(StackEmpty(S))
Error(Stackisempty.)
returnS->top->data;
}
注意：
链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。

㈧ C语言关于栈操作

/*
这是关于栈的操作
那么应该定义一个栈类型
栈中包含两个元素
栈顶指针
栈底指针
以下是修改后的，供参考
*/
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
struct link
{
char name[40];
int age;
struct link * next;
};
typedef struct link Node;
typedef Node * List;
typedef struct Stack
{
List pTop;
List pBottom;
}STACK,* PSTACK;
void init(PSTACK pS)//初始化栈
{
pS->pTop = (Node *)malloc(sizeof(Node));
if (NULL == pS->pTop)
{
printf("动态内存分配失败!\n");
exit(-1);
}
else
{
pS->pBottom = pS->pTop ;
pS->pTop->next = NULL;
}
return;
}
/*入栈*/
void push(PSTACK pS,char * name,int age)
{
List p;
p=(Node*)malloc(sizeof(Node));/*申请新节点*/
if(p==NULL)
{
printf("error\n");
exit(1);
}
strcpy(p->name,name);/*将数据传入新节点*/
p->age=age;
p->next=pS->pTop;
pS->pTop=p;
return ;
}
//遍历栈，只是访问栈中元素的值，
//遍历完成后，栈中的元素个数是不会改变的
void traverse(PSTACK pS)
{
List p = pS->pTop;
while (p != pS->pBottom)
{
printf("%s%5d\n",p->name,p->age);
p = p->next ;
}
printf("\n");
return;
}
bool empty(PSTACK pS)
{
if (pS->pTop == pS->pBottom)
{
return true;
}
else
return false;
}
//出栈，将栈顶元素弹出，
//弹出后，栈中元素个数减少
//注意与 遍历栈 的区别
bool pop(PSTACK pS)
{
if (empty(pS))
{
return false;
}
else
{
List r = pS->pTop;
char * name = r->name;
printf("本次出栈元素的\nname=%s",name);
int age = r->age;
printf("\nage=%d",age);
pS->pTop = r->next;
free(r);
r = NULL;
return true;
}
}
void main()
{
STACK s;
printf("栈初始化操作\n");
init(&s);
printf("开始压栈操作\n");
int len;
printf("请输入需要压入栈中的元素的个数：");
scanf("%d",&len);
int i;
for (i=0; i<len; ++i)
{
printf("第%d个\n",(i+1));
printf("name:\t");
char name[40];
scanf("%s",name);
printf("age:\t");
int age;
scanf("%d",&age);
push(&s,name,age);
}
printf("遍历栈......\n");
traverse(&s);
printf("弹出栈顶元素\n");
pop(&s);
printf("\n弹出后重新遍历栈\n");
traverse(&s);

}
/*
----
栈初始化操作
开始压栈操作
请输入需要压入栈中的元素的个数：3
第1个
name: 许褚
age: 55
第2个
name: 徐晃
age: 66
第3个
name: 张辽
age: 22
遍历栈......
张辽 22
徐晃 66
许褚 55
弹出栈顶元素
本次出栈元素的
name=张辽
age=22
弹出后重新遍历栈
徐晃 66
许褚 55
-----
*/

㈨ c语言中，栈是具体应用方法和步骤

栈简单的讲就是一片存储区域（存储区的首地址即为栈顶）
你可以向栈中存入数据取出数据删除数据
/* Note:Your choice is C IDE */
#include "stdio.h"
#define m 100
struct Mystack/*定义栈结构*/
{
char element[m];
int top;/*栈顶*/
};
void push(struct Mystack *s,char x) /*将x的值压入栈顶*/
{
/* s->element[s->top]=x;
s->top++;*/
s->element[s->top]=x;
s->top++;
}
void pop(struct Mystack *s)
/*将栈顶元素删除*/
{
s->top--;
}
int IsEmpty(struct Mystack *s)
/*判断栈是否为空*/
{
if(s->top==0)
return 1;
else
return 0;
}
void Clearstack(struct Mystack *s)
/*清空栈元素*/
{
s->top=0;
}
void Displaystack(struct Mystack *s)
/*输出栈元素*/
{
int i;
for(i=0;i<s->top;i++)
printf("%c",s->element[i]);
}

main()
{
struct Mystack st;
int i;
char ch;
for(i=0;i<100;i++)
st.element[i]='\0';
st.top=0;
printf("please write a string:\n");
ch=getchar();
while(ch!='\n')
{
switch(ch)
{
case '#':
if(!IsEmpty(&st))
pop(&st);
break;
case '@':
if(!IsEmpty(&st))
Clearstack(&st);
break;
default:
push(&st,ch);
}
ch=getchar();
}
printf("the string is :\n");
Displaystack(&st);
}

㈩ 8086堆栈中数据的操作方式是什么

先进后出是正解！这是堆栈段的特点，与堆栈段不同的是指令序列缓冲器——先进先出。

PUSH指令：将一个字压入堆栈同时SP-2；
POP指令：一个字出栈，同时SP+2；

所以在写汇编时，若要用到堆栈，务必注意进栈和出栈的顺序：

例如写现场保护：

PUSH AX
PUSH DX

....

恢复现场的时候一定要先POP DX，再POP AX……简单地说就是上下对称。