【数据结构及算法】栈（stack）的概念及C语言实现

大家好，我是讯享网，很高兴认识大家。

0x00 前言

文章中的文字可能存在语法错误以及标点错误，请谅解；

如果在文章中发现代码错误或其它问题请告知，感谢！

0x01 栈的概念和定义

1.概念

栈（stacks）是一种只能从表的一端存取数据且遵循 先进后出（last in first out，FILO）原则的线性存储结构。具体来说，它是一个仅对表尾进行插入或删除的操作线性表。栈的表尾称为栈顶（top），栈的表头称为栈底（bottom）。栈的示意图如下：
在这里插入图片描述
讯享网

2.进栈和出栈

因为栈具有仅对表尾进行操作的特点，所以对栈的操作有两种：
进栈：向栈表栈顶添加元素。
出栈：从栈表栈顶取出元素。

3.栈的两种表示

栈有两种表示方式：顺序栈和链栈。
顺序栈是利用一组地址连续的存储空间依次存放自栈底到栈顶的数据元素；对于顺序栈通常会附设两个指针top以及base，其中base为栈底指针，指向栈底，不随着栈内元素增加而改变；top为栈顶指针，指向栈顶，top指针初值指向栈底即base位置，当有新的数据元素进栈后（从base起始位置存放），每增加一个元素，top指针增加1，当删除栈顶元素时，top指针减1，在非空栈中，栈顶指针top始终在栈顶元素的下一个位置。另外，还需要指定栈的初始长度，确定栈的大小。在使用栈的过程中，会出现栈空间不够的情况，这时候可以设置一个栈空间增量大小来扩充栈。
在这里插入图片描述
顺序栈的类型定义一般形式如下：

typedef struct{ 
    SElemtype *base; //栈底指针 SElemtype *top; //栈顶指针 int stacksize; //栈初始长度 }Sqstack；

讯享网

链栈采用链式存储结构，可以在需要时申请，数据元素可以不在连续的存储空间上。链栈示意图如下：
在这里插入图片描述

链栈的类型定义一般形式如下：

讯享网typedef struct { 
    Elemtype data; struct Sqstack *next; }Sqstack;

4.线性表、链表、栈、队列

0x02 顺序栈和链栈程序举例

1.顺序栈代码举例

#include<stdio.h> #include<stdlib.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 20 typedef struct { 
    char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈初始长度 }Sqstack; //栈初始化 int InitStack(Sqstack *S) { 
    S->base = (char*)malloc(STACK_INIT_SIZE * sizeof(char)); if(NULL == S->base) return -1; S->top = S->base; S->stacksize = STACK_INIT_SIZE; return 0; } //入栈 int Push(Sqstack *S, char e) { 
    if(S->top - S->base >= S->stacksize) { 
    S->base = (char*)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(char)); if(NULL == S->base) return -1; S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } *S->top++ = e; return 0; } //出栈 int Pop(Sqstack *S, char *e) { 
    if(S->top == S->base) return -1; *e = *--S->top; return 0; } int main() { 
    Sqstack stack = { 
   0}; char res = 0; InitStack(&stack); Push(&stack, 'a'); Push(&stack, 'b'); Push(&stack, 'c'); Push(&stack, 'd'); Pop(&stack, &res); printf("出栈元素：%c\n",res); Pop(&stack, &res); printf("出栈元素：%c\n",res); Pop(&stack, &res); printf("出栈元素：%c\n",res); Pop(&stack, &res); printf("出栈元素：%c\n",res); return 0; }

运行结果：
在这里插入图片描述

2.链栈代码举例

讯享网#include <stdio.h> #include <stdlib.h> typedef struct { 
    char data; struct Sqstack *next; }Sqstack; //入栈 Sqstack* push(Sqstack *stack,char a) { 
    Sqstack *res=(Sqstack*)malloc(sizeof(Sqstack)); res->data = a; res->next = stack; stack = res; return stack; } //出栈 Sqstack * pop(Sqstack *stack) { 
    if (stack) { 
    Sqstack *p = stack; stack=stack->next; printf("出栈元素：%c ",p->data); if (stack) { 
    printf("栈顶元素：%c\n",stack->data); } else { 
    printf("栈已空\n"); } free(p); } else { 
    printf("栈为空\n"); return stack; } return stack; } int main() { 
    Sqstack *stack=NULL; stack=push(stack, 'a'); stack=push(stack, 'b'); stack=push(stack, 'c'); stack=push(stack, 'd'); stack=pop(stack); stack=pop(stack); stack=pop(stack); stack=pop(stack); stack=pop(stack); return 0; }

