数据结构-栈

2013-10-08

数据结构--栈栈是一种被限制在只能在表的一端进行插入和删除运算的线性表。（局部变量是用栈来保存的）可以进

数据结构--栈
栈是一种被限制在只能在表的一端进行插入和删除运算的线性表。（局部变量是用栈来保存的）
可以进行插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），当表中没有元素时（表长为0的栈）称为空栈。
栈的修改是按后进先出的原则进行，因此栈被称为后进先出（Last in first out）线性表。
数据结构-栈堆和栈是占一块内存的，栈向下存，堆向上存，当堆和栈相遇的时候内存就占满了存入与取出基本运算：1.初始化InitStack（S）构造一个空栈S
2.StackEmpty（S）判断栈空，若S为空栈，则返回true，否则返回false
3.StackFull（S）判断栈满，若S为满栈，则返回true，否则返回false注意：该运算只适合顺序栈的存储结构。
如果栈需要很大内存的时候可以用虚拟内存的方式，在物理内存不够的时候可以用磁盘的内存来虚拟内存使用。但会使速度变慢。
4.Push（S,x）进栈，若栈S不满，则将元素x插入到S的栈顶。
5.Pop（S）退栈，若栈S非空，则将S的栈顶元素删去，并返回该元素。
6.StackTop（S）取栈顶元素，若栈S非空，则返回栈顶元素，但栈状态不变。顺序栈定义：栈的顺序存储结构。#define LISTSIZE 100 //栈的最大容量typedef char DataType; //保存的数据类型typedef struct //C程序员的使用技巧 SeqStack并不是变量而是struct结构体的别名，因此在C中定义结构变量需要加struct 所以用这种方式可以省去struct{DataType data[ LISTSIZE ];int top; //栈顶指针}SeqStack;
初始化置栈空void InitStack(SeqStack *_S){_S-> top =-1;}
判断栈空bool StackEmpty(SeqStack* s){return s->top==-1;}
判断顺序栈满bool StackFull(SeqStack *s){return LISTSIZE -1==s-> top ; 栈顶指针指向内存-1，这样就是满了，因为栈顶指针从0开始。。}
进栈bool Push(SeqStack* s,DataType x){if(StackFull(s))return false;s->data[++s->top]=x;return true;}
顺序退栈bool Pop(SeqStack* s,DataType* data){if(StackEmpty(*s))return false;else{*data=s->data[s->top];s->top--;return true;}}

链栈栈顶指针就是链表的头指针
#define LISTSIZE 100 //栈的最大容量typedef char DataType; //保存的数据类型
typedef struct stacknode{DataType date; //内容struct stacknode *next; //指针}StackNode;
typedef StackNode* LinkStack;
初始化置栈空void InitLinkStack(LinkStack *_S){*_S=NULL;}
判断链栈空bool StackLinkEmpty(LinkStack s){return s==NULL;}
虚拟内存bool VirtualMemory(LinkStack s){FILE* stream;if(s == NULL){if((stream = fopen("memory.txt","r+")) != NULL){fseek(stream, -sizeof(StackNode), SEEK_END);fread(s,sizeof(StackNode),1,stream);while (NULL == s->next){fseek(stream, -2 * sizeof(StackNode), SEEK_CUR);fread(s,sizeof(StackNode),1,stream);}fseek(stream, -sizeof(StackNode), SEEK_CUR);s->next = NULL;fwrite(s,sizeof(StackNode),1,stream);fclose(stream);return true;}elsereturn false;}else{if((stream = fopen("memory.txt","a+")) != NULL){s->next = (LinkStack) 1;fwrite(s,sizeof(StackNode),1,stream);fclose(stream);free(s);return true;}elsereturn false;}}
链栈进栈void Push(LinkStack* s,DataType x){LinkStack p=(LinkStack)malloc(sizeof(stacknode));if(NULL==p){VirtualMemory(s);p=(LinkStack)malloc(sizeof(stacknode));}p->data=x;p->next=*s;*s=p; }
链栈退栈bool Pop(LinkStack* pStack,DataType* data){if(StackEmpty(*pStack)))return false;LinkStack temp=*pStack;*data=temp->data;*pStack=temp->next;free(temp);temp=NULL;return true;}
int _tmain(int argc, _TCHAR* argv[]){LinkStack top,bottom;InitLinkStack(&top);_getch();return 0;}

热点排行

移动开发

数据结构-栈