用棧記錄回滾步驟

㈠ 什麼是棧回溯

一、棧回溯的概念：
棧回溯就是回溯法，是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。

二、演算法框架：
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……簡單地說就是上下對稱。