运行结果：
在这里插入图片描述

0x03 leetcode栈相关题目

1.有效括号问题

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

讯享网bool isValid(char * s) { 
    if(NULL == s || '\0' == s[0]) { 
    return true; } int count = 0; int i = 0; int len = 0; len = strlen(s); char *temp_srt = (char*)malloc(sizeof(char)*len); char *p = s; for(i = 0;i<len;i++) { 
    if('(' == p[i] || '{' == p[i] || '[' == p[i]) { 
    //printf("1%c,i:%d count:%d\n",p[i],i,count); temp_srt[count] = p[i]; count++; } else if(')' == p[i] || '}' == p[i] || ']' == p[i]) { 
    if(count>0) { 
    if(temp_srt[count-1] == p[i]-1 || temp_srt[count-1] == p[i]-2) { 
    count--; } else { 
    free(temp_srt); return false; } } else { 
    free(temp_srt); return false; } } } free(temp_srt); return (!count); }

2.用两个栈实现队列问题

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

1 <= values <= 10000 最多会对 appendTail、deleteHead 进行 10000 次调用

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

讯享网typedef struct __STACK_NODE__ { 
    int TreeNodeData; struct __STACK_NODE__ *next; }SNode_T, *SNode_P; typedef struct __STACK__ { 
    SNode_P top; int Num; }STACK_T, *STACK_P; //栈初始化 STACK_P StackInit() { 
    STACK_P stack = NULL; stack = (STACK_P)malloc(sizeof(STACK_T)); stack->top = (SNode_P)malloc(sizeof(SNode_T)); stack->top->next = NULL; stack->top->TreeNodeData = NULL; stack->Num = 0; return stack; } //入栈 void StackPush(STACK_P stack, int pTreeNode) { 
    SNode_P newSnode = NULL; if ((!pTreeNode)||(!stack)) { 
    return; } newSnode = malloc(sizeof(SNode_T)); newSnode->TreeNodeData = pTreeNode; newSnode->next = stack->top->next; stack->top->next = newSnode; stack->Num++; return; } //出栈 int StackPop(STACK_P stack) { 
    SNode_P tempnode = NULL; int PopTreeNode = NULL; if (!stack) { 
    return NULL; } if (stack->Num == 0) { 
    return NULL; } tempnode = stack->top->next; stack->top->next = tempnode->next; stack->Num--; PopTreeNode = tempnode->TreeNodeData; free(tempnode); return PopTreeNode; } //获取栈顶元素 int StackTop(STACK_P stack) { 
    SNode_P tempnode = NULL; int PopTreeNode = NULL; if (!stack) { 
    return NULL; } if (stack->Num == 0) { 
    return NULL; } return stack->top->next->TreeNodeData; } //销毁 void StackFree(STACK_P stack) { 
    SNode_P tempnode = NULL; int PopTreeNode = NULL; if (!stack) { 
    return NULL; } while (stack->Num > 0) { 
    StackPop(stack); } free(stack->top); free(stack); return ; } typedef struct { 
    STACK_P left; STACK_P right; int datanum; } CQueue; CQueue queue; CQueue* cQueueCreate() { 
    queue.left = StackInit(); queue.right = StackInit(); queue.datanum = 0; return &queue; } void cQueueAppendTail(CQueue* obj, int value) { 
    StackPush(obj->left, value); obj->datanum++; } int cQueueDeleteHead(CQueue* obj) { 
    if(obj->datanum == 0) { 
    return -1; } if (obj->right->Num == 0) { 
    while(obj->left->Num>0) { 
    StackPush(obj->right, StackPop(obj->left)); } } obj->datanum--; return StackPop(obj->right); } void cQueueFree(CQueue* obj) { 
    StackFree(obj->left); StackFree(obj->right); obj->datanum = 0; } / * Your CQueue struct will be instantiated and called as such: * CQueue* obj = cQueueCreate(); * cQueueAppendTail(obj, value); * int param_2 = cQueueDeleteHead(obj); * cQueueFree(obj); */

以上。

参考文档：
1.http://data.biancheng.net/view/9.html
2.http://c.biancheng.net/view/3349.html
3. 严蔚敏.吴伟明.数据结构（C语言版）[M].北京：清华大学出版社,2020.