栈和队列都属于线性数据的逻辑存储结构
image.png
概念
栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。
最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。
image.png
存储原理
栈既可以用数组来实现，也可以用链表来实现
栈的数组实现如下：
image.png
数组实现的栈也叫顺序栈或静态栈，栈的链表实现如下：
image.png
链表实现的栈也叫做链式栈或动态
操作
1）入栈（压栈）
入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶
image.png
image.png
2）出栈（弹栈）
出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。
image.png
完整代码
数组实现
package com.david.line.stack;
/**
* 数组实现
*/
public class ArrayStack {
private int[] nums; // 数组
private int count; // 栈中元素个数
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.nums = new int[n];
this.count = 0;
}
// 入栈操作
public boolean push(int n) {
// 数组空间不够了，直接返回false，入栈失败。 没有扩容
// nums.len*2 arraycopy
if (count >= nums.length) return false;
// 将item放到下标为count的位置，并且count加一
nums[count] = n;
count++;
return true;
}
// 出栈操作
public int pop() {
// 栈为空，则直接返回0
if (count == 0)
return 0;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
int n = nums[count-1];
count--;
return n;
}
public static void main(String[] args) {
ArrayStack as=new ArrayStack(8);
as.push(3);
as.push(5);
as.push(1);
as.push(4);
System.out.println(as.pop());
System.out.println(as.pop());
System.out.println(as.pop());
System.out.println(as.pop());
}
}
链表实现
package com.david.line.stack;
/**
* 链表节点
*/
public class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
}
}
/**
* 链表实现
*/
public class LinedStack {
int size;
Node head;
/**
* 初始化
*/
public LineStack() {
head = null;
size = 0;
}
/**
* 入栈
*
* @param node
*/
public void push(Node node) {
//head
if (size == 0) {
head = node;
}
//非head
else {
node.next = head;
head = node;
}
size++;
}
/**
* 出栈
*
* @param node
*/
public Node pop() {
if (size > 0) {
Node oldHead = head;
head = head.next;
size--;
return oldHead;
} else {
return null;
}
}
public static void main(String[] args) {
Node n1 = new Node(3);
Node n2 = new Node(5);
Node n3 = new Node(1);
Node n4 = new Node(4);
LinedStack ls = new LinedStack();
ls.push(n1);
ls.psuh(n2);
ls.push(n3);
ls.push(n4);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
}
}
时间复杂度
入栈和出栈的时间复杂度都是O(1)。
支持动态扩容的顺序栈。
当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组，通过前面学过的知识，可以得知入栈的时间复杂度是O(n)。
应用
1）函数调用
每进入一个函数，就会将临时变量作为一个栈入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。
2）浏览器的后退功能
我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了
网友评论