概念描述
棧是限定僅在表位進(jìn)行插入或刪除操作的線性表。棧的表尾稱(chēng)為棧頂，表頭稱(chēng)為棧底。不含元素的棧稱(chēng)為空棧。
左圖為棧的示意圖，右圖為用鐵路調(diào)度表示棧。
如下是入棧至棧滿再進(jìn)行出棧的過(guò)程示意圖。值得注意的是，棧滿后，top指針指向的不是頂端元素，而是頂端的下一個(gè)位置。
基本操作
構(gòu)造一個(gè)空棧S
在正式開(kāi)始前，照例需要定義一些如下的常量
#define STACK_INIT_SIZE 100//存儲(chǔ)空間初始分配量
#define STACKINCREMENT 10//存儲(chǔ)空間分配增量
#define TRUE 1
#define ERROR 0
#define OVERFLOW -2
typedef char SElemType;
tyoedef int Status;
typedef struct{
SElemType *base;//棧底指針.在棧構(gòu)造之前和銷(xiāo)毀之后,base的值為NULL
SElemType *top;//棧頂指針
int stacksize;//當(dāng)前已分配的存儲(chǔ)空間,初始值一般為STACK_INIT_SIZE,不夠時(shí)再以STACKINCREMENT為單位擴(kuò)大
}SqStack;在順序棧中，base指針始終指向棧底元素，棧不存在的條件為base=NULL。top指針初值指向棧底，棧空的條件為base==top。棧不空時(shí)，top指向(棧頂+1)。也就是說(shuō)，在正常情況下，S.top 是不指向任何元素的。(top-base)的值即為棧中元素的個(gè)數(shù)，也即棧的長(zhǎng)度。當(dāng)top-base==stacksize時(shí)，說(shuō)明棧滿。此時(shí)若想進(jìn)行入棧操作，需要擴(kuò)充分配存儲(chǔ)空間。
判空
Status StackEmpty(SqStack S)
{
if(!S.base) return TRUE;
else return FALSE;
}構(gòu)造一個(gè)空棧
Status InitStack(SqStack &S)
{
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}若棧不存在，分配空間時(shí)發(fā)生上溢出錯(cuò)誤而退出。
入棧
在入棧、出棧、取棧頂元素的函數(shù)中，不存在分配空間的問(wèn)題，是return ERROR而不是?exit(OVERFLOW)
Status Push(SqStack& S, SEIemType e)//入棧
{
if (S.top - S.base >= S.stacksize) return ERROR;
*S.top = e;//注意S.top是指針型變量
S.top++;//先賦值,再加一
return OK;
}
出棧
Status (SqStack &S)
{
if(S.top==S.base) return ERROR;
S.top--;
e=*(S.top);
return OK；
}值得注意的是，出棧后，元素e并未從棧中刪除。改變的只是top指針的位置。雖然e還在棧中，但棧長(zhǎng)已經(jīng)改變，e的原位置此后可以被其它值覆蓋。
取棧頂元素
取棧頂元素就是“top指針位置不變”版的“出棧”。博主初學(xué)時(shí)沒(méi)意識(shí)到這一點(diǎn)，以為出棧就是刪除元素，所以構(gòu)造了一個(gè)很復(fù)雜的取棧頂元素函數(shù)。為避免誤導(dǎo)，就不放在這里了。
Status(SqStack S,SElemType)
{
if(S.top==S.base) return ERROR;
e=*(S.top-1);//top指針位置不變
return OK;
}輸出棧中所有元素
和取棧頂元素同理，在不移動(dòng)指針位置的情況下輸出元素。若采用for循環(huán)，需要先求棧長(zhǎng)。一般使用while循環(huán)。
Status PrintStack(SqStack S)
{
int i=0;
SElemType *s;
s=S.base;//注意！順序棧從底部開(kāi)始向上存儲(chǔ)，順序輸出是從S.base開(kāi)始
//并且，如果想做逆序輸出，while循環(huán)條件應(yīng)為s!=S.base-1
while(s!=S.top)
{
printf("%c\n",*s);
s++;
i++;
}
printf("已輸出棧中%d個(gè)元素",i);
return OK；
}Status PrintStack(SqStack S)
{
int a=S.top-S.base;
if(S.base==S.top) return ERROR;
int i;
for(i=1;i<=a;i++)
printf("%c\n",*(S.top-a));
printf("已輸出棧中%d個(gè)元素",a);
return OK;
}括號(hào)匹配
題干描述
由鍵盤(pán)輸入一系列左括號(hào)和右括號(hào)，判斷這些括號(hào)是否成功配對(duì)。一旦發(fā)現(xiàn)不配對(duì)的括號(hào)，立刻退出程序并說(shuō)明原因。如：( { [ ] [ ] } )是匹配成功，而((]是由于括號(hào)不匹配而失敗，{ ( [ ] )是因?yàn)樽罄ㄌ?hào)多余而失敗，( { } ) ]是因?yàn)橛依ㄌ?hào)多余而失敗。
題目分析
代碼(含分析)
Status March_Brackets(SqStack& S)
{
char ch;//輸入一連串字符(括號(hào)),以回車(chē)結(jié)束.起初,括號(hào)都存儲(chǔ)在ch中,棧S為空棧.
SElemType* s;
s = S.top-1;//s指向棧頂元素
printf("請(qǐng)輸入字符:\n");
ch = getchar();//輸入括號(hào),進(jìn)入循環(huán)
while (ch != '\n')//循環(huán)接收括號(hào)字符以回車(chē)為結(jié)束符,每輸入一個(gè)括號(hào),就進(jìn)行一次判斷。
{
if (ch =='(' || ch == '[' || ch == '{') //如果ch是左括號(hào),入棧.棧中存放左括號(hào),有匹配的右括號(hào)就出棧.若全部匹配成功,?？铡? Push(S, ch); //入棧
if (ch == ')')//輸入字符為右括號(hào)
{
if ((Pop(S, *s) == 0)) { printf("右括號(hào)多余,不匹配\n"); return ERROR; }
/*在Pop函數(shù)中, 若返回值為0, 說(shuō)明是空棧.這有兩種情況:1,還未輸入左括號(hào),第一個(gè)輸入的就是右括號(hào);
2,之前輸入的左、右括號(hào)都已成功匹配,左括號(hào)已全部出棧*/
else if (*s != '(') { printf("右括號(hào)與左括號(hào)不匹配\n"); return ERROR; }
/*最后輸入的左括號(hào)不是小括號(hào),與輸入的右小括號(hào)不匹配*/
}
else if (ch == ']')
{
if ((Pop(S, *s) == 0)) { printf("右括號(hào)多余,不匹配\n"); return ERROR; }
else if (*s != '[') { printf("右括號(hào)與左括號(hào)不匹配\n"); return ERROR; }
}
else if (ch == '}')
{
if ((Pop(S, *s) == 0)) { printf("右括號(hào)多余,不匹配\n"); return ERROR; }
else if (*s != '{') { printf("右括號(hào)與左括號(hào)不匹配\n"); return ERROR; }
}
ch = getchar();
}//循環(huán)結(jié)束,說(shuō)明輸入的右括號(hào)都有預(yù)支品牌的左括號(hào).但這不意味著匹配成功?。∵€有左括號(hào)多余的可能。
if (S.top != S.base)//棧不空,說(shuō)明有左括號(hào)未出棧,未匹配
{
printf("左括號(hào)多余,不匹配\n");
return ERROR;
}
else//?？?說(shuō)明左括號(hào)已全部出棧,匹配成功
{
printf("匹配完整,成功退出\n");
return OK;
}
} 上機(jī)實(shí)現(xiàn)
完整代碼
經(jīng)高手指點(diǎn)：由于getchar的一些特性，建議只執(zhí)行一次括號(hào)判斷函數(shù)。不要在主函數(shù)中反復(fù)執(zhí)行它。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-732587.html
#include <stdio.h>
#include <stdlib.h>
typedef char SElemType;
typedef int Status;
constexpr auto ERROR = 0;
constexpr auto OK = 1;
constexpr auto OVERFLOW = -2;
constexpr auto STACK_MAX_SIZE = 100;
typedef struct {
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
Status InitStack(SqStack& S)//建立空順序棧
{
S.stacksize = STACK_MAX_SIZE;
S.base = (SElemType*)malloc(STACK_MAX_SIZE * sizeof(SElemType));
if (!S.base) exit(OVERFLOW);
S.top = S.base;
return OK;
}
Status Push(SqStack& S, SElemType e)//入棧
{
if (S.top - S.base >= S.stacksize) exit(OVERFLOW);
*S.top = e;//注意S.top是指針型變量
S.top++;//先賦值,再加一
return OK;
}
Status Pop(SqStack& S, SElemType& e)//出棧
{
if (S.base == S.top) return ERROR;
S.top--;//注意S.top是指針型變量
e = *S.top;//先減一,再賦值
return OK;
}
Status GetTop(SqStack S, SElemType &e)//獲取棧頂元素
{
if (S.top == S.base) return ERROR;
e = *(S.top - 1);//top指針位置不變
return OK;
}
Status PrintStack(SqStack S)//輸出棧所有元素
{
if (S.top == S.base) return ERROR;
int i = 0;
SElemType* s;
s = S.base;
while (s != S.top)
{
printf("%c\n", *s);
i++;
s++;
}
printf("已輸出棧中%d個(gè)元素", i);
return OK;
}
Status March_Brackets(SqStack& S)
{
char ch;//輸入一連串字符(括號(hào)),以回車(chē)結(jié)束.起初,括號(hào)都存儲(chǔ)在ch中,棧S為空棧.
SElemType* s;
s = S.top-1;//s指向棧頂元素
printf("請(qǐng)輸入字符:\n");
ch = getchar();//輸入括號(hào),進(jìn)入循環(huán)
while (ch != '\n')//循環(huán)接收括號(hào)字符以回車(chē)為結(jié)束符,每輸入一個(gè)括號(hào),就進(jìn)行一次判斷。
{
if (ch =='(' || ch == '[' || ch == '{') //如果ch是左括號(hào),入棧.棧中存放左括號(hào),有匹配的右括號(hào)就出棧.若全部匹配成功,?？?。
Push(S, ch); //入棧
if (ch == ')')//輸入字符為右括號(hào)
{
if ((Pop(S, *s) == 0)) { printf("右括號(hào)多余,不匹配\n"); return ERROR; }
/*在Pop函數(shù)中, 若返回值為0, 說(shuō)明是空棧.這有兩種情況:1,還未輸入左括號(hào),第一個(gè)輸入的就是右括號(hào);
2,之前輸入的左、右括號(hào)都已成功匹配,左括號(hào)已全部出棧*/
else if (*s != '(') { printf("右括號(hào)與左括號(hào)不匹配\n"); return ERROR; }
/*最后輸入的左括號(hào)不是小括號(hào),與輸入的右小括號(hào)不匹配*/
}
else if (ch == ']')
{
if ((Pop(S, *s) == 0)) { printf("右括號(hào)多余,不匹配\n"); return ERROR; }
else if (*s != '[') { printf("右括號(hào)與左括號(hào)不匹配\n"); return ERROR; }
}
else if (ch == '}')
{
if ((Pop(S, *s) == 0)) { printf("右括號(hào)多余,不匹配\n"); return ERROR; }
else if (*s != '{') { printf("右括號(hào)與左括號(hào)不匹配\n"); return ERROR; }
}
ch = getchar();
}//循環(huán)結(jié)束,說(shuō)明輸入的右括號(hào)都有預(yù)支品牌的左括號(hào).但這不意味著匹配成功！！還有左括號(hào)多余的可能。
if (S.top != S.base)//棧不空,說(shuō)明有左括號(hào)未出棧,未匹配
{
printf("左括號(hào)多余,不匹配\n");
return ERROR;
}
else//?？?說(shuō)明左括號(hào)已全部出棧,匹配成功
{
printf("匹配完整,成功退出\n");
return OK;
}
}
int main(void)
{
SqStack S; int i;
char e; char f; char k;
InitStack(S);
printf("請(qǐng)向棧中輸入字符\n");
for (i = 0; i < 7; i++)
{
scanf_s("%c", &e);
Push(S, e);//入棧
}
printf("已初始化棧如下\n");
PrintStack(S);
GetTop(S, f);//獲取棧頂元素
printf("棧頂元素為\n");
putchar(f);
printf("刪除棧頂元素\n");
Pop(S, k);//出棧
printf("更新棧如下\n");
PrintStack(S);
printf("下面進(jìn)入括號(hào)匹配\n");
SqStack B;
InitStack(B);
March_Brackets(B);
return 0;
}運(yùn)行結(jié)果
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-732587.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】順序棧的基本操作：出棧、入棧、取棧頂元素、輸出所有棧中元素、括號(hào)匹配題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
