”后进后出“栈

2024-06-04 22:58

文章标签 后出后进

本文主要是介绍”后进后出“栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

栈的定义：

栈是限定仅在表尾进行插入或删除操作的线性表，因此表尾端成为栈顶，相应的，表头端成为栈底，不含有任何元素的栈称为空栈。

栈的修改遵循后进先出的原则，因此栈又称为后进先出的线性表，简称LIFO结构。

栈一般采用数组作为其存储结构，这样做可以避免使用指针，简化程序，当然数组需要预先声明静态数据区的大小，但这不是问题，因为即便是频繁进出入栈操作，任何时刻栈元素的实际个数也不会很多，为栈预留一个足够大但又不占用太多空间并不是很困难，如果不能做到这一点，那么节省内存的方法就是使用链表存储栈。

栈的基本运算：

[cpp]  view plain copy  
 print ? 
 #include<iostream>  
 #include<cstdio>  
 using namespace std;  
 typedef struct Stacknode//定义链式栈的结构体  
 {  
     int data;//数据域  
     Stacknode *next;//下一节点的指针域  
 }Stacknode,*Stack;  
 //初始化一个链式栈（返回一个链式栈的头节点）  
 Stack InitStack()  
 {  
     Stack stack=(Stack)malloc(sizeof(Stacknode));  
     stack->next=NULL;  
     return stack;  
 }  
 //入栈  
 void Push(Stack stack,int newData)  
 {  
     //判断是否为空  
     if(stack==NULL)  
     {  
         printf("栈未初始化，请初始化以后再使用\n");  
         return;  
     }  
     //找到最后一个节点  
    Stacknode *lastnode=stack;  
    while(lastnode->next)  
     {  
     lastnode=lastnode->next;  
     }  
    lastnode->next=(Stacknode*)malloc(sizeof(Stacknode*));  
    lastnode->next->data=newData;  
    lastnode->next->next=NULL;  
    printf("入栈成功！\n");  
 }  
 //出栈  
 int Pop(Stack stack)  
 {  
     //判断栈是否为空  
     if(!stack->next)  
     {  
         printf("栈为空，无法出栈\n");  
         return -1;//-1只是一个自定义的错误代码  
     }  
     //找到最后一个节点的钱一个节点  
     //tempNode:最后一个节点的前一个节点  
     Stacknode *tempNode=stack;  
     while(tempNode->next->next)  
     {  
         tempNode=tempNode->next;  
     }  
     int data=tempNode->next->data;  
     free(tempNode->next);  
     tempNode->next=NULL;  
     return data;  
 }  
   
 int main()  
 {  
     Stack stack=InitStack();  
     Push(stack,3);//3进栈  
     Push(stack,4);//4进栈  
     Push(stack,5);//5进栈  
     printf("%d\n",Pop(stack));  
     printf("%d\n",Pop(stack));  
     printf("%d\n",Pop(stack));  
     printf("%d\n",Pop(stack));//第4次出栈，应该出错  
     return 0;  
 }  
  
 
  