设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 顺序栈的操作
返回列表 发新帖
查看: 280|回复: 8

[已解决]顺序栈的操作

[复制链接]
tangpeng04
发表于 2023-12-6 20:35:15 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
顺序栈的操作
【实验要求】
(1) 建立含有若干个元素的顺序栈；
(2) 对已建立的顺序栈进行插入、删除、取栈顶元素等基本操作。
【实验提示】
首先定义顺序栈的数据类型 SqStack；对于题目要求的插入、删除、取栈顶
元素等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序栈的元
素。
最佳答案
月排行榜 / 总排行榜
FishC_GPT
2023-12-6 20:36:09
下面是一个简单的顺序栈的实现，包含了插入、删除和取栈顶元素等基本操作：
  1. #include <stdio.h>
  2. #define MAXSIZE 100
  4. typedef struct {
  5.     int data[MAXSIZE];
  6.     int top;
  7. } SqStack;
  9. // 初始化栈
  10. void InitStack(SqStack *stack) {
  11.     stack->top = -1;  // 栈为空时，top为-1
  12. }
  14. // 判断栈是否为空
  15. int IsEmpty(SqStack *stack) {
  16.     return stack->top == -1;
  17. }
  19. // 判断栈是否已满
  20. int IsFull(SqStack *stack) {
  21.     return stack->top == MAXSIZE - 1;
  22. }
  24. // 插入元素
  25. int Push(SqStack *stack, int value) {
  26.     if (IsFull(stack)) {
  27.         printf("栈已满，无法插入元素\n");
  28.         return 0;
  29.     }
  30.     stack->data[++stack->top] = value;
  31.     return 1;
  32. }
  34. // 删除元素
  35. int Pop(SqStack *stack) {
  36.     if (IsEmpty(stack)) {
  37.         printf("栈已空，无法删除元素\n");
  38.         return 0;
  39.     }
  40.     stack->top--;
  41.     return 1;
  42. }
  44. // 取栈顶元素
  45. int GetTop(SqStack *stack) {
  46.     if (IsEmpty(stack)) {
  47.         printf("栈已空，无栈顶元素\n");
  48.         return 0;
  49.     }
  50.     return stack->data[stack->top];
  51. }
  53. // 输出栈的元素
  54. void PrintStack(SqStack *stack) {
  55.     if (IsEmpty(stack)) {
  56.         printf("栈为空\n");
  57.         return;
  58.     }
  59.     printf("栈的元素为：");
  60.     for (int i = 0; i <= stack->top; i++) {
  61.         printf("%d ", stack->data[i]);
  62.     }
  63.     printf("\n");
  64. }
  66. int main() {
  67.     SqStack stack;
  68.     InitStack(&stack);
  69.    
  70.     Push(&stack, 1);
  71.     Push(&stack, 2);
  72.     Push(&stack, 3);
  73.     Push(&stack, 4);
  75.     PrintStack(&stack);  // 输出：栈的元素为：1 2 3 4
  77.     Pop(&stack);
  78.     Pop(&stack);
  80.     PrintStack(&stack);  // 输出：栈的元素为：1 2
  82.     int top = GetTop(&stack);
  83.     printf("栈顶元素为：%d\n", top);  // 输出：栈顶元素为：2
  84.    
  85.     return 0;
  86. }
复制代码

注意，这只是一个简单的顺序栈实现，没有考虑栈的动态扩容等情况。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

FishC_GPT
发表于 2023-12-6 20:36:09 | 显示全部楼层    本楼为最佳答案   
下面是一个简单的顺序栈的实现，包含了插入、删除和取栈顶元素等基本操作：
  1. #include <stdio.h>
  2. #define MAXSIZE 100
  4. typedef struct {
  5.     int data[MAXSIZE];
  6.     int top;
  7. } SqStack;
  9. // 初始化栈
  10. void InitStack(SqStack *stack) {
  11.     stack->top = -1;  // 栈为空时，top为-1
  12. }
  14. // 判断栈是否为空
  15. int IsEmpty(SqStack *stack) {
  16.     return stack->top == -1;
  17. }
  19. // 判断栈是否已满
  20. int IsFull(SqStack *stack) {
  21.     return stack->top == MAXSIZE - 1;
  22. }
  24. // 插入元素
  25. int Push(SqStack *stack, int value) {
  26.     if (IsFull(stack)) {
  27.         printf("栈已满，无法插入元素\n");
  28.         return 0;
  29.     }
  30.     stack->data[++stack->top] = value;
  31.     return 1;
  32. }
  34. // 删除元素
  35. int Pop(SqStack *stack) {
  36.     if (IsEmpty(stack)) {
  37.         printf("栈已空，无法删除元素\n");
  38.         return 0;
  39.     }
  40.     stack->top--;
  41.     return 1;
  42. }
  44. // 取栈顶元素
  45. int GetTop(SqStack *stack) {
  46.     if (IsEmpty(stack)) {
  47.         printf("栈已空，无栈顶元素\n");
  48.         return 0;
  49.     }
  50.     return stack->data[stack->top];
  51. }
  53. // 输出栈的元素
  54. void PrintStack(SqStack *stack) {
  55.     if (IsEmpty(stack)) {
  56.         printf("栈为空\n");
  57.         return;
  58.     }
  59.     printf("栈的元素为：");
  60.     for (int i = 0; i <= stack->top; i++) {
  61.         printf("%d ", stack->data[i]);
  62.     }
  63.     printf("\n");
  64. }
  66. int main() {
  67.     SqStack stack;
  68.     InitStack(&stack);
  69.    
  70.     Push(&stack, 1);
  71.     Push(&stack, 2);
  72.     Push(&stack, 3);
  73.     Push(&stack, 4);
  75.     PrintStack(&stack);  // 输出：栈的元素为：1 2 3 4
  77.     Pop(&stack);
  78.     Pop(&stack);
  80.     PrintStack(&stack);  // 输出：栈的元素为：1 2
  82.     int top = GetTop(&stack);
  83.     printf("栈顶元素为：%d\n", top);  // 输出：栈顶元素为：2
  84.    
  85.     return 0;
  86. }
