当前位置: article > 正文

栈的实现——链表和数组_c++栈的实现用单链表和数组哪个更好

作者：很楠不爱3 | 2024-05-28 03:36:47

踩

c++栈的实现用单链表和数组哪个更好

C语言（打印函数采用的c++）：

栈的链表实现—— 栈的初始化（创建||清空）、入栈、出栈（获取栈顶元素）
栈的数组实现——初始化、入栈、出栈、清空栈

参考资料：《数据结构与算法分析——C语言描述》 P46

一. 栈的链表实现

StackLinkList.cpp

[cpp]view plaincopy 
   
 /* 
 功能：栈的链表实现: 栈的初始化（创建||清空）、入栈、出栈（获取栈顶元素） 
 Date: 2015/01/23 
 Author : quinn 
 */  
 #include <iostream>  
 #include <stdlib.h>  
 using namespace std;  
 typedef int Item;  
 typedef struct Node Node;  
 typedef Node* Stack;  
 struct Node  
 {  
     Item item;  
     Node* next;  
 };  
 void StackPop(Stack s);  
 Stack StackInit(Stack s) //创建或清空（初始化）  
 {  
     if (s == NULL) //创建  
     {  
         s = (Stack)malloc(sizeof(*s));  
         s->next = NULL;  
     }  
     else //清空  
         while(s->next != NULL)  
             StackPop(s);  
     cout << "初始化成功！" <<endl;  
     return s;  
 }  
 void StackPush(Stack s, Item item) //入栈  
 {  
     Node* tmpNode = (Node*)malloc(sizeof(*tmpNode));  
     tmpNode->item = item;  
     tmpNode->next = s->next;  
     s->next = tmpNode;  
     cout << "PUSH: " << item <<endl;  
 }  
 Item StackPopAndTop(Stack s) //出栈并返回栈顶元素值  
 {  
     if (s->next == NULL)  
     {  
         cout << "空栈，POPAndTop失败" <<endl;  
         return -1; //返回-1作警告  
     }  
     else  
     {  
         Node* firstNode = s->next;  
         s->next = s->next->next;  
         return firstNode->item;  
     }  
 }  
 void StackPop(Stack s) //出栈  
 {  
     if (s->next == NULL)  
     {  
         cout << "空栈，POP失败" <<endl;  
     }  
     else  
     {  
         Node* firstNode = s->next;  
         s->next = s->next->next;  
         free(firstNode);  
     }  
 }  
 Item StackTop(Stack s) //仅获取栈顶元素  
 {  
     if (s->next == NULL)  
     {  
         cout << "空栈，获取栈顶元素失败" <<endl;  
     }  
     return (s->next)->item;  
 }  
   
 int main()  
 {  
     Stack s = NULL;  
     s = StackInit(s);  
     for(int i = 0; i < 10; i++)  
         StackPush(s, i);  
     for(int i = 0; i < 5; i++)  
         cout << StackPopAndTop(s) <<endl;  
     StackInit(s);  
     cout << StackPopAndTop(s) <<endl;  
     system("pause");  
     return 0;  
 }  

运行结果：

二. 栈的数组实现

StackArray.cpp

[cpp]view plaincopy 
   
 /* 
 功能：栈的数组实现——初始化、入栈、出栈、清空栈 
 注： 定义栈为空时，栈顶index为 -1；栈满时，栈顶index为栈的长度-1 
 Date：2015/01/23 
 Author ： quinn 
 */  
 #include <iostream>  
 #include "item.h"  
 #define STACK_SIZE 10 //认为设定栈的长度为10  
 #define FULL_STACK (STACK_SIZE - 1)  
 #define EMPTY_STACK (-1)  
 using namespace std;  
 typedef struct stack stack;  
 typedef int Item;  
 struct stack  
 {  
     Item *stackItem;  
     int stackTop;  
 };  
   
 void Error(const char* str) //异常时输出提示  
 {  
     cout << "Error: " << str << endl;  
 }  
 int IsFull(stack* s) //判断是否栈满  
 {  
     if (s->stackTop == FULL_STACK)  
         return 1;  
     else  
         return 0;  
 }  
 int IsEmpty(stack* s) //判断是否空栈  
 {  
     if (s->stackTop == EMPTY_STACK)  
         return 1;  
     else  
         return 0;  
 }  
   
 stack* StackInit( stack* s, int maxN) //初始化栈空间  
 {  
      s->stackTop = -1; //空栈初始化 Top = -1  
      s->stackItem = (Item*)malloc(maxN * sizeof(Item)); //分配栈空间  
      return s;  
 }  
 void StackMakeEmpty(stack* s) //清空栈  
 {  
     if (!IsEmpty(s))  
         s->stackTop = EMPTY_STACK;  
 }  
   
 void StackPush(stack* s, Item item) //入栈  
 {  
     if (!IsFull(s))  
     {  
         s->stackItem[++(s->stackTop)] = item;  
         cout << "PUSH: " << item <<endl;  
     }  
     else  
         Error("栈已满，push失败");  
 }  
 Item StackPop(stack *s) //出栈  
 {  
     if (!IsEmpty(s))  
     {  
         return s->stackItem[(s->stackTop)--];  
     }  
     else  
         Error("空栈，pop失败");  
 }  
   
 int main()  
 {  
     stack *s = (stack*)malloc(sizeof(*s));  
     StackInit(s, STACK_SIZE);  
     for (int i = 0; i < 11; i++)  
     {  
         StackPush(s, i);  
     }  
     cout << "POP: " << StackPop(s) << endl;  
     cout << "POP: " << StackPop(s) << endl;  
     StackPush(s, 20);  
     cout << "POP: " << StackPop(s) << endl;  
     StackMakeEmpty(s);  
     StackPop(s);  
     StackPush(s, 30);  
     cout << "POP: " << StackPop(s) << endl;  
     system("pause");  
     return 0;  
 }  

运行结果：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/635447