前言
数据结构从大的方向上分,可以分为逻辑结构和物理结构。逻辑结构是抽象的概念,它依赖于物理结构而存在。
物理结构可划分为:顺序存储结构与链式存储结构。
- 顺序存储结构:把数据元素存放在地址连续存储单元里,其数据间的逻辑关系和物理关系是一致的。例如
数组
。 - 链式存储结构:其中逻辑关系和物理关系没有多大的关系,因为其中的数据元素会产生变化。链式存储结构是把数据元素存放在任意的存储单元里,存储单元可以是连续的也可以是不连续的。当然也比顺序存储结构更加灵活。例如
链表
。
逻辑结构可划分为:线性结构与非线性结构。
- 线性结构:顾名思义,一条线性的结构,元素间的关系就是一对一的。例如
线性表
、栈
、队列
。 - 非线性结构:包括树形结构、图形结构等。例如
树
、图
。
栈的基本知识
栈,stack,又称堆栈,是一种线性结构。与数组相比,访问它的元素是受限制的:栈只能在同一端(栈顶)进行操作,且只允许访问一个数据项,即最后插入的数据项。栈中的元素只能先入后出
(First In Last Out,简称FILO),最先进入的元素存放的位置叫栈底
,最后进入的元素存放的位置叫栈顶
。
生活中也不缺可以体现出栈的特点的设计/例子,例如:老师批改一叠作业,正常情况下都是先拿起最上面的一本,处理完这本之后,再去批改下一本,从上到下,直到被压在最后的一本,但是最后一本是最开始放的。例如:兵乓球圆筒的一端封闭,另一端开口。往圆筒放入兵乓球,先放入的在圆筒底部,后放入的靠近圆筒入口。在圆筒直径条件限制下,只能按放入顺序相反的顺序取球。
栈的基本操作
- 入栈(push),就是把一个新元素放入栈中,只允许从栈顶一侧放入,下一个新元素放入的位置将成为新的栈顶。
- 出栈(pop),就是把一个元素从栈中弹出,只有栈顶的元素才允许弹出,出栈元素的前一个元素将成为新的栈顶。
- peek(),查看栈顶部的对象,但不对栈做任何改动。
- size(),返回栈内元素的大小。
- isEmpty(),测试栈是否为空,返回布尔值。
- isFull(),测试栈是否为满,返回布尔值。
栈的实现
栈既可以用数组来实现,也可以用链表来实现。注意,如果用数组来实现,需要先规定栈的大小;如果用链表来实现,则不需要先规定栈的容量。
class ArrayStack {
// 最大长度
private int maxSize;
// 栈顶索引
private int top;
// 用于存储元素的数组
private int[] stackArray;
public ArrayStack(int val){
maxSize = val;
stackArray = new int[maxSize];
top = -1;
}
// 栈空
public boolean isEmpty(){
return (top == -1);
}
// 栈满
public boolean isFull(){
return (top == maxSize - 1);
}
// 入栈
public void push(int x){
if (isFull()){
throw new RuntimeException("栈已满!");
}
stackArray[++top] = x;
}
// 出栈
public int pop(){
if (isEmpty()){
throw new RuntimeException("栈是空的!");
}
return stackArray[top--];
}
// 查看栈顶
public int peek(){
return stackArray[top];
}
// 长度
public int size(){
return top + 1;
}
// 遍历输出:输出顺序与输入顺序相反
public void show(){
if (isEmpty()){
System.out.println("栈是空的!");
}else {
int temp = top;
while (temp != -1) {
System.out.println(stackArray[temp]);
System.out.print(" ");
temp--;
}
}
}
}
class LinkStack<T>{
// 栈顶
private Node top;
// 长度
private int size = 0;
// 节点
private class Node{
// 数据
private T data;
// next指针
private Node next;
public Node(T data){
this.data = data;
}
}
// 创建
public LinkStack(){
top = new Node(null);
}
// 栈空,链表没有定义存储限制,所以没有栈满
public boolean isEmpty(){
if (top.next == null){
return true;
}
return false;
}
// 入栈
public void push(T data){
if (isEmpty()){
top.next = new Node(data);
}else{
Node newNode = new Node(data);
newNode.next = top.next;
top.next = newNode;
}
size++;
}
// 出栈
public T pop(){
if (isEmpty()){
System.out.println("栈是空的!");
return null;
}else {
T val = top.next.data;
top.next = top.next.next;
size--;
return val;
}
}
// 获取栈顶元素
public T peek(){
if (isEmpty()){
return null;
}else{
return top.next.data;
}
}
// 栈的长度
public int size(){
return size;
}
// 输出
public void show(){
Node temp = top;
if (isEmpty()){
System.out.println("栈是空的!");
}else{
while(temp.next != null){
temp = temp.next;
System.out.print(temp.data + " ");
}
}
}
}
栈的应用及效率
栈是一个重要的数据结构,其特性简而言之就是“先进后出”,可以用它辅助遍历二叉树的节点,也可以用它辅助查找图的顶点。
在计算机中,大部分微处理器运用基于栈的体系结构。在windows等大部分操作系统中,每个运行中的二进制程序都配有一个调用栈(Call Stack)和执行栈(Execution Stack)。当调用一个方法时,把它的返回地址和参数压入栈,方法结束返回时,那些数据就出栈,栈操作就嵌入在微处理器中。
- 用栈实现单词逆序;
- 中缀表达式求值;
- 实现十进制数和其他n进制数的转换;
- 用于解析某种类型的文本串,实现分隔符匹配;
- ......
栈操作所耗时间不依赖于栈中数据项的个数,因为入栈、出栈都是只影响到最后一个元素,不涉及比较和移动操作,所以无论是数组实现还是链表实现的,数据项入栈、出栈的时间复杂度都是常数级O(1)。
本文链接:https://newabug.top/archives/4.html