栈 特点
根据存储结构不同分为顺序栈与链栈, 顺序栈：顺序存储 ； 链栈：链式存储
是限定在表尾进行插入和删除的线性表
表尾端为栈顶，表头端为栈底
修改遵循后进先出
I. 分类–顺序栈 操作 (插入图片)
1.存储结构 1 2 3 4 5 6 #define MAXSIZE 100 typedef struct{ SElemType *base; //栈底指针，指向栈底元素 SElemType *top; //栈顶指针 int stacksize; //栈可用的最大容量 }SqStack;
2.初始化 步骤：MAXZISE 的数组空间 top 初始化为栈底指针base ，表示空栈 MAXSIZE
1 2 3 4 5 6 7 8 Status InitStack(SqStack &S) { S.base = new SElemType[MAXSIZE]; //动态分配最大容量为MAXSIZE的数组 if(!S.base) exit(EOVERFLOW); S.top = S.base; //空栈 S.stacksize = MAXSIZE;; return OK; }
3.入栈 步骤：
1 2 3 4 5 6 7 8 9 Status Push(SqStack &S, SElemType e) { if(S.top-S.base==S.stacksize) return ERROR; // *S.top++ = e; *S.top = e; S.top++; return OK; }
4.出栈 步骤:
1 2 3 4 5 6 7 8 9 Status Pop(SqStack &S, SElemType &e) { if(S.top==S.base) return ERROR; S.top--; e = *S.top; //e = *--S.top; return OK; }
5.取栈顶元素 步骤：栈顶指针保持不变
1 2 3 4 5 6 7 8 Status GetTop(SqStack &S) { if(S.top!=S.base) { return *(S.top-1); } return OK; }
6.完整实现（java） II. 分类–链栈 1.存储结构 1 2 3 4 typedef struct StackNode{ ElemType data; struct StackNode *next; }StackNode, *LinkStack;
2.初始化 步骤：
1 2 3 4 5 Status InitStack(LinkStack &S) { S = NULL; return 0; }
3.入栈 步骤：
1 2 3 4 5 6 7 8 9 Status Push(LinkStack &S, ElemType e){ LinkStack p = new StackNode; //生成新结点 p->data = e; p->next = S; //插到栈顶 S = p; //修改栈顶指针为p return OK; }
4.出栈 步骤：
1 2 3 4 5 6 7 8 9 Status Pop(LinkStack &S, ElemType &e){ if(S==NULL) return ERROR; LinkStack p = new StackNode; e = S->data; p = S; //p临时保存栈顶元素空间，以备释放 S = S->next; delete p; return OK;
5.取栈顶元素 1 2 3 4 5 Status GetTop(LinkStack &S) { if(S!=NULL) return S->data; }
6.完整实现（java） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 //链栈类代码 package stack; import java.lang.NullPointerException; public class LinkStack { private Element base; private Element top; class Element{ public Object data; public Element next; } //初始化 void initStack(){ top = new Element(); base = new Element(); top.data = null; top.next = null; base.data = null; base.next = null; } //入栈 void push(Object o){ Element e = new Element(); e.data = o; //empty stack if(top.next==base){ e.next = base; top.next = e; }else{ e.next = top.next; top.next = e; } } //出栈 void pop(){ if(top.next==base){ System.out.println("栈中没有元素"); }else { System.out.println("出栈：" + top.next.data); top.next = top.next.next; } } //print void print(){ System.out.println("打印栈：\n"); Element temp = top; while(temp.next!=base){ System.out.println(temp.next.data + "\t"); temp = temp.next; } System.out.println(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 //链栈测试代码 package stack; public class LinkStackMain { public static void main(String[] args){ LinkStack ls = new LinkStack(); ls.initStack(); ls.push(1); ls.push(2); ls.push(3); ls.push(4); ls.print(); ls.pop(); ls.pop(); ls.print(); ls.pop(); ls.pop(); ls.print(); ls.pop(); } }
顺序栈与链栈的区别
存储结构
顺序栈：顺序存储
链栈： 链式存储
链栈通常不会出现栈满情况，链栈动态分配内存，不浪费内存；顺序栈使用固定大小数组保存数据，容易浪费内存
top指针区别
顺序栈：指向栈顶的空白元素处，top-1才是指向栈顶元素
链栈：指向栈顶实在的元素
入栈
出栈
