入栈（栈及其操作）

栈

入栈（栈及其操作）

特点

根据存储结构不同分为顺序栈与链栈, 顺序栈：顺序存储；链栈：链式存储是限定在表尾进行插入和删除的线性表表尾端为栈顶，表头端为栈底修改遵循后进先出

I. 分类--顺序栈

操作

(插入图片)

1.存储结构

#define MAXSIZE 100typedef struct{ SElemType *base; //栈底指针，指向栈底元素 SElemType *top; //栈顶指针 int stacksize; //栈可用的最大容量}SqStack;

2.初始化

步骤：a. 为顺序栈分配一个最大容量MAXZISE的数组空间b. 栈顶指针top初始化为栈底指针base，表示空栈c. stacksize设为栈的最大容量MAXSIZE

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.入栈

步骤：a. 判断栈容量是否已满b. 将插入的元素压入栈顶，栈顶指针加1

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.出栈

步骤:a. 判断栈是否为空b. 先将栈顶指针减1，再将要出栈的元素赋给栈顶指针所指的值,栈顶元素出栈

Status Pop(SqStack &S, SElemType &e){ if(S.top==S.base) return ERROR; S.top--; e = *S.top; //e = *--S.top; return OK;}

5.取栈顶元素

步骤：a. 若非空，返回栈顶指针的值，栈顶指针保持不变

Status GetTop(SqStack &S){ if(S.top!=S.base) { return *(S.top-1); } return OK;}

6.完整实现（java）

II. 分类--链栈

1.存储结构

typedef struct StackNode{ ElemType data; struct StackNode *next;}StackNode, *LinkStack;

2.初始化

步骤：a. 构造一个空栈，不用设头结点，直接将栈顶指针置空

Status InitStack(LinkStack &S){ S = NULL; return 0;}

3.入栈

步骤：a. 为入栈元素分配空间，并用新指针结点指向b. 新结点值设为ec. 新结点插入栈顶，修改栈顶指针为p

Status Push(LinkStack &S, ElemType e){ LinkStack p = new StackNode; //生成新结点 p->data = e; p->next = S; //插到栈顶 S = p; //修改栈顶指针为p return OK;}

4.出栈

步骤：a. 判断是否为空b. 将栈顶元素赋给e，临时保存栈顶元素空间，以备释放c. 修改栈顶指针，指向新元素d. 释放原栈顶元素空间

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.取栈顶元素

Status GetTop(LinkStack &S){ if(S!=NULL) return S->data;}

6.完整实现（java）

//链栈类代码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(); }} //链栈测试代码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才是指向栈顶元素链栈：指向栈顶实在的元素入栈顺序栈需要判断栈是否满，链栈不用出栈都需要判断栈是否空，链栈需要释放栈元素的空间