A. 棧的存儲結構
棧同順序表和鏈表一樣，棧也是用來存儲邏輯關系為 "一對一" 數據的線性存儲結構。
棧的具體實現
棧是一種 "特殊" 的線性存儲結構，因此棧的具體實現有以下兩種方式：
順序棧：採用順序存儲結構可以模擬棧存儲數據的特點，從而實現棧存儲結構；
鏈棧：採用鏈式存儲結構實現棧結構；
棧存儲結構與之前所學的線性存儲結構有所差異，這緣於棧對數據 "存" 和 "取" 的過程有特殊的要求：
棧只能從表的一端存取數據，另一端是封閉的；
在棧中，無論是存數據還是取數據，都必須遵循"先進後出"的原則，即最先進棧的元素最後出棧。
通常，棧的開口端被稱為棧頂；相應地，封口端被稱為棧底。因此，棧頂元素指的就是距離棧頂最近的元素。
B. 棧的鏈式存儲結構
int initstack(stack &s) 建堆棧
{
s.base=(char *)malloc(100*sizeof(char));
if(!s.base) exit(0);
s.top=s.base;
s.stacksize=100;
return 1;
}
int push(stack &s,char e)
{
if(s.top-s.base>=s.stacksize)
{
s.base=(char *)realloc(s.base,(s.stacksize+10)*sizeof(char));
if(!s.base) exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++=e;
}
int pop(stack &s,char &e)
{
if(s.top==s.base) exit(0);
e=*--s.top;
return 1;
}
參考下
C. 分別就棧的順序存儲結構和鏈式存儲結構實現棧的各種基本操作。
順序存儲結構
#include<iostream>
typedef char ElemType;
#define MaxSize 100
using namespace std;
typedef struct
{
ElemType data[MaxSize];
int top;
}sqStack;
void InitStack(sqStack *&s);//初始化棧
void ClearStack(sqStack *&s);//摧毀棧
int StackLength(sqStack *s);//返回棧的長度
bool StackEmpty(sqStack *s);//判斷棧是否為空
int Push(sqStack *&s,ElemType e);//進棧
int Pop(sqStack *&s,ElemType &e);//出棧
int GetTop(sqStack *s,ElemType &e);//取棧頂元素
void DispStack(sqStack *s);//顯示棧中元素值
int main()
{
return 0;
}
void InitStack(sqStack *&s)//初始化棧
{
s=new sqStack;
s->top=-1;
}
void ClearStack(sqStack *&s)//摧毀棧
{
delete s;
}
int StackLength(sqStack *s)//返回棧的長度
{
return (s->top+1);
}
bool StackEmpty(sqStack *s)//判斷棧是否為空
{
return (s->top==-1);
}
int Push(sqStack *&s,ElemType e)//進棧
{
if(s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
int Pop(sqStack *&s,ElemType &e)//出棧
{
if(s->top==-1)
return 0;
e=s->data[s->top];
s->top--;
return 1;
}
int GetTop(sqStack *s,ElemType &e)//取棧頂元素
{
if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}
void DispStack(sqStack *s)//顯示棧中元素值
{
for(int i=s->top;i>=0;i--)
cout<<s->data[i]<<" ";
cout<<endl;
}
鏈式存儲結構
typedef char ElemType;
typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;
void InitStack(LiStack *&s);//初始化棧
void ClearStack(LiStack *&s);//摧毀棧
int StackLength(LiStack *s);//返回棧的長度
bool StackEmpty(LiStack *s);//判斷棧是否為空
void Push(LiStack *&s,ElemType e);//進棧
int Pop(LiStack *&s,ElemType &e);//出棧
int GetTop(LiStack *s,ElemType &e);//取棧頂元素
void DispStack(LiStack *s);//顯示棧中元素值
int main()
{
return 0;
}
void InitStack(LiStack *&s)//初始化棧
{
s=new LiStack;
s->next=NULL;
}
void ClearStack(LiStack *&s)//摧毀棧
{
for(LiStack *p=s->next;p;p=p->next)
{
delete s;
s=p;
p=p->next;
}
delete s;
}
int StackLength(LiStack *s)//返回棧的長度
{
int i=0;
for(LiStack *p=s->next;p;p=p->next)
i++;
return i;
}
bool StackEmpty(LiStack *s)//判斷棧是否為空
{
return (s->next==NULL);
}
void Push(LiStack *&s,ElemType e)//進棧
{
LiStack *p=new LiStack;
p->data=e;
p->next=s->next;
s->next=p;
}
int Pop(LiStack *&s,ElemType &e)//出棧
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
delete p;
return 1;
}
int GetTop(LiStack *s,ElemType &e)//取棧頂元素
{
if(s->next==NULL)
return 0;
e=s->next->data;
return 1;
}
void DispStack(LiStack *s)//顯示棧中元素值
{
LiStack *p=s->next;
for(;p;p=p->next)
cout<<p->data<<" ";
cout<<endl;
}
D. 棧的基本操作
棧的基本操作如下：
（1）初始化一個棧：InitStack
（2）銷毀一個棧：DestroyStack
（3）清空一個棧：ClearStack
（4）判斷一個棧是否為空：StackIsEmpty
（5）返回棧中元素個數，即棧的長度：StackLength
（6）入棧，把一個元素加入到棧中：Push
（7）出棧，把棧頂元素給幹掉：Pop
（8）燃毀搭返回棧頂元素，但不出棧：GetTop
對於棧這一數據結構，皮拿我首先寫一下它的基本概念。
一.基本概念：
棧(stack)是僅限定在表尾進行插入和刪除操作的線性表。
棧就是一個線性表，只不過，棧的Insert 和 delete只能在表尾。
普通的線性表，在表中的任意位置都可以進行insert和delete操作。
LIFO: Last In First Out 後進先出，先進後出。
棧頂(Top): 進行插入和刪除操作的一端。
棧底(Bottom)
棧其實我們計算機科學中，更多的一種余陪思想，「先進後出的思想」。在很多演算法或應用中，需要用到「先進後出的思想」，我們可以考慮用棧來實現。
二.存儲結構：
順序結構： 用一組地址連續的空間來存儲數據元素。
鏈式結構：用地址不連續的空間來存儲數據元素，可能需要額外開辟一些空間，來存儲「數據元素之間的邏輯關系"。
E. 單共享棧
棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性數據結構。應用廣，作用大。
一、1、 棧的定義：限定僅在表尾進行插入或刪除操作的線性表，因此，對棧來說，表尾端有其特殊含義，表尾—棧頂(top) ，表頭—棧底(bottom) ，不含元素的空表稱空棧。
例4：計算機系2001年考研題（程序設計基礎）
設依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：
A）a，b，c，d B）c，d，a，b
C）b，c，d，a D）a，c，d，b
A、D可以（ B、C不行）。
答：
例5、習題集P22 3.4
status algo1(stack s)
{int i,n,a[255];
n=0;
While(!stackempty(s))
{n++;
pop (s,a[n]);}
For(i=1;i<=n;i++) push (s,a[i]);
}
5、補充公式：
若輸入的序列為1、2、3 ….n，則可能出現的輸出序列符合卡塔南數列：
驗證：
二、 棧的表示和實現：
順序存貯結構__順序棧；
鏈式存貯結構__鏈棧；
（一） 順序棧
利用一組地址連續的存貯單元依次自棧底到棧頂存放棧的數據元素.
棧底元素是最先進入的，實際上是線性表的第一個元素
數組（靜態數組）：空間固定
動態數組：動態申請空間（用指針表示）
表示容量；
表示數據元素個數；
// 順序棧的C表示
利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時附設指針top指示棧頂元素在順序棧中的位置；base表示棧底指針；
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{ SElemType *Base; // 棧底指針
SElemType *Top; // 棧頂指針
int StackSize;//當前已分配的存儲空間，以元素為 單位。
}SqStack
空棧
A
A進棧
top
base
top
base
s.top=0 或s.top=s.base 表示空棧；
s.base=NULL表示棧不存在；
當插入新的棧頂元素時，指針s.top++；
刪除棧頂元素時，指針s.top--；
當s.top-s.base>=stacksize時，棧滿，溢出
順序棧初始化
SqStack s;
s.Base = NULL;
s.Top = NULL;
s.StackSize = 0;
base
stacksize
top
&s
s.base = s.top =
( SElemType *)malloc( STACK_INIT_SIZE * sizeof( SElemType ));
順序棧的C圖示
base
top
空棧：
base = top;
A
base
top
*top = A;
top ++;
E
C
B
A
D
base
top
B
A
base
top
出棧：
if( top != base )
{
top --;
e = *top;
}
入棧：
if( 沒有空間 )
{
//realloc，調整top
}
順序棧基本演算法_InitStack
// 初始化順序棧, 構造一個空棧
Status InitStack( SqStack &S )
{
s.base = (SElemType *)malloc(
STACK_INIT_SIZE * sizeof( SElemType));
if( !s.base )
{
return OVERFLOW;
}
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
return OK;
}// InitStack
順序棧基本演算法：GetTop
// 用e返回棧S的棧頂元素，若棧空，函數返回ERROR
Status GetTop( SqStack S, SElemType &e)
{
if( s.top != s.base ) // 棧空嗎？
{
e = *( s.top – 1 );
return OK;
}
else
{
return ERROR;
}
}// GetTop
順序棧基本演算法：Push
//把元素e入棧
Status Push(SqStack &S, SElemType e )
{
// 若棧，追加存貯空間
if( s.top == s.base + s.stacksize )
{
p = (SElemType *)realloc( s.base,
(s.stacksize + STACKINCREMENT)*sizeof(SElemType));
if( !p )
{
return OVERFLOW;
}
s.base = p;
順序棧基本演算法：Push
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*s.top = e;
s.top++;
return OK;
}// Push
順序棧基本演算法：Pop
// 出棧
Status Pop( SqStack &S, SElemType &e )
{
if( s.top == s.base ) // 空嗎？
{
return ERROR;
}
s.top --;
e = *s.top;
return OK;
}// Pop
順序棧基本演算法：其他
// 取順序棧長度
int StackLength( SqStack S )
{
return s.top – s.base;
}// StackLength
#define StackLength( S ) ((S).top – (S).base)
// 順序棧空嗎？
Status StackEmpty( SqStack S )
{
return s.top == s.base ? TRUE:FALSE;
}
#define StackEmpty( S ) (((S).top == (S).base )?TRUE:FALSE)
順序棧基本演算法：ClearStack
// 清空棧
Status ClearStack( SqStack S )
{
if( s.base )
{
s.top = s.base;
}
return OK;
}// ClearStack
順序棧基本演算法：DestroyStack
// 銷毀棧
Status DestroyStack( SqStack &S )
{
if( s.base )
{
free( s.base );
s.stacksize = 0;
s.base = s.top = NULL;
}
}// DestroyStack
3.1.3 鏈棧
棧的鏈式存儲結構稱為鏈棧，它的運算是受限的單鏈表，插入和刪除操作僅限制在表頭位置上進行。由於只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結點。棧頂指針就是鏈表的頭指針。
鏈棧的類型說明如下：
棧的鏈接存儲結構
鏈棧的結點定義
typedef struct node
{ ElemType data;
struct node *next;
} LinkStack;
棧的鏈接表示 — 鏈式棧
鏈式棧無棧滿問題，空間可擴充
插入與刪除僅在棧頂處執行
鏈式棧的棧頂在鏈頭
適合於多棧操作
鏈棧的進棧演算法
LinkStack *PUSH (LinkStack *top, ElemType x)
{ LinkStack *p;
p＝malloc(sizeof(LinkStack));
p->data＝x; p->next＝top;top=p;
return top;
}
鏈棧的出棧演算法
linkstack *POP (linkstack *top, ElemType *datap)
{ linkstack *p;
if (top==NULL)
{printf(「under flow\n」); return NULL;}
else
{ *datap＝top->data;
p＝top;
top＝top->next;
free(p);
return top;
}
}
棧的共享存儲單元
有時，一個程序設計中，需要使用多個同一類型的棧,這時候，可能會產生一個棧空間過小，容量發生溢出，而另一個棧空間過大，造成大量存儲單元浪費的現象。 為了充分利用各個棧的存儲空間，這時可以採用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實現存儲空間優勢互補。
棧的應用---基本應用
void read_write()
{ stack S;
int n,x;
cout<<」Please input num int n」;
cin>>n; //輸入元素個數
init_stack(S); //初始化棧
for (i=1; i<=n; i++)
{ cin>>x; //讀入一個數
push_stack(S,x); //入棧
}
while (stack_empty(S)!=TRUE)
{stack_top(S,x); //取出棧頂元素
cout<<x; //輸出
pop_stack(S); //退棧
}
}
讀入一個有限大小的整數n，並讀入n個整數，然後按輸入次序的相反次序輸出各元素的值。
3.2 棧的應用舉例
一、 數制轉換
二、 括弧匹配的檢驗
三、 行編輯程序問題
四、 表達式求值
五、 迷宮求解
六、 實現遞歸
一、數制轉換
十進制N和其它進制數的轉換是計算機實現計算的基本問題,其解決方法很多,其中一個簡單演算法基於下列原理:
N=(n div d)*d+n mod d
( 其中:div為整除運算,mod為求余運算)
例如 (1348)10=(2504)8，
其運算過程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
0
計算順序
輸出順序
演算法分析：
由十進制轉換為其他進制的數的規則，可知，求得的余數的順序為由低位到高位，而輸出則是由高位到低位。
因此，這正好利用棧的特點，先將求得的余數依次入棧，輸出時，再將棧中的數據出棧。
void conversion () {
InitStack(S); // 構造空棧
scanf ("%d",&N); //輸入一個十進制數
while (N) {
Push(S, N % 8); // "余數"入棧
N = N/8; // 非零"商"繼續運算
}
while (!StackEmpty(S)) {
Pop(S,&e);
//和"求余"所得相逆的順序輸出八進制的各位數
printf ( "%d", e );
}
} // conversion
二、 括弧匹配的檢驗
假設在表達式中
(〔〕（））或〔（〔 〕〔 〕）〕
等為正確的格式，
（〔]（ ） 或（（）））或 〔（ 〕）均為不正確的格式。
則 檢驗括弧是否匹配的方法可用「期待的急迫程度」這個概念來描述。
演算法的設計思想：
讀入表達式
1）凡出現左括弧，則進棧；
2）凡出現右括弧，首先檢查棧是否空
若棧空，則表明該「右括弧」多餘，
否則和棧頂元素比較，
若相匹配，則「左括弧出棧」 ，
否則表明不匹配。
3）表達式檢驗結束時，
若棧空，則表明表達式中匹配正確，
否則表明「左括弧」有餘。
Status matching(char exp[ ] ) {
while (i<=Length(exp)) {
switch exp[i] {
case '(『 || '[' :{Push(S,exp[i]); i++; break;}
case ')' : {
if( ！StackEmpty(S)&& GetTop(S)= '(' ）
{Pop(S,e); i++;}
else return ERROR;
break; }
case 『]' : {
if( ！StackEmpty(S)&& GetTop(S)= 『[' ）
{Pop(S,e); i++;}
else return ERROR;
break; } }
if (StackEmpty(S)) return OK;
}
三、行編輯程序問題
「每接受一個字元即存入存儲器」 ?
並不恰當！
設立一個輸入緩沖區，用以接受用戶輸入的一行字元，然後逐行存入用戶數據區,並假設「#」為退格符，「@」為退行符。
在用戶輸入一行的過程中，允許用戶輸入出差錯，並在發現有誤時可以及時更正。
合理的作法是：
假設從終端接受了這樣兩行字元：
whli##ilr#e（s#*s)
outcha@putchar(*s=#++);
則實際有效的是下列兩行：
while (*s)
putchar(*s++);
可設這個輸入緩沖區為一個棧結構，每當從終端接受了一個字元之後先作如下判斷：
1、既不是退格也不是退行符，則將該字元壓入棧頂；
2、如果是一個退格符，則從棧頂刪去一個字元；
3、如果是一個退行符，則將字元棧清為空棧 。
while (ch != EOF && ch != '\n') {
switch (ch) {
case 『#』 : Pop(S, c); break;//棧非空，退棧
case '@': ClearStack(S); break;// 重置S為空棧
default : Push(S, ch); break; //未考慮棧滿
}
ch = getchar( ); // 從終端接收下一個字元
}
ClearStack(S); // 重置S為空棧
if (ch != EOF) ch = getchar( );
}
DestroyStack(S); }
Void LineEdit( ) {
InitStack(S);
ch=getchar();
while (ch != EOF) { //EOF為全文結束符
將從棧底到棧頂的字元傳送至調用過程的數據區；
補充習題：
1、設計一個演算法，用棧的基本運算，判定一個字元串是否為對稱字元串，若是，則返回1，否則返回0。（abccba)
四、表達式求值
1、算術表達式的組成：
將表達式視為由操作數、運算符、界限符（稱為單詞）組成。
操作數：常數、變數或符號常量。
算符：運算符、界限符
表達式求值是程序設計語言編譯的一個最基本的問題。它的實現是棧應用的又一典型例子。 僅以算術表達式為例
2、算術表達式的形式：
中綴(infix)表達式——表達式的運算符在操作數的中間。 <操作數> <操作符> <操作數>
例：A*B 例：5+9*7
後綴(postfix)算術表達式(逆波蘭式)——將運算符置兩個操作數後面的算術表達式。 <操作數> <操作數> <操作符>
例：AB* 例：5 9 7*+
前綴(prefix)表達式(波蘭式)又稱波蘭式，與後綴表達式相反。把運算符放在兩個運算數的前面， <操作符> <操作數> <操作數>
例：*AB 例：+5*9 7
3、介紹中綴算術表達式的求值
例如：3*（7 – 2 ）
（1）算術四則運算的規則：
a. 從左算到右
b. 先乘除，後加減
c. 先括弧內，後括弧外
由此，此表達式的計算順序為：
3*（7 – 2 ）= 3 * 5 = 15
（2）根據上述三條運算規則，在運算的每一步中，對任意相繼出現的算符1和2 ，都要比較優先權關系。
一般任意兩個相繼出現的兩個算符p1和p2之間的優先關系至多有下面三種之一：
p1<p2 p2的優先權高於p1
p1=p2 二者優先權相等
p1>p2 p2的優先權低於p1
算符優先法所依據的算符間的優先關系
見教材P53表3.1
θ1<θ2，表明不能進行θ1 的運算，θ2 入棧，讀 下一字元。
θ1>θ2，表明可以進行θ1 的運算，θ1退棧，運算，運算結果入棧。
θ1=θ2，脫括弧，讀下一字元或表達式結束。
（3）演算法思想：
設定兩棧：操作符棧 OPTR ，操作數棧 OPND
棧初始化：設操作數棧 OPND 為空；操作符棧 OPTR 的棧底元素為表達式起始符 『#』；
依次讀入字元：是操作數則入OPND棧，是操作符則要判斷：
if 操作符 < 棧頂元素，則退棧、計算，結果壓入OPND棧；
操作符 = 棧頂元素且不為『#』，脫括弧（彈出左括弧）；
操作符 > 棧頂元素，壓入OPTR棧。
掃描基本符號
是否操作數？
Y
棧頂運算符低
於當前運算符？
操作數
入棧
N
Y
N
運算符
入棧
取出S棧頂運算符和
O棧頂的兩個操作數
運算，結果入棧O
定義運算符棧S
和操作數棧O
棧S為空？
Y
結束
Y
一般作為相同運算符，先出現的比後出現的優先順序高；
先出現的運算符優先順序低於「(」，高於「)」；
後出現的運算符優先順序高於「(」，低於「)」；優先權相等的僅有「(」和「)」、「#」。
#：作為表達式結束符，通常在表達式之前加一「#」使之成對，當出現「#」=「#」時，表明表達式求值結束，「#」的優先順序最低。
OPTR
OPND
INPUT
OPERATE
3*(7-2)#
Push(opnd,』3』)
#
*(7-2)#
3
#
Push(optr,』*』)
#,*
3
(7-2)#
Push(optr,』(』)
#,*,(
3
7-2)#
Push(opnd,』7』)
#,*,(
3,7
-2)#
Push(optr,』-』)
#,*,(,－
3,7
2)#
Push(opnd,』2』)
#,*,(,－
3,7,2
)#
Operate(7-2)
#,*,(
3,5
)#
Pop(optr)
#,*
3,5
#
Operate(3*5)
#
15
#
GetTop(opnd)
例：3*（7-2）
Status EvaluateExpression( OperandType &result) {
InitStack(OPND); InitStack(OPTR);
Push(OPTR ,』#』);c=getchar();
while((c!=『#』)&&(GetTop(OPTR)!=『#』))
{ if (!In(c,OP) { Push(OPND,c); c=getchar();}
else switch(compare(c,GetTop(OPTR)))
{case 『>』 : Push(OPTR , c); c=getchar();break;
case 『=』: Pop(OPTR);c=getchar();break;
case 『<』 : temat=Pop(OPTR); b=Pop();a=Pop();
result= Operate(a,temat,b);Push(OPND,result);
c=getchar();break;
} //switch }//while
result=GetTop(OPND);}//EvaluateExpression
此函數在哪裡？
4、計算後綴表達式
（1）為什麼要把中綴表示法變為後綴表示法？
計算機計算表達式是機械執行，只能從左至右掃描。計算中綴表達式比較困難。
後綴表達式的求值過程是自左至右運算符出現的次序和真正的計算次序是完全一樣的。
順序掃描表達式的每一項，根據它的類型做如下相應操作：
若該項是操作數，則將其壓棧；
若該項是操作符<op>，則連續從棧中退出兩個操作數Y和X，形成運算指令X<op>Y，並將計算結果重新壓棧。
當表達式的所有項都掃描並處理完後，棧頂存放的就是最後的計
算結果。
人們仍然使用中綴表達式 ，而讓機器把它們轉換成後綴表達式。
（2）後綴表達式求值實例：
A=B*C + D*(E-F)
ABC*DEF-*+=
ABC*—做 B*C=T1
AT1DEF- –—做E-F=T2
AT1DT2*—做D*T2=T3
AT1T3+—做T1+T3=T4
AT4=—做A=T4
後綴表達式「32422*+13*-^*5-」，棧中狀態變化情況：
typedef char elemtype ;
double calcul_exp(char *A) /*本函數返回由後綴表達式A表示的表達式運算結果*/
{ Seq_Starck s ;
ch=*A++ ; Init_SeqStack(s) ;
while ( ch != 』#』 )
{ if (ch!=運算符) Push_SeqStack (s , ch) ;
else { Pop_SeqStack (s , &a) ;
Pop_SeqStack (s , &b) ; /*取出兩個運算量*/
switch (ch).
{ case ch= =』+』： c=b+a ; break ;
case ch= =』-』： c=b-a ; break ;
case ch= =』*』： c=b*a ; break ;
case ch= =』/ 』： c=b/a ; break ;
case ch= =』%』： c=b%a ; break ; }
Push_SeqStack (s, c) ; }
ch=*A++ ;
}
Pop _SeqStack ( s , result ) ;
return result ;
}
（3）中綴表達式變後綴表達式
表達式中操作數次序不變,，運算符次序發生變化,運算符放在操作數的後面。同時去掉了圓括弧 。
例：3+（7*8-9）
運算符的優先數表
5
4
3
2
1
0
優先數
^
*，/
＋，－
＝
）
（
操作
存儲結構
W（I）存放表達式的第I個字元。
利用一個棧S（）。P為棧指針。
演算法設計
Step1：輸入是變數則輸出它；
Step2：是左括弧「（」，無條件地壓入堆棧；
Step3：輸入運算符優先數是2，3，4，5時，如果棧空，則進棧。如果棧不空，則將它與棧頂元進行比較。倘若優先數大於頂元，則進棧；小於頂元，則頂元退棧並輸出之。然後再繼續比較，直到大於頂元或棧空時它進棧；
Step4：若是右括弧「）」，同時棧頂元又為左括弧「（」，則退棧，並抹去「）」。否則按Step3處理；
Step5：輸入完而棧非空，則將棧內內容逐一退棧，並輸出之。
模擬演算法執行過程
A=B*C+D*(E-F)
ABC*DEF-*+=
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
棧s （）:
top=0
A
變數,輸出
輸出:
說明:
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
棧s （）:
A
算符,棧空,入棧
=
輸出:
說明:
top=0
top=0
top=1
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
=
棧s （）:
top=1
A
變數,輸出
輸出:
說明:
B
)
F
-
E
(
*
D
+
C
*
B
=
A
W（I）:
=
棧s （）:
AB
算符*,優先順序等於4,大於棧頂元素=優先順序,入棧
輸出:
說明:
*
top=1
top=1
top=2
)
F
-
F. 棧的鏈式存儲結構是什麼
若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。人們將用鏈式存儲結構表示的棧稱作「鏈棧」。鏈棧通常用一個無頭結點的單鏈表表示。由於棧的插入、刪除操作只能在一端進行，而對於單鏈表來說，在首端插入、刪除結點要比在尾端進行相對容易一些，所以將單鏈表的首端作為棧的頂端，即將單鏈表的頭指針作為棧頂指針。鏈棧如圖1所示。
圖1鏈棧的存儲示意
G. 棧的順序存儲是什麼
由於棧是運算受限的線性表，因此線性表的存儲結構對棧也適用，而線性表有順序存儲和鏈式存儲兩種，所以棧也有順序存儲和鏈式存儲兩種。
1.棧的順序存儲棧的順序存儲是利用一組地址連續的存儲單元依次存放從棧底到棧頂的數據元素，並附設指針top指示棧頂。
2.棧的順序存儲類型定義1）用內存動態分配方式定義棧的順序存儲（1）棧的順序存儲表示。
順序棧本質上是順序表的簡化，由於棧底位置是固定不變的，所以可以將棧底位置設置在存儲空間的基地址上，棧頂位置是隨著進棧和退棧操作而變化的，故用top來指示當前棧頂元素的下一個位置，通常稱top為棧頂指針。
H. 棧的鏈式存儲
#include<stdio.h>
#include<stdlib.h>
凱扒蠢#define elemtype int
#define MAXSIZE 100
typedef struct stack{
elemtype elem;
struct stack *next;
}STACK;
//鏈盯陪式存儲的棧結構，及其相應演算法
void InitStack(STACK *top)
{//初始化空棧
top->next=NULL;
}
void DestroyStack(STACK *top)
{//銷毀棧，將棧所佔內存空間釋放
STACK *p;
p=top->next;
while(p!=NULL){
top->next=p->next;
free(p);
p=top->next;
}
}
int EmptyStack(STACK *top)
{//判斷是否棧空，為空則返回1，否則返回0
if(top->next==NULL){
return 1;
}
else{
return 0;
}
}
int push(STACK *top, elemtype x)
{//元素x進棧操作，成功返回1，否則返回0
STACK *p;
p=(STACK *)malloc(sizeof(STACK));
p->elem=x;
p->next=top->next;
top->next=p;
return 1;
}
elemtype pop(STACK *top)
{//出棧操作，返回出棧元素
if(EmptyStack(top)){
printf("棧為空");
return 0;
}
else{
elemtype x;
STACK *p;
p=top->next;
此彎x=p->elem;
top->next=p->next;
free(p);
p=top->next;
return x;
}
}
void Print(STACK *top)
{//依次輸出棧頂到棧底的所有元素
STACK *h;
h=top->next;
while(h!=NULL){
printf("%4d",h->elem);
h=h->next;
}
}
int main(void)
{
STACK *top=NULL;
top=(STACK *)malloc(sizeof(STACK));
InitStack(top);
push(top,1);
push(top,2);
push(top,4);
Print(top);
push(top,5);
Print(top);
pop(top);
Print(top);
DestroyStack(top);
}
I. 鏈棧如何構造，鏈棧新結點如何進棧
鏈式棧就是用鏈式存儲結構表示一個棧，也就是指針域。
根據棧的性質，知道棧是先進後出，所以只需要設置一個棧頂指針，還是說點C++吧
先構造一個結構模板
template<class
ElemType>
typedef
struct
Node
//建立
{
ElemType
data;//數據成員，用於存儲
struct
Node*next;//指針成員，用於連接邏輯結構
}LNode;
1.構造一個空棧，只需要：
LNode*head;//定義棧頂指針
head=(LNode*)malloc(sizeof(LNode));//分配空間
head->next=NULL;//下一個為空
2.新節點：比如新節點數據位1
入棧操作：
LNode*p;
p->data=1;
p->next=head;
head=p;
總之有點類似C語言里的鏈表
還有什麼不清楚的可以追問
希望對你有所幫助！！！
J. 簡述棧和隊列的順序存儲結構和鏈式存儲結構的優缺點
順序棧--入棧操作受數組上界的約束有可能發生棧上溢，且需要地址連續的存儲單元。
鏈棧--無須地址連續，便於多個棧共享存儲單元，且不存在棧滿上溢情況。
順序隊列--需地址連續且有假上溢現象（需改為循環隊列才可解決假上溢）
鏈式隊列--特別適合於數據元素變動比較大的情況，且不存在隊列滿而產生的溢出問題。