A. 數據結構中什麼叫做順序棧
順序棧
棧的順序存儲結構簡稱為順序棧,它是運算受限的順序表。
1、
順序棧的類型定義
#define
StackSize
100
//假定預分配的棧空間最多為100個元素
typedef
char
DataType;//假定棧元素的數據類型為字元
typedef
struct{
DataType
data[StackSize];
int
top;
}SeqStack;
注意：
①順序棧中元素用向量存放
②棧底位置是固定不變的，可設置在向量兩端的任意一個端點
③棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針）來指示當前棧頂位置
2、
順序棧的基本操作
前提條件：
設S是SeqStack類型的指針變數。若棧底位置在向量的低端，即S-＞data[0]是棧底元素。
（1）
進棧操作
進棧時，需要將S-＞top加1
注意：
①S-＞top==StackSize-1表示棧滿
②"
上溢
"現象--當棧滿時，再做進棧運算產生空間溢出的現象。
上溢是一種出錯狀態，應設法避免。
（2）
退棧操作
退棧時，需將S-＞top減1
注意：
①S-＞top<0表示空棧
②"
下溢
"現象——當棧空時，做退棧運算產生的溢出現象。
下溢是正常現象，常用作程序控制轉移的條件。
順序棧在進棧和退棧操作時的具體變化情況【參見動畫演示】
3、順序棧的基本運算
（1）
置棧空
void
InitStack（SeqStack
*S）
{//將順序棧置空
S->top=-1;
}
（2）
判棧空
int
StackEmpty（SeqStack
*S）
{
return
S->top==-1;
}
（3）
判棧滿
int
StackFull（SeqStack
*SS）
{
return
S->top==StackSize-1;
}
（4）
進棧
void
Push（S，x）
{
if
(StackFull(S))
Error("Stack
overflow");
//上溢，退出運行
S->data[++S->top]=x;//棧頂指針加1後將x入棧
}
（5）
退棧
DataType
Pop（S）
{
if(StackEmpty(S))
Error("Stack
underflow");
//下溢，退出運行
return
S->data[S->top--];//棧頂元素返回後將棧頂指針減1
}
（6）
取棧頂元素
DataType
StackTop（S）
{
if(StackEmpty(S))
Error("Stack
is
empty");
return
S->data[S->top];
}
4、兩個棧共享同一存儲空間
當程序中同時使用兩個棧時，可以將兩個棧的棧底設在向量空間的兩端，讓兩個棧各自向中間延伸。當一個棧里的元素較多，超過向量空間的一半時，只要另一個棧的元素不多，那麼前者就可以佔用後者的部分存儲空間。
只有當整個向量空間被兩個棧占滿（即兩個棧頂相遇）時，才會發生上溢。因此，兩個棧共享一個長度為m的向量空間和兩個棧分別佔用兩個長度為 └ m/2┘和┌m/2┐的向量空間比較，前者發生上溢的概率比後者要小得多。
B. 兩棧共享空間
1.如果有兩個相同類型的棧，我們為它們各自開辟了數組空間，極有可能 一個棧已經滿了，再進棧就溢出了，而另一個棧還有很多存儲空間空間 。
2.所以我們可以使用 一個數組來存儲兩個棧 。
3.具體做法如下：數組有兩個端點，兩個棧有兩個棧底，讓 一個棧的棧底為數組的始端，即下標為0處 ， 另一個棧為數組的末端，即下標為數組長度n-1處
這樣，兩個棧如果增加元素，就是 兩端點向中間延伸
與上一遍順序棧的程序不同的是，此處採用下標記錄棧頂位置，而非指針，且並沒有指向棧頂的下一個存儲空間
如下圖所示：
測試：
C. 兩棧共享一個存儲空間,判定棧滿的條件是什麼
應該是top[1]=top[2] 吧，因為兩個棧頂都對到一起了才能說明棧的存儲已達到極限了，我是這么理解的。
D. 若棧採用順序存儲方式存儲,現兩棧共享空間
暈.這么簡單的問題也拿出來問
1 2 3 .m
| |
那麼當他們滿的時候,兩個指針相鄰
那就是
top[1]+1=top[2]
top[1]在top[2]左邊相鄰了
E. 請問「多個棧共存時,最好用鏈式存儲空間作為存儲結構」，這是為什麼啊
如果只有兩個棧，則可以將一個放在數組的低空間，一個放在高空間，兩者從兩頭向中間擴展，這樣沒有空間浪費
如果多於兩個棧時，還是採用順序存儲，則一個滿了另外棧空間雖然有空，但是必須要移動棧中元素才能使用別的浪費的空間，這樣演算法的效率就不高了，此時不如直接採用鏈接存儲好了
F. 設有兩個堆棧S1，S2都採用順序棧方式，並且共享一個存儲區，採用棧頂相向、迎面增長的存貯方式，
1
s1空：S1的棧頂等於棧底
s2空：s2的棧頂等於棧底
2
s1滿：S1的棧頂等於S2的棧頂
s2滿：S2的棧頂等於S1的棧頂
#include
#define
TYPE_S1
1
#define
TYPE_S2
-1
#define
STACK_SIZE
20
void
StackPush(int
**stackTop,
int
elmnt,
int
type)
{
**stackTop
=
elmnt;
*stackTop
+=
type;
}
void
main()
{
int
stack[STACK_SIZE]
=
{0};
int
*S1Top
=
&stack[0],
*S2Top
=
&stack[STACK_SIZE
-
1];
int
i,
input
=0;
for
(i
=
0;
i
<
20;
i++)
{
printf("請輸入一個整數：");
scanf("%d",
&input);
if(input
%
2
==0)
{
StackPush(&S1Top,
input,
TYPE_S1);
}
else
{
StackPush(&S2Top,
input,
TYPE_S2);
}
if(S1Top
==
S2Top)
{
printf("堆棧已滿\n");
break;
}
}
return;
}
G. 基本運算的棧的定義及基本運算
棧和隊列是兩種特殊的線性表，它們的邏輯結構和線性表相同，只是其運算規則較線性表有更多的限制，故又稱它們為運算受限的線性表。棧和隊列被廣泛應用於各種程序設計中。 棧（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運算。
H. 1，2，3，4依次進棧，出棧隨時，寫一演算法求出所有可能出棧序列
代碼如下：
#define N 4
int m=0,a=0,b=N;/*m表示種數，a表示棧中元素個數，b表示外面還有需要進棧的個數*/
main()
{
inS(a,b);/*首先入棧*/
printf("%d",m);
getch();
}
int inS(int a,int b)/*入棧*/
{
a++;b--;/*入棧棧中元素+1，棧外元素-1 */
if(b>0)/*若棧外有元素，可以入棧*/
inS(a,b);
if(a>0)/*若棧中有元素，可以出棧*/
outS(a,b);
}
int outS(int a,int b)/*出棧*/
{
a--;/*出棧棧中元素-1*/
if(a==0&&b==0)/*若棧中元素和棧外元素都為0個*/
{
m++;/*則此種情況的序列滿足條件，種數+1*/
return;
}
if(b>0)
inS(a,b);
if(a>0)
outS(a,b);
}
(8)三個棧共享一個順序存儲空間擴展閱讀
棧的相關知識點：
順序棧內容包含數據和棧頂指針(int)，因此採用結構體。
注意：
1、初始時，top指向-1；
2、入棧時，先判斷順序棧是否已滿（判斷條件：top=maxsize-1）;如果沒滿，則top++，並將元素值賦給s.top;
3、出棧時，先判斷順序棧是否已空（判斷條件：top=-1）;如果沒空，則先返回棧頂元素，再top- -。
共享棧
兩個順序棧共享一個一維數組空間，而棧底位置相對不變，兩個棧底分別設為一維數組的兩端。
note:
(1)棧空：top1==-1&&top2==maxsize;
(2)棧滿：top2-top1= 1(此時兩個棧頂指針相鄰)；
(3)入棧：S.data[++top1]=x或S.data[–top2]=x;
(4)出棧：x=S.data[top1–]或x=S.data[top2++];
(5)共享棧可以更好的利用存儲空間，整個存儲空間被占滿時發生上溢。
I. 兩個棧共享一段內存區域是什麼意思
當程序中同時使用兩個棧時，可以將兩個棧的棧底設在向量空間的兩端，讓兩個棧各自向中間延伸。如下圖所示：
當一個棧的元素較多，超過向量空間的一半時，只要另一個棧的元素不多，那麼前者就可以佔用後者的部分存儲空間。
只有當整個向量空間被兩個棧占滿（即兩個棧頂相遇）時，才會發生上溢，因此兩個棧共享一個長度為m的向量空間
J. 棧的共享存儲單元是什麼
有時，一個程序設計中，需要使用多個同一類型的棧，這時候，可能會產生一個棧空間過小，發生溢出，而另一個棧空間過大，造成大量存儲單元浪費的現象。為了充分利用各個棧的存儲空間，這時可以採用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實現存儲空間優勢互補。
1.雙棧為兩個棧共同開辟一個存儲空間，讓一個棧的棧底為該空間的始端，另一棧的棧底為該空間的末端，當元素進棧時，都從兩端向中間「增長」，這樣能夠使剩餘的空間為任意一個棧所使用，即當一個棧的深度不足整個空間的一半時，另一個棧的深度可超過其一半，從而提高了存儲空間的利用率。可以使用一個數組同時存兩個棧，讓一個棧的棧底為數組的始端，另一個棧的棧底為數組的末端，每個棧從各自的端點向中間延伸，雙棧示意如圖1所示。其中，MAXSTACKSIZE為整個數組空間的長度，棧1的底端固定在下標為0的一端，棧2的底端固定在下標為MAXSTACKSIZE－1的一端。top1和top2分別為棧1和棧2的棧頂指針，並約定棧頂指針指向當前元素，即棧1空的條件是top1＝－1，棧1滿的條件是top1＝＝top2－1，棧2空的條件是top2＝MAXSTACKSIZE，棧2滿的條件是top2＝＝top1＋1。
圖1兩相棧共享存儲單元示意