词条 | 栈 |
释义 | “地崩山摧壮士死,然后天梯石栈(zhàn)相钩连”的蜀道。石栈就是石梯的意思。 计算机 基本概念栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为后进先出表。 栈可以用来在函数调用的时候存储断点,做递归时要用到栈! 以上定义是在经典计算机科学中的解释。 在计算机系统中,栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中,也可以将数据从栈顶弹出。在i386机器中,栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小,弹出的操作使得栈顶的地址增大。 栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息,这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息: 1. 函数的返回地址和参数 2. 临时变量:包括函数的非静态局部变量以及编译器自动生成的其他临时变量。 基本算法1.进栈(PUSH)算法 ①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作②); ②置TOP=TOP+1(栈指针加1,指向进栈地址); ③S(TOP)=X,结束(X为新进栈的元素); 2.退栈(POP)算法 ①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检查是否已为空栈, 空则下溢;不空则作②); ②X=S(TOP),(退栈后的元素赋给X): ③TOP=TOP-1,结束(栈指针减1,指向栈顶)。 实现栈分顺序栈和链式栈,下面程序介绍了顺序栈的实现。 在pascal下的实现1.数组型 Const m=栈表目数的上限; Type stack=array[1..m] of stype; {栈类型} Var s:stack;{栈} top:integer; 2.记录型 const m=栈表目数的上限; type stack=record elem: array[1..m] of elemtp; top:0..m; {栈顶指针} end; Var s:stack;{栈} 在C/C++中栈的一些基本操作: C++代码:#include <iostream> class SqStack { private: enum {MaxSize=100}; int data[MaxSize]; int top; public: SqStack(); ~SqStack(); bool isEmpty(); void pushInt(int x); int popInt(); int getTop(); void display(); }; SqStack::SqStack() { top=-1; } SqStack::~SqStack(){} bool SqStack::isEmpty() //判断栈为空 { return (top==-1); } void SqStack::pushInt(int x) //元素进栈 { if(top==MaxSize-1) { std::cout<<"栈上溢出!"<<std::endl; } else { ++top; data[top]=x; } } int SqStack::popInt() //退栈 { int tmp=0; if(top==-1) { std::cout<<"栈已空!"<<std::endl; } else { tmp=data[top--]; } return tmp; } int SqStack::getTop() //获得栈顶元素 { int tmp=0; if(top==-1) { std::cout<<"栈空!"<<std::endl; } else { tmp=data[top]; } return tmp; } void SqStack::display() //打印栈里元素 { std::cout<<"栈中元素:"<<std::endl; for(int index=top;index>=0;--index) { std::cout<<data[index]<<std::endl; } } int main() { SqStack st; std::cout<<"栈空:"<<st.isEmpty()<<std::endl; for(int i=1;i<10;i++) { st.pushInt(i); } st.display(); std::cout<<"退一次栈"<<std::endl; st.popInt(); std::cout<<"栈顶元素: "<<st.getTop()<<std::endl; st.popInt(); st.display(); return 0; } C代码#include<stdio.h> #include<malloc.h> #define DataType int #define MAXSIZE 1024 typedef struct { DataType data[MAXSIZE]; int top; }SeqStack; SeqStack *Init_SeqStack()//栈初始化 { SeqStack *s; s=(SeqStack *)malloc(sizeof(SeqStack)); if(!s) { printf("空间不足\"); return NULL; } else { s->top=-1; return s; } } int Empty_SeqStack(SeqStack *s)//判栈空 { if(s->top==-1) return 1; else return 0; } int Push_SeqStack(SeqStack *s,DataType x)//入栈 { if(s->top==MAXSIZE-1) return 0;//栈满不能入栈 else { s->top++; s->data[s->top]=x; return 1; } } int Pop_SeqStack(SeqStack *s,DataType *x)//出栈 { if(Empty_SeqStack(s)) return 0;//栈空不能出栈 else { *x=s->data[s->top]; s->top--; return 1; }//栈顶元素存入*x,返回 } DataType Top_SeqStack(SeqStack *s)//取栈顶元素 { if(Empty_SeqStack(s)) return 0;//栈空 else return s->data[s->top]; } int Print_SeqStack(SeqStack *s) { int i; printf("当前栈中的元素:\"); for(i=s->top;i>=0;i--) printf("%3d",s->data[i]); printf("\"); return 0; } int main() { SeqStack *L; int n,num,m; int i; L=Init_SeqStack(); printf("初始化完成\"); printf("栈空:%d\",Empty_SeqStack(L)); printf("请输入入栈元素个数:\"); scanf("%d",&n); printf("请输入要入栈的%d个元素:\",n); for(i=0;i<n;i++) { scanf("%d",&num); Push_SeqStack(L,num); } Print_SeqStack(L); printf("栈顶元素:%d\",Top_SeqStack(L)); printf("请输入要出栈的元素个数(不能超过%d个):\",n); scanf("%d",&n); printf("依次出栈的%d个元素:\",n); for(i=0;i<n;i++) { Pop_SeqStack(L,&m); printf("%3d",m); } printf("\"); Print_SeqStack(L); printf("栈顶元素:%d\",Top_SeqStack(L)); return 0; } 关于汉字“栈”栈 郑码:FHM,U:6808,GBK:D5BB 笔画数:9,部首:木,笔顺编号:123411534 inn; shed; warehouse; 栈 (1) 栈 zhàn (2) (形声。从木,戋(jiān)声。本义:牲口棚) (3) 同本义 [shed] 栈,棚也。――《说文》。按,栅者,竖编之,棚者,横编之。 (4) 又如:皂栈(马房中的栅栏和方格木条) (5) 古代用竹木条横排编成车箱的轻便车子 [bamboo or wood cart] (6) 又如:栈车(栈舆。古代用竹木条编成车箱的车,不蒙皮革);栈轸(指编排竹木条而成的车箱,不蒙皮革);栈舆马(陋车劣马。后用为居官清廉俭朴的典实) (7) 栈道 [plank road built along the face of a cliff] 栈道千里,通于蜀汉。――《战国策·秦策》 复从峡度栈以上。――《徐霞客游记·游黄山记》 (8) 又如:栈山(以栈为道跋越高山);栈山航海(谓跋山涉水,逾越险阻);栈谷(架设栈道以跨越山谷);栈径(栈道);栈云(谓栈道高与云连);栈路(栈道) (9) 留宿客商或储存货物的房屋 [warehouse;storehouse]。如:栈使(客栈的仆役);栈伙(旧时称店员或旅店的伙计);栈租(租借栈房的钱);栈货(指已运到并进入仓库的货物);栈阁(存放东西的屋子);栈师(旧称店堂、仓库里工作的职员);羊栈;栈豆(马记豆料);栈驹(饲养于厩中的马驹) (10) 姓 栈 (1) 栈 zhàn (2) [在栈内] 加料精养 [fee] (3) 又如:栈羊(在圈内加料精养的肥羊);栈鹿(在栈内加料精养的鹿) 栈道 zhàndào [a plank road built along the face of a cliff] 在悬崖绝壁上凿孔架木而成的窄路 栈房 zhànfáng (1) [warehouse; storehouse]∶仓库,货栈 (2) [inn][方]∶客栈;旅店 栈桥 zhànqiáo [landing stage] 形状像桥的建筑物,建在车站、港口、矿山或工厂,用于装卸货物或上下旅客 栈 (栈) zhàn ㄓㄢˋ (1) 竹木编成的遮蔽物或其他东西:马~(养马的竹木棚)。~车(古代用竹木编成棚的车子)。 (2) 通过,越过:~山航海。 引申字义 栈:罗嗦、强势。 《水浒传》第十六回:“……不是我口栈,量你是个遭死的军人,相公可怜抬举你做个提辖,比得芥菜子大小的官职,直得恁地逞能……” 1.a warehouse; a storehouse 2a shed; a pen |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。