复制代码

注意，这只是一个简单的顺序栈实现，没有考虑栈的动态扩容等情况。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

tangpeng04
 楼主| 发表于 2023-12-6 20:44:02 | 显示全部楼层
FishC_GPT 发表于 2023-12-6 20:36
下面是一个简单的顺序栈的实现，包含了插入、删除和取栈顶元素等基本操作：

说明整段代码的思路和求出时间复杂度
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

FishC_GPT
发表于 2023-12-6 20:44:52 | 显示全部楼层
tangpeng04 发表于 2023-12-06 20:44
说明整段代码的思路和求出时间复杂度

这段代码实现了一个简单的顺序栈。具体来说，代码中定义了一个结构体SqStack，它包含两个成员变量：data用于存储栈中的元素值，top用于记录栈顶的位置。

代码中包含了一些基本操作：

1. InitStack函数用于初始化栈，将top设置为-1，表示栈为空。
2. IsEmpty函数判断栈是否为空，即栈顶位置是否为-1。
3. IsFull函数判断栈是否已满，即栈顶位置是否达到了最大容量。
4. Push函数用于将元素插入栈中，首先判断栈是否已满，如果满了则返回0，否则将值赋给data，top加1。
5. Pop函数用于删除栈顶元素，首先判断栈是否为空，如果是则返回0，否则将top减1。
6. GetTop函数用于取栈顶元素的值，首先判断栈是否为空，如果是则返回0，否则返回data的值。
7. PrintStack函数用于输出栈中的元素，首先判断栈是否为空，如果是则输出"栈为空"，否则通过循环将栈中的元素逐个输出。

最后，在main函数中进行了一些测试操作，先初始化栈，然后进行插入、删除和取栈顶元素等操作，并通过PrintStack函数将栈中的元素输出。

时间复杂度分析：
1. 初始化栈操作的时间复杂度为O(1)。
2. 判断栈是否为空和判断栈是否已满的操作时间复杂度均为O(1)。
3. 插入元素、删除元素和取栈顶元素的操作时间复杂度均为O(1)。
4. 输出栈中的元素操作的时间复杂度为O(n)，其中n为栈中元素的个数。
因此，整段代码的时间复杂度主要取决于输出栈中的元素操作，为O(n)。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

tangpeng04
 楼主| 发表于 2023-12-6 20:58:18 | 显示全部楼层
FishC_GPT 发表于 2023-12-6 20:44
这段代码实现了一个简单的顺序栈。具体来说，代码中定义了一个结构体SqStack，它包含两个成员变量：data ...

【实验要求】
请写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
#define StackSize 100 //假定预分配的栈空间最多为 100 个元素
typedef char DataType;//假定栈元素的数据类型为字符
代码注释详细点
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

FishC_GPT
发表于 2023-12-6 21:04:32 | 显示全部楼层
tangpeng04 发表于 2023-12-06 20:58
【实验要求】
请写一个算法判定给定的字符向量是否为 ...

