数据结构 C 栈及栈的应用

栈的定义

仅在表尾进行插入删除操作的线性表
栈顶：表尾端
栈底：表头端
空栈：不含元素的空表

特点：后进先出（如铁路调度站，撤销(后退键)等）

程序设计中：需要按照保存数据时相反的顺序来使用数据时，可利用栈来实现

顺序栈

顺序栈基本操作：1.初始化 2.入栈 3.出栈 4.测试

#include 
#include 


#define STACK_MAX_SIZE 10
typedef struct CharStack{
	int top;//栈顶元素的位置 
	int data[STACK_MAX_SIZE];
}*CharStackPtr;
int i;char ch; 


void outputStack(CharStackPtr paraStack){
	for( i=0 ; i <= paraStack->top ; i++ ){
		printf("%c",paraStack->data[i]);
	} //Of for i
	printf("rn");
}//Of outputStack


CharStackPtr initStack(){
	CharStackPtr resultPtr=(CharStackPtr)malloc(sizeof(struct CharStack));
	resultPtr->top = -1;
	return resultPtr;
} //Of initStack


void push(CharStackPtr paraStack,char paraChar){
	//判断栈是否已满（空间检查）
	if(paraStack->top >= STACK_MAX_SIZE-1){
		printf("Cannot push element: The stack is full.rn");
		return;
	} //Of if
	//更新栈顶 
	paraStack->top++;
	//添加元素到栈顶 
	paraStack->data[paraStack->top]=paraChar;
}//Of push


char pop(CharStackPtr paraStack){
	//检查栈是否为空 
	if(paraStack->top<0){
		printf("Cannot pop the element: The stack is empty.rn");
		return '';
	} //Of if
	//更新栈顶 
	paraStack->top--;
	//返回出栈元素 
	return paraStack->data[paraStack->top+1];
}//Of pop


void pushPopTest(){
	printf("---- pushPopTest begins. ----rn");
	//初始化init 
	CharStackPtr tempStackPtr=initStack();
	printf("After initialization, the stack is: rn");
	outputStack(tempStackPtr);
	//入栈push
	for(ch='a';ch<'m';ch++){
		printf("Pushing %c.rn",ch);
		push(tempStackPtr,ch);
		outputStack(tempStackPtr);
	}
	//出栈pop
	for(i=0;i<3;i++){
		ch=pop(tempStackPtr);
		printf("Poping %c.rn",ch);
		outputStack(tempStackPtr);
	}
	printf("---- pushPopTest ends. ----rn");
}//Of pushPopTest
int main() {
	pushPopTest();
	return 0;
}// Of main

运行结果

注意：

初始化时栈顶"指针"top为-1
入栈出栈都要进行空间检查
顺序栈的插入删除都只在栈顶进行
栈元素具有线性关系，即具有前驱后继关系（栈为特殊线性表）
栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制（在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就行）
扩展：两栈共享空间

括号匹配

#include 
#include 
#include

#define STACK_MAX_SIZE 10
typedef struct CharStack{
	int top;//栈顶元素的位置 
	int data[STACK_MAX_SIZE];
}*CharStackPtr;
int i;char ch; 


void outputStack(CharStackPtr paraStack){
	for( i=0 ; i <= paraStack->top ; i++ ){
		printf("%c",paraStack->data[i]);
	} //Of for i
	printf("rn");
}//Of outputStack


CharStackPtr initStack(){
	CharStackPtr resultPtr=(CharStackPtr)malloc(sizeof(struct CharStack));
	resultPtr->top = -1;
	return resultPtr;
} //Of initStack


void push(CharStackPtr paraStack,char paraChar){
	//判断栈是否已满（空间检查）
	if(paraStack->top >= STACK_MAX_SIZE-1){
		printf("Cannot push element: The stack is full.rn");
		return;
	} //Of if
	//更新栈顶 
	paraStack->top++;
	//添加元素到栈顶 
	paraStack->data[paraStack->top]=paraChar;
}//Of push


char pop(CharStackPtr paraStack){
	//检查栈是否为空 
	if(paraStack->top<0){
		printf("Cannot pop the element: The stack is empty.rn");
		return '';
	} //Of if
	//更新栈顶 
	paraStack->top--;
	//返回出栈元素 
	return paraStack->data[paraStack->top+1];
}//Of pop


void pushPopTest(){
	printf("---- pushPopTest begins. ----rn");
	//初始化init 
	CharStackPtr tempStackPtr=initStack();
	printf("After initialization, the stack is: rn");
	outputStack(tempStackPtr);
	//入栈push
	for(ch='a';ch<'m';ch++){
		printf("Pushing %c.rn",ch);
		push(tempStackPtr,ch);
		outputStack(tempStackPtr);
	}
	//出栈pop
	for(i=0;i<3;i++){
		ch=pop(tempStackPtr);
		printf("Poping %c.rn",ch);
		outputStack(tempStackPtr);
	}
	printf("---- pushPopTest ends. ----rn");
}//Of pushPopTest

bool bracketMatching(char* paraString,int paraLength){
	//初始化(统一操作：将'#'压入栈底)
	CharStackPtr tempStack=initStack();
	push(tempStack,'#');
	char tempchar,tempPopedchar;
	
	//处理字符串
	for(i=0;i 
运行结果 
 
注意：for循环结束后要再次检查栈中是否还有未匹配的括号（此处也是为什么初始化时要将'#'压入栈底，这里是一种“统一操作”） 
括号匹配的处理过程与栈的特点相吻合：每读入一个括号，若为右括号，则使置于栈顶的最急迫的期待得以消解，否则是不合法情况；若为左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中所有未消解的期待的紧迫性下降了一级。 
表达式求值 
#include 
#include 
#include 
#include //直接定义栈，需要stack头文件 
#include 
//在C++中使用cin和cout，需要包含头文件iostream以及std标准命名空间。
using namespace std;


stack num;
stack op;

//计算 
void eval()
{
    auto b = num.top();//auto：根据后边的值来推测前面的值是什么 
    num.pop();
    auto a = num.top();
    num.pop();
    auto c = op.top();
    op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);//计算结果入栈； 
}

int main()
{
    unordered_map pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};//运算符优先级 
    string str;
    cin >> str;//cin标准输入和cout标准输出
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))// c为数字 
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))//j不超过字符串的最大长度 
                x = x * 10 + str[j ++ ] - '0';//str[j ++ ] - '0'是将字符转化为数字的操作 
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);//c为左括号，压入运算符栈op 
        else if (c == ')')//c为右括号 
        {
            while (op.top() != '(') eval();//op栈顶元素不匹配，就计算 
            op.pop();//计算完毕，将op栈的栈顶元素弹出 
        }
        else
        {	//op栈不为空，栈顶元素不为左括号 ，栈顶元素优先级比当前元素c高 ：计算 
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);//计算完毕，将op栈的栈顶元素弹出
        }
    }
    while (op.size()) eval();//op栈不为空，继续算 
    cout << num.top() << endl;//输出计算结果 
    return 0;
} 
运行结果： 
 
 图解表达式求值：以3+(5-2)*4为例 
1.入栈（遇到右括号之前） 
 
2.遇到右括号之后，相继弹出进行计算  
  
3.让计算结果入栈  
  
 4.表达式遍历完毕，跳出for循环,进入while循环 
  
 5.while循环两次，一次计算3*4=12，将12入num栈；第二次再计算3+12=15，将15入num栈 
计算表达式核心思想：用两个栈，一个储存数字，一个储存操作符

数据结构 C 栈及栈的应用

C/C++/C#相关栏目本月热门文章