本文主要是介绍C语言数据结构之栈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 1.栈的概念及结构
- 2.栈的实现
- 3.栈的代码实现
- 4.相关例题
•͈ᴗ•͈
个人主页:御翮
•͈ᴗ•͈
个人专栏:C语言数据结构
•͈ᴗ•͈
欢迎大家关注和订阅!!!
1.栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
讲到栈,就要提到它的两种基本操作:压栈(入栈)和出栈。
入栈和出栈遵循一种规则:后进先出(进入栈晚的数据先出栈,就像是先进去的数据被后进入的数据压住了,只能先把上面的数据拿走才能拿到下面的数据)。
连续入栈和连续出栈:
2.栈的实现
对于栈的实现,我们有两种结构可以选择:顺序表和链表。考虑到先进后出的规则,链表尾插和尾删的成本比顺序表高,不太适合,顺序表尾插和尾删只需要改变加减的size的大小就可以做到,所以我们采用顺序表来实现栈。
关于栈,我们要实现以下几个接口:
3.栈的代码实现
test.c
#include "Stack.h"void menu()
{printf("********************************************\n");printf("*************** 请选择 ***************\n");printf("****** 1.PushStack 2.PopStack *******\n");printf("****** 3.PrintStack 4.TopStack *******\n");printf("****** 5.SizeStack 6.CheckEmpty *******\n"); printf("****** 0.Exit *******\n");printf("********************************************\n");
}int main()
{int input = 0;int value = 0;Stack s;Init_Stack(&s);do{menu();scanf("%d", &input);switch (input){case 1:printf("请输入你要入栈的值>:");scanf("%d", &value);Push_Stack(&s, value);break;case 2:Pop_Stack(&s);break;case 3:Print_Stack(&s);break;case 4:if (Empty_Stack(&s) != 0){printf("栈为空\n");break;}printf("栈顶的元素是%d\n", Top_Stack(&s));break;case 5:printf("栈中有效元素的个数为%d\n", Size_Stack(&s));break;case 6:if (Empty_Stack(&s) != 0)printf("栈为空\n");elseprintf("栈不为空\n");break;case 0:Destroy_Stack(&s);printf("销毁栈成功\n");break;default:printf("选择错误,请重新选择\n");break;}} while (input);return 0;
}
Stack.c
#include "Stack.h"//初始化栈
void Init_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针STDataType* tmp = (STDataType*)malloc(3*sizeof(STDataType));if (tmp == NULL) //申请空间可能失败,失败会返回NULL,不能解引用,要终止程序{perror("Init_Stack\n");exit(1);}ptr->stack = tmp; //申请空间成功就正常初始化ptr->capacity = 3;ptr->size = 0;
}//销毁栈
void Destroy_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针free(ptr->stack);ptr->stack = NULL;
}//检查栈是否满了,满了则扩容
void Check_Capacity(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针if (ptr->size == ptr->capacity){STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));if (tmp == NULL) //申请空间可能失败,失败会返回NULL,不能解引用,要终止程序{perror("Check_Capacity\n");exit(1);}ptr->stack = tmp; //要把申请到的空间赋给原指针,不然后面操作不了这块空间ptr->capacity *= 2; //扩容之后要修改capacity的值,不然检查栈的大小时会一直扩容}
}//打印栈里面的数据
void Print_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针for (int i = 0; i < ptr->size; i++){printf("%d ", ptr->stack[i]);}printf("\n");
}//数据入栈
void Push_Stack(Stack* ptr,STDataType val)
{assert(ptr); // ptr要解引用,不能为空指针Check_Capacity(ptr); //入栈时要检查空间是否足够ptr->stack[ptr->size] = val;ptr->size++;
}//数据出栈
void Pop_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针if (ptr->size == 0){printf("栈为空\n");return;}ptr->size--; //出栈就相当于顺序表可以读取的元素少一个,size - 1 就可以了
}//获取栈顶数据
STDataType Top_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针return ptr->stack[ptr->size-1];
}//获取栈储存的元素个数
int Size_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针return ptr->size;
}//判断栈是否为空
int Empty_Stack(Stack* ptr)
{assert(ptr); // ptr要解引用,不能为空指针if (ptr->size == 0)return 1;elsereturn 0;
}
Stack.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>typedef int STDataType; // 栈储存的数据的类型typedef struct Stack
{STDataType* stack; //动态开辟的空间,在堆上int size; //储存元素的个数int capacity; //栈的大小(容量),可变化
}Stack;//栈的初始化
void Init_Stack(Stack* ptr);//打印栈里面的数据
void Print_Stack(Stack* ptr);//数据入栈
void Push_Stack(Stack* ptr, STDataType val);//数据出栈
void Pop_Stack(Stack* ptr);//获取栈顶数据
STDataType Top_Stack(Stack* ptr);//获取栈储存元素的个数
int Size_Stack(Stack* ptr);//判断栈是否为空
int Empty_Stack(Stack* ptr);//销毁栈
void Destroy_Stack(Stack* ptr);
4.相关例题
题目描述:
参考解析:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* stack;int size;int capacity;
}Stack;void Init_Stack(Stack* ptr)
{assert(ptr);STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType));if (tmp == NULL){perror("Init_Stack\n");exit(1);}ptr->stack = tmp;ptr->capacity = 3;ptr->size = 0;
}void Destroy_Stack(Stack* ptr)
{assert(ptr);free(ptr->stack);ptr->stack = NULL;
}void Check_Capacity(Stack* ptr)
{assert(ptr);if (ptr->size == ptr->capacity){STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));if (tmp == NULL){perror("Check_Capacity\n");exit(1);}ptr->stack = tmp;ptr->capacity *= 2;}
}void Print_Stack(Stack* ptr)
{assert(ptr);for (int i = 0; i < ptr->size; i++){printf("%d ", ptr->stack[i]);}printf("\n");
}void Push_Stack(Stack* ptr, STDataType val)
{assert(ptr);Check_Capacity(ptr);ptr->stack[ptr->size] = val;ptr->size++;
}void Pop_Stack(Stack* ptr)
{assert(ptr);if (ptr->size == 0){return;}ptr->size--;
}STDataType Top_Stack(Stack* ptr)
{assert(ptr);return ptr->stack[ptr->size - 1];
}int Size_Stack(Stack* ptr)
{assert(ptr);return ptr->size;
}int Empty_Stack(Stack* ptr)
{assert(ptr);if (ptr->size == 0)return 1;elsereturn 0;
}//解题思路:
//该题比较简单,是对栈特性很好的应用,具体操作如下:
//循环遍历String中的字符,逐个取到每个括号,如果该括号是:
//1. 左括号,直接入栈
//2. 右括号,与栈顶的左括号进行匹配,如果不匹配直接返回false
//否则继续循环
//循环结束后,如果栈空则匹配,否则左括号比右括号多肯定不匹配bool isValid(char* s)
{Stack st;Init_Stack(&st);while (*s){switch (*s){//是左括号则入栈case '(':case '{':case '[':Push_Stack(&st, *s);break;//是右括号则从栈顶获取左括号来检测是否匹配case ')':case '}':case ']':if (Size_Stack(&st) == 0) // 如果有右括号,而栈里面左括号已经没有了,就不是匹配的return false;char tmp = Top_Stack(&st);Pop_Stack(&st); // 取完元素要从栈中删除if (tmp == '(' && *s != ')')return false;else if (tmp == '{' && *s != '}')return false;else if (tmp == '[' && *s != ']')return false;}s++;}if (Empty_Stack(&st)) // 如果完全匹配,循环结束时栈内一定是空的return true;elsereturn false;
}
这篇关于C语言数据结构之栈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!