下面是一个判断给定字符向量是否为回文的算法实现：
  1. ++
  2. #include <stdio.h>
  3. #include <string.h>
  5. #define StackSize 100
  7. typedef char DataType;
  9. typedef struct {
  10.     DataType data[StackSize];
  11.     int top;
  12. } SqStack;
  14. // 初始化栈
  15. void InitStack(SqStack *stack) {
  16.     stack->top = -1;
  17. }
  19. // 判断栈是否为空
  20. int IsEmpty(SqStack *stack) {
  21.     return stack->top == -1;
  22. }
  24. // 判断栈是否已满
  25. int IsFull(SqStack *stack) {
  26.     return stack->top == StackSize - 1;
  27. }
  29. // 入栈操作
  30. int Push(SqStack *stack, DataType value) {
  31.     if (IsFull(stack)) {
  32.         printf("栈已满，无法插入元素\n");
  33.         return 0;
  34.     }
  35.     stack->top++;
  36.     stack->data[stack->top] = value;
  37.     return 1;
  38. }
  40. // 出栈操作
  41. int Pop(SqStack *stack) {
  42.     if (IsEmpty(stack)) {
  43.         printf("栈已空，无法删除元素\n");
  44.         return 0;
  45.     }
  46.     stack->top--;
  47.     return 1;
  48. }
  50. // 获取栈顶元素
  51. DataType GetTop(SqStack *stack) {
  52.     if (IsEmpty(stack)) {
  53.         printf("栈已空，无栈顶元素\n");
  54.         return '\0';
  55.     }
  56.     return stack->data[stack->top];
  57. }
  59. // 判断给定字符向量是否为回文
  60. int IsPalindrome(DataType *str) {
  61.     int len = strlen(str);
  62.    
  63.     SqStack stack;
  64.     InitStack(&stack);
  65.    
  66.     // 将前一半字符入栈
  67.     for (int i = 0; i < len / 2; i++) {
  68.         Push(&stack, str[i]);
  69.     }
  70.    
  71.     // 当字符个数为奇数时，跳过中间字符
  72.     if (len % 2 != 0) {
  73.         len++;
  74.     }
  75.    
  76.     // 判断后一半字符与栈中的字符是否相等
  77.     for (int i = len / 2; i < len; i++) {
  78.         if (str[i] != GetTop(&stack)) {
  79.             return 0;
  80.         }
  81.         Pop(&stack);
  82.     }
  83.    
  84.     return 1;
  85. }
  87. int main() {
  88.     DataType str[] = "abcddcba";
  89.    
  90.     if (IsPalindrome(str)) {
  91.         printf("给定字符向量是回文\n");
  92.     } else {
  93.         printf("给定字符向量不是回文\n");
  94.     }
  95.    
  96.     return 0;
  97. }
复制代码

这段代码中定义了一个结构体`SqStack`用于表示顺序栈，包含一个字符数组`data`用于存储栈元素，以及一个整型变量`top`用于记录栈顶位置。

主要的操作包括初始化栈、判断栈是否为空、判断栈是否已满、入栈、出栈和获取栈顶元素。

`IsPalindrome`函数是判断给定字符向量是否为回文的具体实现。算法的思路是将前一半的字符依次入栈，然后与后一半的字符逐个比较，如果有不相等的则返回0，否则返回1。

在主函数中，定义了一个字符向量`str`，通过调用`IsPalindrome`函数判断给定字符向量是否为回文，并输出相应的结果。

该算法的时间复杂度为O(n)，其中n为字符向量的长度。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

tangpeng04
 楼主| 发表于 2023-12-6 21:11:38 | 显示全部楼层
FishC_GPT 发表于 2023-12-6 21:04
下面是一个判断给定字符向量是否为回文的算法实现：

字符串由用户输入，时间复杂度分析详细一点
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

FishC_GPT
发表于 2023-12-6 21:12:11 | 显示全部楼层
tangpeng04 发表于 2023-12-06 21:11
字符串由用户输入，时间复杂度分析详细一点

如果字符串长度为n，则时间复杂度分析如下：

1. 初始化栈：时间复杂度为O(1)。

2. 判断栈是否为空：时间复杂度为O(1)。

3. 判断栈是否已满：时间复杂度为O(1)。

4. 入栈操作：由于需要将前一半字符依次入栈，所以需要进行n/2次入栈操作，每次操作的时间复杂度为O(1)，因此总的时间复杂度为O(n/2)。

5. 出栈操作：由于需要将后一半字符逐个与栈中元素比较并出栈，所以需要进行n/2次出栈操作，每次操作的时间复杂度为O(1)，因此总的时间复杂度为O(n/2)。

6. 获取栈顶元素：时间复杂度为O(1)。

综上所述，算法的时间复杂度为O(n/2)，在大O表示法中可以简化为O(n)。需要注意的是，这里的时间复杂度只考虑了字符入栈和出栈的情况，没有考虑输入字符串的读取过程。如果字符串的输入过程需要读取字符到内存中，则会存在额外的时间消耗，这部分时间消耗的大小与具体的输入方式有关，不在算法本身的时间复杂度之内。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

tangpeng04
 楼主| 发表于 2023-12-6 21:17:36 | 显示全部楼层
FishC_GPT 发表于 2023-12-6 21:12
如果字符串长度为n，则时间复杂度分析如下：

1. 初始化栈：时间复杂度为O(1)。

用两个顺序栈实现一个共享栈，具体要求为：设有两个栈都采用顺序栈方式，共
享一个存储区，[0,maxsize - 1]，采用栈顶相向，迎面增长的存储方式，设计
出栈和入栈等操作算法
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-28 02:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表