摘要：栈是一种新的数据结构，在我们生活中其实也有很多，只是我们没有关注。栈可以形象为一个死胡同，秉承着“先进后出，后进先出”的原则。栈相较于之前的链表较为简单，但其应用十分广泛。
一.代码块
1）栈的创建
#define MAXSIZE 10
typedef struct charStack
{
int top;//记录栈顶的位置，方便我们压栈和出栈
char data[MAXSIZE];//存储数据的本质还是数组
}*charStackPtr;
2）栈的初始化
charStackPtr stackInit()
{
charStackPtr resultStack = (charStackPtr)malloc(sizeof(struct charStack));
resultStack->top = -1;//栈顶在-1，表示该栈为空栈
return resultStack;
}
3）栈的打印
void outputStack(charStackPtr paraStack)
{
int i;
for(i = 0;i <= paraStack->top;i ++)
{
printf("%c ",paraStack->data[i]);
}
printf("rn");
}
4）压栈
void push(charStackPtr paraStack,char paraChar)
{
if(paraStack->top >= MAXSIZE-1)
{
printf("Cannot push element:stack fullrn");
return ;
}
paraStack->top ++;
paraStack->data[paraStack->top] = paraChar;
}
5）出栈
char pop(charStackPtr paraStack)
{
if(paraStack->top < 0)
{
printf("Cannot pop element:stack empty");
return ' ';
}
paraStack->top --;
return paraStack->data[(paraStack->top)+1];
}
6）压栈出栈测试函数
void pushPopTest()
{
char ch;
int i;
printf("---- pushPopTest begins. ----rn");
charStackPtr tempStack = stackInit();
printf("After initialization, the stack is: ");
outputStack(tempStack);
for (ch = 'a'; ch < 'm'; ch ++)
{
printf("Pushing %c.rn", ch);
push(tempStack, ch);
outputStack(tempStack);
}
for (i = 0; i < 3; i ++)
{
ch = pop(tempStack);
printf("Pop %c.rn", ch);
outputStack(tempStack);
}
printf("---- pushPopTest ends. ----rn");
}
7）括号匹配（栈的简单应用）
int bracketMatching(char paraString[],int paraLength)
{
//不知道为啥我的编译器不支持bool，我就用int代替的，效果一样
int i;
char tempChar,tempPopedChar;
charStackPtr tempStack = stackInit();
push(tempStack,'#');
tempStack->top = 0;
for(i = 0;i < paraLength;i ++)
{
tempChar = paraString[i];
switch (tempChar)
{
case '(':
case '[':
case '{':
push(tempStack,tempChar);
break;
case ')':
tempPopedChar = pop(tempStack);
if(tempPopedChar != '(')
{
return 0;
}
break;
case ']':
tempPopedChar = pop(tempStack);
if(tempPopedChar != '[')
{
return 0;
}
break;
case '}':
tempPopedChar = pop(tempStack);
if(tempPopedChar != '{')
{
return 0;
}
break;
default :
break;
}
}
//如何判断为空栈，直接用到了我们的#号
tempPopedChar = pop(tempStack);
if(tempPopedChar != '#')
{
return 0;
}
return 1;
}
8）括号匹配测试函数
void bracketMatchingTest()
{
char* tempExpression = "[2 + (1 - 3)] * 4";
int tempMatch = bracketMatching(tempExpression, 17);
printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
tempExpression = "( ) )";
tempMatch = bracketMatching(tempExpression, 6);
printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
tempExpression = "()()(())";
tempMatch = bracketMatching(tempExpression, 8);
printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
tempExpression = "({}[])";
tempMatch = bracketMatching(tempExpression, 6);
printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
tempExpression = "((((";
tempMatch = bracketMatching(tempExpression, 4);
printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
tempExpression = ")(";
tempMatch = bracketMatching(tempExpression, 2);
printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}
三.全部代码
#include#include #define MAXSIZE 10 typedef struct charStack { int top;//记录栈顶的位置，方便我们压栈和出栈 char data[MAXSIZE];//存储数据的本质还是数组 }*charStackPtr; charStackPtr stackInit() { charStackPtr resultStack = (charStackPtr)malloc(sizeof(struct charStack)); resultStack->top = -1;//栈顶在-1，表示该栈为空栈 return resultStack; } void outputStack(charStackPtr paraStack) { int i; for(i = 0;i <= paraStack->top;i ++) { printf("%c ",paraStack->data[i]); } printf("rn"); } void push(charStackPtr paraStack,char paraChar) { if(paraStack->top >= MAXSIZE-1) { printf("Cannot push element:stack fullrn"); return ; } paraStack->top ++; paraStack->data[paraStack->top] = paraChar; } char pop(charStackPtr paraStack) { if(paraStack->top < 0) { printf("Cannot pop element:stack empty"); return ' '; } paraStack->top --; return paraStack->data[(paraStack->top)+1]; } void pushPopTest() { char ch; int i; printf("---- pushPopTest begins. ----rn"); charStackPtr tempStack = stackInit(); printf("After initialization, the stack is: "); outputStack(tempStack); for (ch = 'a'; ch < 'm'; ch ++) { printf("Pushing %c.rn", ch); push(tempStack, ch); outputStack(tempStack); } for (i = 0; i < 3; i ++) { ch = pop(tempStack); printf("Pop %c.rn", ch); outputStack(tempStack); } printf("---- pushPopTest ends. ----rn"); } int bracketMatching(char paraString[],int paraLength) { //不知道为啥我的编译器不支持bool，我就用int代替的，效果一样 int i; char tempChar,tempPopedChar; charStackPtr tempStack = stackInit(); push(tempStack,'#'); tempStack->top = 0; for(i = 0;i < paraLength;i ++) { tempChar = paraString[i]; switch (tempChar) { case '(': case '[': case '{': push(tempStack,tempChar); break; case ')': tempPopedChar = pop(tempStack); if(tempPopedChar != '(') { return 0; } break; case ']': tempPopedChar = pop(tempStack); if(tempPopedChar != '[') { return 0; } break; case '}': tempPopedChar = pop(tempStack); if(tempPopedChar != '{') { return 0; } break; default : break; } } //如何判断为空栈，直接用到了我们的#号 tempPopedChar = pop(tempStack); if(tempPopedChar != '#') { return 0; } return 1; } void bracketMatchingTest() { char* tempExpression = "[2 + (1 - 3)] * 4"; int tempMatch = bracketMatching(tempExpression, 17); printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch); tempExpression = "( ) )"; tempMatch = bracketMatching(tempExpression, 6); printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch); tempExpression = "()()(())"; tempMatch = bracketMatching(tempExpression, 8); printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch); tempExpression = "({}[])"; tempMatch = bracketMatching(tempExpression, 6); printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch); tempExpression = "(((("; tempMatch = bracketMatching(tempExpression, 4); printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch); tempExpression = ")("; tempMatch = bracketMatching(tempExpression, 2); printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch); } int main() { pushPopTest(); bracketMatchingTest(); }
四.运行结果
---- pushPopTest begins. ----
After initialization, the stack is:
Pushing a.
a
Pushing b.
a b
Pushing c.
a b c
Pushing d.
a b c d
Pushing e.
a b c d e
Pushing f.
a b c d e f
Pushing g.
a b c d e f g
Pushing h.
a b c d e f g h
Pushing i.
a b c d e f g h i
Pushing j.
a b c d e f g h i j
Pushing k.
Cannot push element:stack full
a b c d e f g h i j
Pushing l.
Cannot push element:stack full
a b c d e f g h i j
Pop j.
a b c d e f g h i
Pop i.
a b c d e f g h
Pop h.
a b c d e f g
---- pushPopTest ends. ----
Is the expression '[2 + (1 - 3)] * 4' bracket matching? 1
Is the expression '( ) )' bracket matching? 0
Is the expression '()()(())' bracket matching? 1
Is the expression '({}[])' bracket matching? 1
Is the expression '((((' bracket matching? 0
Is the expression ')(' bracket matching? 0
