将颠倒的Push和Pop方法更正，并更换图片。栈是数据结构中较为简单的结构体,是一种操作收到限制的线性表.但简单不代表没用,毕竟数组很简单.但谁敢说数组没用呢?
栈栈的理论栈是一个先进后出的结构,类似于堆盘子,先放到地上的盘子最后被取走(默认只能取走一个盘子)栈其实就是操作受限的线性表,只有一个口,每一次操作时,这个口可以当出口也可以当入口.例如:水桶,注入水时,水桶的头当做入口,倒水时,水桶的头当做出口栈的图解.在图解之前,先举一个例子,让大家记住栈 : 栈其实就是吃了一顿饭,然后吐出来.
这是一个空栈,只有上面是入口和出口
放入一个元素a
接着依次放入B,C元素
取出一个元素,由栈只有一个口的特点可以知道取出了C
再次放入一个元素D
栈的可用操作
根据理论环节,可以轻易的看出:栈的基本操作只有两个:
入栈出栈而且样子长得十分像一个水桶。
但是如果栈已经放满了,就像水桶装满了水一样,不能再放水了,即不能再进行入栈操作,所以要在每次入栈前判断栈满的情况.同理,出栈之前,栈中必须有数据,不然就出现要么空指针,要么野指针.都不是我们想要的结果,所以出栈前要判断栈空,.所有一个栈一共有四个功能:
入栈(英文名:push)判(栈)满(isFull)出栈(pop)判(栈)空(isEmpty)栈的C语言定义(结构体)开篇就说了栈是操作收到限制的线性表,而众所周知的线性表主要有:1.顺序存储的数组,优点: 节省空间, 操作简单,学习成本较低,易于理解.缺点: 栈的大小一开始就声明’死’了,不利于使用.2.非顺序存储的链表.优缺点:与数组栈正好相反.
两种栈各有好处,争论是愚蠢的,学习是学不完的,所以赶快开始coding吧
数组栈数组栈,顾名思义,就是基于数组的栈,也是说把一个数组的强大的下标功能阉割掉,并且只能从一头进入(数组头明显更为方便)所以结构体为:(为了方便学习,存储类型统一使用int,但是我们一般更习惯在头文件下面给int 起一个别名,原因很简单:这样就这样实现简单的多态,需要将int类型栈改成char类型栈时,只需要改定义的别名中的类型即可)
typedef struct{ int Data[MaxSize]; // 存储元素的数组 int topIdx; //栈顶指针}SeqStack;12345栈的四个基本操作定义:
//return 0 为false,1为true(下同)// 将元素推入栈中int Push(SeqStack &L, int e){ // 栈已满 if(L.topIdx==MaxSize -1) { return 0; } // 加入栈中 L.Data[L.topIdx++] = e; // 返回自身 return e;}// 移除栈顶元素int Pop(SeqStack &L){ // 栈空 if(L.topIdx == 0) { //返回失败 return 0; } // 打印并返回栈 int val = L.Data[--L.topIdx]; printf("%d ",val); return val;}//判断栈s是否为空int isEmpty(SeqStack s){ // 如果下标在0，说明栈中无元素 if(s.topIdx != 0) { return 1; } return 0;}// 判断栈是否已栈.Status isFull(SeqStack s){ // 已满返回true(1) if(s.topIdx != MaxSize -1)//之前的定义数组的最大值的下标 { return 1; } return 0;}12345678910111213141516171819202122232425262728293031323334353637383940414243444546链表栈结构体
typedef struct LNode{ ElemType data; struct LNode * next;} LNode,*LinkList;12345两大功能(链表无需判满,判空也简单,不再单独实现)
Status Pop(LinkList L){ if(L->next == NULL) { return 0; } LinkList tem = L->next; printf("%d ",tem->data); L->next = tem->next; free(tem); return 1;}Status Push(LinkList L, ElemType e){ LinkList newNode = (LinkList) malloc(sizeof(LinkList)); newNode->data = e; newNode->next = L->next; L->next = newNode; return 1;}1234567891011121314151617181920最后写几个简单的作业(我们老师留给我们的)以及我的代码
//1、本题要求实现顺序栈，写出Push 、Pop、StackEmpty函数的实现，并用一个简单的main函数测试。
//已有类型定义typedef struct{ ElementType Data[MaxSize]; // 存储元素的数组 Position Top; //栈顶指针}SeqStack;
//函数接口定义：Status Push(SeqStack &L, ElemType e);Status Pop(SeqStack &L, ElemType &e);Status StackEmpty(SeqStack s); //判断栈s是否为空//其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针； e 是数据元素。/*** 3、进制转换。* 输入一个十进制正整数n和一个目标进制R（１ 12345678910111213141516171819我的代码实现： #include //函数接口定义：Status Push(SeqStack &L,ElemType e);Status Pop(SeqStack &L);Status StackEmpty(SeqStack s); //判断栈s是否为空Status prinStack(SeqStack &L);Status convNum(int n, int R);Status pipei();void work1();//其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针； e 是数据元素。int main(){ //work1();//第一题 //convNum(8,2);//进制转化 pipei(); return 0;}Status prinStack(SeqStack &L){ while (StackEmpty(L)) { Push(L); } return 1;}void work1(){ SeqStack L; L.Top = 0; Pop(L, 1); Pop(L, 2); Pop(L, 3); prinStack(L);}Status Pop(SeqStack &L){if(L.Top == 0) { return 0; } printf("%d ",L.Data[--L.Top]); return 1;}Status Push(SeqStack &L, ElemType e){ if(L.Top==MaxSize -1) { return 0; } L.Data[L.Top++] = e; return 1;}//判断栈s是否为空Status StackEmpty(SeqStack s){ if(s.Top != 0) { return 1; } return 0;}//3、进制转换。//输入一个十进制正整数n和一个目标进制R（１ public class LinkedStack public T push(T newEntry) { Node newNode = new Node public T pop() { T tempData = peek(); if (tempData == null) { return null; } topNode = topNode.next; return tempData; } public T peek() { if (isEmpty()) { return null; } return (T) topNode.data; } public boolean isEmpty() { return topNode == null; } public void clear() { topNode = null; // java拥有内存回收，只需要让头结点引用为空即可，GC就可以回收掉所有其他节点。 } public LinkedStack() { this.topNode = null; } private class Node public Node(T dataPortion) { this(dataPortion, null); } public Node(T data, Node next) { super(); this.data = data; this.next = next; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } }}————————————————版权声明：本文为CSDN博主「过道」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/m0_37961948/article/details/80245008 搜索 复制