栈的实现

简介: 栈的实现

一、 栈的概念以及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为 栈顶 ,另一端称为 栈底 。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。【后进先出】

压栈:栈的插入操作叫做进栈/压栈/入栈, 入数据在栈顶。

出栈:栈的删除操作叫做出栈。 出数据也在栈顶。

一个是数据结构中的栈,是一个数据结构;一个是操作系统中内存划分的一个区域,也叫作栈,是用来函数调用时,建立栈帧。相似点是,都是后进先出。【这两个没有特别的关系,属于两个学科中的名词】

入栈时是:1234,,出栈时是4321吗?答案是不一定的,后进先出,是相对而言的,如果2进的时候,1已经出来了,那么1就会在2的前面,所以是不一定的。

二、 栈的实现

栈的实现,是选择数组还是链表呢?答案是:数组。   单链表也可以,但是数组更好

ღ理由是:可以把数组的后面当做栈顶,前面当做栈底。插入,删除方便,但是要扩容。CPU高速缓存命中率会更高。

stack.h

1. #pragma once
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <assert.h>
5. #include <stdbool.h>
6. 
7. typedef int STDataType;
8. 
9. typedef struct stack
10. {
11.   STDataType* a;
12.   int top;//栈顶的位置
13.   int capacity;//容量
14. }ST;
15. 
16. void StackInit(ST* ps);
17. void StackDestory(ST* ps);
18. //插入
19. void StackPush(ST* ps, STDataType x);
20. //删除
21. void StackPop(ST* ps);
22. //判断栈是否为空
23. bool StackEmpty(ST* ps);
24. //栈有多少个数
25. int StackSize(ST* ps);
26. //访问栈顶的数据
27. STDataType StackTop(ST* ps);

stack.c

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "stack.h"
3. 
4. void StackInit(ST* ps)
5. {
6.  assert(ps);
7.  ps->a = NULL;
8.  ps->top = 0;
9.  ps->capacity = 0;
10. }
11. void StackDestory(ST* ps)
12. {
13.   assert(ps);
14.   free(ps->a);
15.   ps->a = NULL;
16.   ps->top = ps->capacity = 0;
17. }
18. //插入
19. void StackPush(ST* ps, STDataType x)
20. {
21.   assert(ps);
22.   //扩容
23.   if (ps->capacity == ps->top)//
24.   {
25.     int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);//容量
26.     ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));//
27.     if (ps->a == NULL)
28.     {
29.       printf("realloc fail \n");
30.       exit(-1);
31.     }
32.     ps->capacity = newCapacity;
33.   }
34. 
35.   ps->a[ps->top] = x;
36.   ps->top++;
37. }
38. //删除
39. void StackPop(ST* ps)
40. {
41.   assert(ps);
42.   assert(ps->top > 0);
43.   --ps->top;
44. }
45. //判断栈是否为空
46. bool StackEmpty(ST* ps)
47. {
48.   assert(ps);
49.   return ps->top == 0;//等于0的话,就是真,不等于0的话,就是假
50. }
51. //栈有多少个数
52. int StackSize(ST* ps)
53. {
54.   assert(ps);
55.   return ps->top;
56. }
57. //访问栈顶的数据
58. STDataType StackTop(ST* ps)
59. {
60.   assert(ps);
61.   return ps->a[ps->top - 1];
62. }

元素插入的时候(1)如果top初始化的是0,那么就是栈顶元素的后一个位置。【就是在插入元素的后一个位置】先插入元素,top再++(2)top刚开始是-1,top指向栈顶元素,top先++,再放数据。【top指的是下标】

打印栈的元素,需要首先判断栈是否为空,不为空的话,就打印栈顶的元素,然后再删除栈顶的元素,再次进入循环判断栈是否为空。

1. while (!StackEmpty(&st))
2.  {
3.    printf("%d ", StackTop(&st));
4.    StackPop(&st);
5.  }

三、习题

3.1 选择题

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是(B)。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

2.若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是(C)

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

【进栈过程中可以出栈】

 

3.2 括号匹配问题

https://leetcode.cn/problems/valid-parentheses/

代码如下:【此代码里面不包括栈,仅仅把栈的实现的上述代码把int换成char】

1. bool isValid(char * s)
2. {
3.     ST st;
4. StackInit(&st);
5. while(*s)
6.     {
7. if (*s == '(' || *s == '[' || *s == '{')
8.         {
9. StackPush(&st, *s);
10.             s++;
11.         }
12. else
13.         {
14. if (StackEmpty(&st))
15.             {
16. return false;
17.             }
18. char top = StackTop(&st);
19. StackPop(&st);
20. if ((*s == ']' && top != '[') || (*s == ')' && top != '(') || (*s == '}' && top != '{'))
21.             {
22. StackDestory(&st);
23. return false;
24.             }
25. else
26.             {
27.                 s++;
28.             }
29.         }
30.     }
31. bool ret = StackEmpty(&st);
32. StackDestory(&st);
33. return ret;
34. }

思路:用栈。遍历字符串,如果遇到左括号就入栈,如果是右括号就进行匹配,不匹配就返回false,当遍历完字符串,如果全部匹配,就返回true

注意:C语言比较局限,要先写一个栈。代码区域必须包括栈。

目录
打赏
0
0
0
0
0
分享
相关文章
|
2月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
292 9
|
2月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
45 1
|
15天前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
132 77
|
15天前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
37 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
15天前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
39 9
|
15天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
30 7
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
90 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
104 21
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
2月前
|
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
63 4

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等