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

古城微笑少年丶 2023-02-28 08:49 14阅读 0赞

# 0x00 前言 #

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

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

# 0x01 栈的概念和定义 #

## 1.概念 ##

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

## 2.进栈和出栈 ##

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

## 3.栈的两种表示 ##

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

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

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

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

typedef struct
    { 
        Elemtype data;
        struct Sqstack *next;
    }Sqstack;

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

为了厘清线性表、链表、栈、队列之间的的关系可以参考如下链接：  
[https://blog.csdn.net/qq\_26849233/article/details/72235521][https_blog.csdn.net_qq_26849233_article_details_72235521]

# 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;
    }

运行结果：  
![在这里插入图片描述][2020072117414360.png]

## 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;
    }

运行结果：  
![在这里插入图片描述][20200721183643546.png]

# 0x03 leetcode栈相关题目 #

## 1.有效括号问题 ##

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

有效字符串需满足：

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

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

示例 1:

输入: “()”  
输出: true

示例 2:

输入: “()\[\]\{\}”  
输出: true

示例 3:

输入: “(\]”  
输出: false

示例 4:

输入: “(\[)\]”  
输出: false

示例 5:

输入: “\{\[\]\}”  
输出: true

来源：力扣（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][http_data.biancheng.net_view_9.html]  
2.[http://c.biancheng.net/view/3349.html][http_c.biancheng.net_view_3349.html]  
3. 严蔚敏.吴伟明.数据结构（C语言版）\[M\].北京：清华大学出版社,2020.

[20200721104914796.jpg_pic_center]: /images/20230209/ff363edf998547889cf8ca7597ec841e.png
[2020072115312455.jpg]: /images/20230209/ac70575d78d54647a04f1046e9a0479c.png
[20200721162142613.jpg]: /images/20230209/fa0ece170f41486a8916f3a668fad4fa.png
[https_blog.csdn.net_qq_26849233_article_details_72235521]: https://blog.csdn.net/qq_26849233/article/details/72235521
[2020072117414360.png]: /images/20230209/8ec07d2bd4014165a615e67f298c354e.png
[20200721183643546.png]: /images/20230209/307521c7697246de83150c0abaf3ae6a.png
[http_data.biancheng.net_view_9.html]: http://data.biancheng.net/view/9.html
[http_c.biancheng.net_view_3349.html]: http://c.biancheng.net/view/3349.html