什么是栈
百度百科
上,栈是这么定义的:
- 栈(stack)又名
,它是一种堆栈
的运算受限
。限定仅在线性表
和表尾进行插入
操作的线性表。这一端被称为删除
,相对地,把另一端称为栈顶
。向一个栈插入新元素又称作栈底
,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作进栈、入栈或压栈
,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。出栈或退栈
稍微介绍一下关键名词:
- 运算受限:也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端就行插入和删除。同样,队列也是运算受限,只能在两天操作。
- 线性表:栈也是一种线性表,前面详细介绍过线性表,它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分
,他们的物理存储结构不同。但是逻辑结构(数组和链表实现
)相同。实现的目的
- 栈顶栈底: 这个描述是偏向于逻辑上的内容,因为大家知道
更容易,而数组在末尾插入删除
更容易。所以数组可以用末尾做栈顶,而链表可以头做栈顶。单链表通常在头插入删除
栈的应用:
- 栈的应用广泛,比如你的程序执行查看调用堆栈、加减运算、甚至在搜索算法中dfs,替代递归等等。所以栈也是必须掌握的一门数据结构。很多规范也是栈,比如上图放书拿书一样!
设计与介绍
这里我们介绍数组实现的栈和链表实现的栈。
数组实现
结构设计
- 对于数组来说,我们模拟栈的过程很简单,因为栈是
,我们很容易在数组的末尾进行插入和删除。所以我们选定后进先出
。所以对于一个栈所需要的基础元素是 一个data数组和一个top(int)表示栈顶位置。末尾为栈顶
- 那么初始话以及构造的函数代码为:
private T data[];
private int top;
public seqStack() {
data=(T[]) new Object[10];
top=-1;
}
public seqStack(int maxsize)
{
data=(T[]) new Object[maxsize];
top=-1;
}
push插入
栈的核心操作之一push:入栈操作。
- 如果top<数组长度-1。入栈。
top++;a[top]=value;
- 如果top==数组长度-1;栈满。
pop弹出并返回首位
- 如果top>=0,栈不为空,可以弹出。
return data[top--];
- 如下图,本来栈为1,2,3,4(栈顶),执行pop操作。top变为3的位置并且返回4;
其他操作
- 其他例如peek操作时返回栈顶
.所以只需满足题意时候不弹出
即可。return data[top]
链表实现
有数组实现,链表当然也能实现。对于栈的运算。大致可以分为两种思路:
- 像数组那样在尾部插入删除。大家都知道链表效率
。而查询到尾部效率很低。而我们就算用了尾指针,可以解决尾部插入效率。但是依然无法解决删除效率(删除需要找到前节点).还需要双向链表。前面虽然详细介绍过双向链表,但是这样未免太复杂!低在查询
- 所以我们采用带头节点的单链表在头部插入删除,把头部当中栈顶,这样精了很多。插入直接在头节点后插入。而删除也直接删除头节点后第一个元素即可。
长话短说,短话不说
。直接上代码就懂。 链表的节点:
static class node<T>
{
T data;
node next;
public node() {
}
public node(T value)
{
this.data=value;
}
}
基本结构:
public class lisStack <T>{
int length;
node<T> head;//头节点
public lisStack() {
head=new node<>();
length=0;
}
//其他方法
}
与单链表头插入一致,如果不太了解请先看笔者队线性表介绍的。
和数组形成的栈有个
区别
。就是理论上栈没有大小限制(不突破内存系统限制)。不需要考虑是否越界。
- 节点
入栈team
- 空链表入栈
head.next=team;
- 非空入栈
team.next=head.next;head.next=team;
pop弹出
与单链表头删除一致,如果不太了解请先看笔者队线性表介绍的。
和数组同样需要判断是否为空。
-
出栈team
- head指向team后驱节点。
。如果为1个节点,team.next=null.执行完毕head.next=null。变为空,满足条件。不需要考虑链表是否为1个节点
-
.所以只需判空满足题意时候不弹出
即可。而length你可以遍历链表返回长度,也可以动态设置(本文采取)跟随栈长变化。其他操作直接看api。return head.next.data
实现代码
package 队栈;
public class seqStack<T> {
private T data[];
private int top;
public seqStack() {
data=(T[]) new Object[10];
top=-1;
}
public seqStack(int maxsize)
{
data=(T[]) new Object[maxsize];
top=-1;
}
boolean isEmpty()
{
return top==-1;
}
int length()
{
return top+1;
}
boolean push(T value) throws Exception//压入栈
{
if(top+1>data.length-1)
{
throw new Exception("栈已满");
}
else {
data[++top]=value;
return true;
}
}
T peek() throws Exception//返回栈顶元素不移除
{
if(!isEmpty())
{
return data[top];
}
else {
throw new Exception("栈为空");
}
}
T pop() throws Exception
{
if(isEmpty())
{
throw new Exception("栈为空");
}
else {
return data[top--];
}
}
public String toString()
{
if(top==-1)
{
return "";
}
else {
String va="";
for(int i=top;i>=0;i--)
{
va+=data[i]+" ";
}
return va;
}
}
}
package 队栈;
public class lisStack <T>{
static class node<T>
{
T data;
node next;
public node() {
}
public node(T value)
{
this.data=value;
}
}
int length;
node<T> head;//头节点
public lisStack() {
head=new node<>();
length=0;
}
boolean isEmpty()
{
return head.next==null;
}
int length()
{
return length;
}
public void push(T value) {//近栈
node<T> team=new node<T>(value);
if(length==0)
{
head.next=team;
}
else {
team.next=head.next;
head.next=team;}
length++;
}
public T peek() throws Exception {
if(length==0) {throw new Exception("链表为空");}
else {//删除
return (T) head.next.data;
}
}
public T pop() throws Exception {//出栈
if(length==0) {throw new Exception("链表为空");}
else {//删除
T value=(T) head.next.data;
head.next=head.next.next;//va.next
length--;
return value;
}
}
public String toString(){
if(length==0) {return "";}
else {
String va="";
node team=head.next;
while(team!=null)
{
va+=team.data+" ";
team=team.next;
}
return va;
}
}
}
测试
总结
- 栈的逻辑比较
。很容易理解,实现起来也相对容易。但是要注意数组情况的界限问题。简单
-
,相比栈,队列内容更丰富一些。难度也稍大一些。后面将介绍队列
- 如果有
还请不好需要改进
!指出
- 最后,喜欢的话可以关注公众号:bigsai 持续分享(回复 数据结构 获得精心准备资料一份!)