栈的实现，使元素存放在一个地方，先进入的元素后出来，可以想成一个有一面底部的圆柱体，放入带有序号的小球（小球半径比圆柱体小一点，保证小球进入后不能相互交换位置）， 这样先进入的小球要出来，就要等后进来的小球出去之后才行，形成了先进后出现象，这一特点可以用于实现计算机的返回操作。用链表和数组都能实现，这里用的数组。
栈的实现 创建栈：说明：
top 表示栈顶
代码：
typedef struct CharStack {
int top;
int data[STACK_MAX_SIZE];
}*CharStackPtr;
栈的初始化：
说明：
top赋予-1,栈空
代码：
CharStackPtr charStackInit() {
CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
resultPtr->top = -1;
return resultPtr;
}
栈的基本操作：
进栈：
说明：
最先进入的数据元素放在栈底，最后进入的放在最上面。
代码：
void push(CharStackPtr paraStackPtr, int paraValue) {
//Step 1.检查，栈是否是满的
if (paraStackPtr->top >= STACK_MAX_SIZE) {
printf("Cannot push element: stack is fulln");
return;
}
//Step 2.更新栈顶位置
paraStackPtr->top++;
//Step 3.放入元素.
paraStackPtr->data[paraStackPtr->top] = paraValue;
}
出栈：
说明：
先进后出，栈底的元素最后出栈，这是栈的特点
代码：
char pop(CharStackPtr paraStackPtr) {
//Step 1.检查是否为空
if(paraStackPtr->top < 0){
printf("Cannot pop element: stack empty.n");
return ' ';
}
//Step 2.更新栈顶
paraStackPtr->top--;
//Step 3.弹出元素
return paraStackPtr->data[paraStackPtr->top + 1];
}
栈的应用：
括号匹配
思路：
利用在运算中，括号总是成对出现的，且都是局部对称的，所有可以用栈，存储局部对称的一半（左边），一个一个弹出来进行比较。
图解：
代码：
bool bracketMatching(char* paraString, int paraLength) {
//Step 1. Initailize the stack through pushing a '#' at the bottom.
CharStackPtr tempStack = charStackInit();
push(tempStack, '#');
char tempChar, tempPopedChar;
//Step 2.Process the string.
for (int i = 0; i < paraLength; i++) {
tempChar = paraString[i];
switch (tempChar) {
case '(':
case '[':
case '{':
push(tempStack, tempChar);
break;
case ')':
tempPopedChar = pop(tempStack);
if (tempPopedChar != '(') {
return false;
}//Of if
break;
case ']':
tempPopedChar = pop(tempStack);
if (tempPopedChar != '[') {
return false;
}//Of if
break;
case '}':
tempPopedChar = pop(tempStack);
if (tempPopedChar != '{') {
return false;
}//Of if
break;
default:
break;
}//Of switch
}//Of for i
tempPopedChar = pop(tempStack);
if (tempPopedChar != '#') {
return false;
}//Of if
return true;
}
总代码：
#include总结：#include #define STACK_MAX_SIZE 10 typedef struct CharStack { int top; int data[STACK_MAX_SIZE];//The maximum length is fixed. }*CharStackPtr; void outputStack(CharStackPtr paraStack) { if ( paraStack->top == -1) { printf("The stack is empty！n"); return; } for (int i = 0; i <=paraStack->top; i++) { printf("%c ", paraStack->data[i]); }//Of for i printf("rn"); }//Of outputStack CharStackPtr charStackInit() { CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack)); resultPtr->top = -1; return resultPtr; } void push(CharStackPtr paraStackPtr, int paraValue) { //Step 1.Space check. if (paraStackPtr->top >= STACK_MAX_SIZE) { printf("Cannot push element: stack is fulln"); return; } //Step 2.Updata the top. paraStackPtr->top++; //Step 3.Push element. paraStackPtr->data[paraStackPtr->top] = paraValue; }//Of push char pop(CharStackPtr paraStackPtr) { //Step 1.Space check. if(paraStackPtr->top < 0){ printf("Cannot pop element: stack empty.n"); return ' '; } //Step 2.Update the top. paraStackPtr->top--; //Step 3.Push element. return paraStackPtr->data[paraStackPtr->top + 1]; }//Of pop void pushPopTest(){ printf("--- pushPopTest Begins.---n"); //Initailize. CharStackPtr tempStack = charStackInit(); printf("Afer initialization, the stack is: "); outputStack(tempStack); //Push for (char ch = 'a'; ch < 'm'; ch++) { printf("Pushing %c.n", ch); push(tempStack, ch); outputStack(tempStack); }//Of For i //Pop char temp; for (int i = 0; i < 3; i++) { temp = pop(tempStack); printf("Pop %cn", temp); outputStack(tempStack); }//Of for i printf("--- pushPopTest Ends.---n"); } bool bracketMatching(char* paraString, int paraLength) { //Step 1. Initailize the stack through pushing a '#' at the bottom. CharStackPtr tempStack = charStackInit(); push(tempStack, '#'); char tempChar, tempPopedChar; //Step 2.Process the string. for (int i = 0; i < paraLength; i++) { tempChar = paraString[i]; switch (tempChar) { case '(': case '[': case '{': push(tempStack, tempChar); break; case ')': tempPopedChar = pop(tempStack); if (tempPopedChar != '(') { return false; }//Of if break; case ']': tempPopedChar = pop(tempStack); if (tempPopedChar != '[') { return false; }//Of if break; case '}': tempPopedChar = pop(tempStack); if (tempPopedChar != '{') { return false; }//Of if break; default: break; }//Of switch }//Of for i tempPopedChar = pop(tempStack); if (tempPopedChar != '#') { return false; }//Of if return true; } void bracketMatchingTest() { char* tempExpression = "[2 + (1 - 2)] * 4"; if(bracketMatching(tempExpression, 17)) { printf("The expression: %s is matching.n", tempExpression); } else { printf("The expression: %s is not matching.n", tempExpression); } tempExpression = "())"; if(bracketMatching(tempExpression, 3)) { printf("The expression: %s is matching.n", tempExpression); } else { printf("The expression: %s is not matching.n", tempExpression); } tempExpression = ")"; if(bracketMatching(tempExpression, 1)) { printf("The expression: %s is matching.n", tempExpression); } else { printf("The expression: %s is not matching.n", tempExpression); } tempExpression = "()(){}(({}))"; if(bracketMatching(tempExpression, 12)) { printf("The expression: %s is matching.n", tempExpression); } else { printf("The expression: %s is not matching.n", tempExpression); } tempExpression = "({}[])"; if(bracketMatching(tempExpression, 6)) { printf("The expression: %s is matching.n", tempExpression); } else { printf("The expression is not matching.n"); } tempExpression = ")(()"; if(bracketMatching(tempExpression, 4)) { printf("The expression: %s is matching.n", tempExpression); } else { printf("The expression: %s is not matching.n", tempExpression); } } int main(){ pushPopTest(); bracketMatchingTest(); return 0; }
栈作为一种 数据结构 ，是一种只能在一端进行插入和删除操作的特殊 线性表 。 它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
值得注意的是，可以把数组0号位不存放有效字符来作为栈底。
