2022/8/10 说明: 评论区有很多反对的声音, 有说我写错的, 有说我用了C++的, 大家可以自己多尝试下, 截至2022/8/10的反馈我都看过了, 目前都没问题.
2019/5/22 更新，将颠倒的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;
栈的四个基本操作定义:
//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;
}
链表栈
结构体
typedef struct LNode
{
ElemType data;
struct LNode * next;
} LNode,*LinkList;
两大功能(链表无需判满,判空也简单,不再单独实现)
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;
}
最后写几个简单的作业(我们老师留给我们的)以及我的代码
//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（１ */ 我的代码实现： #include #include #define MaxSize 100 typedef int Status; typedef int ElemType; typedef int Position; //1、本题要求实现顺序栈，写出Push 、Pop、StackEmpty函数的实现，并用一个简单的main函数测试。 //已有类型定义 typedef struct { ElemType Data[MaxSize]; // 存储元素的数组 Position Top; //栈顶指针 } SeqStack; //函数接口定义： 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（１ Status convNum(int n, int R) { //声明栈 SeqStack L; L.Top = 0; while (n!=0) { //将每次产生的余数防入栈低 Pop(L, n%R); n/=R; } prinStack(L); return 1; } 以下附上Java 代码实现的栈 public class LinkedStack private Node topNode; public T push(T newEntry) { Node newNode = new Node topNode = newNode; T tempData = peek(); return tempData; } 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 private T data; private Node next; 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; } } }