㈠ 數據結構，定義了一個共享棧，劃線部分s.top［1］是什麼意思啊是數組嗎上面定義了top［0］
這里說的共享棧的意思是： 有一段內存(elemtp stack[xxxx])， 這段內存的起始地址分別當作兩個棧， 但是這兩個棧增長的方向相反，地址小的那一端向地址大的方向增長， 地址大的那一個棧向地址小的方向增長。 int top[2] 定義了這兩個棧的棧頂(stack 這個數組的兩端 index)， s.top[0] , s.top[1]分別表示兩個棧頂
㈡ 數據結構中共享棧判斷棧滿的條件一個是top1=top2，還有一種是top2-top1=1，哪位大俠
共享棧，當top2-top1=1時已經滿了。因為top指向的是棧元素，同一元素不能同屬兩個棧。
㈢ 單共享棧
棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性數據結構。應用廣，作用大。
一、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
-
㈣ 數據結構中的兩棧共享空間有點不理解求解！
這個應該是以一個數組實現兩個棧的共享。
-----------------------------------------------
| | | | | | | | | | | 長度為10的數組
------------------------------------------------
top1(-1) top2(10)
如上圖，假設初始top1為-1，top2為11，棧1push了一個數字2，棧2push了一個數字3之後，數組變成如下形式，top1為0，top2為9：
-----------------------------------------------
| 2 | | | | | | | | | 3 |
-----------------------------------------------
top1(0) top2(9)
當整個數組存滿的時候top1+1=top2。比如棧1存了2、5、4、6、7，棧2存了3、9、4、8、1，此時top1=4，top2=5
----------------------------------------------------
| 2 | 5 | 4 | 6 | 7 | 1 | 8 | 4 | 9 | 3 |
----------------------------------------------------
top1(4) top2(5)
㈤ 數據結構共享棧 問題好像是入棧入不進去 求指導 多謝
希望如下對你有用：
/*棧的基本操作*/
# define stacksize 100 /*定義棧的最大存儲空間*/
# define LEN sizeof(struct stack)
static size=0;
struct stack {
int data;
int *top[stacksize];
};
struct stack *sqstack;
struct stack *s;
static e;
int push() /*將元素壓入棧*/
{
if (size<=stacksize)
* sqstack->top[size++]=e;
else
printf (" the stack is full:");
}
int pop(struct stack *sqstack,int location) /*元素出棧*/
{
e=*(sqstack->top[location]);
return (e);
}
main()
{ int n,i,t,x=0;
int element;
printf ( "\n create the stack first :");
scanf ("%d ",&n);
for (i=1;i<=n;i++)
{
scanf ("%d",&e);
push (e);
}
s=sqstack;
t=size;
printf ("\n after pushed , the sqstack is :");
while (t>=0)
{
*s->top[t]=*sqstack->top[t];
t--;
}
t=size;
while (t!=0)
{
t--;
e=pop(s,t);
printf (" %d->",e);
}
printf ("\n which element you want to pop :");
scanf ("%d",&element);
while (size!=0)
{
e=pop(sqstack,size--);
if (element==e)
{
printf ("\n %d is poped",element);
x=1;
}
}
if(x==0)
printf ("\n %d is not found in the sqstack.\n",element);
}