java数据结构与算法——栈与队列

不念不忘少年蓝@ 2022-05-27 11:22 263阅读 0赞

本节目标：

1.掌握栈的原理与应用

2.掌握队列的原理与应用

栈和队列都属于线性表

# 栈 #

栈又称为堆栈，是一种运算受限的线性表，这是因为它仅允许在线性表的固定一端（表尾）进行插入、删除和读取元素等运算，不允许在其他任何位置进行运算。

相关名词：栈顶、栈顶元素、栈底、进栈（压栈）、出栈（退栈）

特点：后进先出

时间复杂度：O(1)

## 顺序存储结构 ##

需要一个数组和整型变量，利用数组来存储元素，利用整型变量存储栈顶元素的下标，通常用top表示，也叫栈顶指针。

top=-1时表示栈空；

压栈时，首先将top增1，用来指代新的栈顶位置，然后把新元素赋值到栈顶位置上；

退栈时，先取出栈顶元素，然后top减1；

top指向最后一个下标位置时，栈满。若再添加元素时，需要重新分配更大的数组空间；

![20180418092639691][]

/\*\*  
 \* 栈的基本基本功能  
 \* @author root  
 \*/  
public interface Stack \{  
//向栈顶插入一个元素  
void push(Object obj);  
//删除栈顶元素并返回  
Object pop();  
//返回栈顶元素  
Object peek();  
//是否为空  
boolean isEmpty();  
//清空栈内元素  
void clean();

/\*\*  
 \* 栈基本功能实现  
 \* @author root  
 \*/  
public class SequenceStack implements Stack \{  
//栈的一维数组初始长度  
final int minSize = 10;  
//栈保存元素依赖于数组  
private Object\[\] stackArray;  
//栈顶元素位置下标（相当于数组下标），栈顶指针  
private int top ;  
/\*\*  
 \* 构造函数  
 \*/  
SequenceStack()\{  
top = -1;//-1表示初始化时栈顶没有元素  
stackArray = new Object\[minSize\];  
\}  
  
SequenceStack(int n)\{//指定元素存储空间  
if (n<minSize) \{  
n = minSize;  
\}  
top = -1;  
stackArray = new Object\[n\];  
\}  
  
/\*\*  
 \* 往栈中压入元素  
 \*/  
@Override  
public void push(Object obj) \{  
// 1.判断数组空间，若已满，则创建2倍空间数组，复制到新空间  
// 2.栈顶指针+1  
// 3.新元素写到新栈顶位置  
if (top == this.stackArray.length-1) \{  
Object\[\] b = new Object\[2\*top\];  
for (int i = 0; i <= top; i++) \{  
b\[i\] = this.stackArray\[i\];  
\}  
stackArray = b;  
  
\}  
top++;  
stackArray\[top\] = obj;  
\}  
  
/\*\*  
 \* 弹出栈顶元素  
 \*/  
@Override  
public Object pop() \{  
//1.判断栈是否为空，空时返回null  
//2.栈顶指针-1  
//3.返回栈顶元素  
  
if (top == -1) \{  
return null;  
\}  
top--;  
return this.stackArray\[top+1\];  
\}  
  
/\*\*  
 \* 查看栈顶元素  
 \*/  
@Override  
public Object peek() \{  
if (top == -1) \{  
return null;  
\}  
return stackArray\[top\];  
\}  
  
/\*\*  
 \* 栈是否为空  
 \*/  
@Override  
public boolean isEmpty() \{  
return top == -1;  
\}  
/\*\*  
 \* 清空栈  
 \*/  
@Override  
public void clean() \{  
this.top = -1;  
\}

/\*\*  
 \* 测试栈的基本功能  
 \* @author root  
 \*/  
public class SequenceStackTest \{  
public static void main(String\[\] args) \{  
Stack stack = new SequenceStack();  
int\[\] a = \{2,4,23,3,5\};  
for (int i = 0; i < a.length; i++) \{  
stack.push(a\[i\]);  
\}  
System.out.println("stack.pop:"+stack.pop());//5  
stack.push(1);  
System.out.println(stack.peek());//1  
stack.clean();  
System.out.println(stack.isEmpty());//true  
\}

## 链式存储结构 ##

由结点构成的单链表实现，也成为链栈，即链接存储的栈。表头指针成为栈顶指针，由栈顶节点指向的元素结点称为栈顶结点。

压栈时，使新元素的结点指针域指向原先的栈顶结点，栈顶指针指向新元素结点；

退栈时，栈顶指针指向后继结点；

空栈：top为null

![2018041809271040][]

/\*\*  
 \* 节点类  
 \* @author root  
 \*/  
public class Node \{  
 Object element;//值域  
 Node next;//指针域  
  
Node(Node next)\{  
this.next = next;  
\}  
Node(Object element,Node next)\{  
this.element = element;  
this.next = next;  
\}

/\*\*  
 \* 链表结构的栈  
 \* @author root  
 \*  
 \*/  
public class LinkStack implements Stack\{  
private Node top;//栈顶指针  
  
LinkStack()\{  
this.top = null;//初始化为空栈  
\}  
  
@Override  
public void push(Object obj) \{  
top = new Node(obj, top);//相当于在单链表表头插入结点  
  
\}  
  
/\*\*  
 \* 弹出栈顶元素  
 \*/  
@Override  
public Object pop() \{  
if (top == null) \{  
return null;  
\}  
Node p = top;    //将栈顶引用保存到p中  
top = top.next;//栈顶指针指向下一个结点  
return p.element;//弹出原先栈顶元素  
\}  
  
@Override  
public Object peek() \{  
if (top == null) \{  
return null;  
\}  
  
return top.element;//返回栈顶元素的值  
\}  
  
@Override  
public boolean isEmpty() \{  
return top == null;  
\}  
  
@Override  
public void clean() \{  
top = null;  
\}  
\}

# 队列 #

队列简称队，也是运算受限的线性表，仅允许在表的一段插入，另一端删除。允许插入的一端做队尾，进行删除的一端做队首。

相关名词：进队、出队

特点：先进先出（FIFO）

时间复杂度：O(1)

## 顺序存储结构 ##

需要一个数组和两三个变量实现。数组用来保存所有元素；需要一个变量保存队首位置（通常存储队首元素的前一个位置），也即队首指针；需要一个变量保存队尾位置，也即队尾指针；或者再添加一个变量保存元素个数。

进队：先将队尾指针后移一个位置，然后向这个位置写入新元素。如果队尾指针指向数组空间的最后一个位置时，若队首元素的前面仍有空闲位置，则表明队列没有占满整个数组空间，那么下一个存储位置为下标为0的空闲位置，因此，要先将队尾指针指向下标为0的位置，然后写入。

通过this.rear= (this.rear+1)%this.queueArray.length可以使存储队列的整个数组空间变为首尾相接的环，所以顺序存储的队列又称为循环队列。在循环队列中，存储空间是首尾相接的，当rear指向最后一个存储位置的时候，下一个位置自动转为数组空间的开始位置（即下标为0的位置）。

出队：如果队列不空，先将队首指针后移，然后返回该元素的值。队首后移也要采用取模运算，this.front= (this.front\+1)%this.queueArray.length，实现首尾相接，循环利用。

队列已满的条件是队列长度为this.queueArray.length-1，也就是说必须有一个位置是空闲的。这是因为如果使用全部的数组空间，当队首和队尾指向同一个位置时，可能是空队，也可能是满队。利用队尾指针加1并对this.queueArray.length取模后是否等于队首指针作为判断满队的条件。

![20180418122320660][]

\*\*

\* 队列的基本功能  
 \* @author root  
 \*  
 \*/  
public interface Queue \{  
//进队，在队尾部插入新元素  
void enter(Object obj);  
//出队，从队首删除并返回对首元素  
Object leave();  
//返回队首元素  
Object peek();  
//队列是否为空  
boolean isEmpty();  
//清空队列  
void clean();

/\*\*  
 \* 顺序队列  
 \* @author root  
 \*  
 \*/  
public class SequenceQueue implements Queue \{  
//存储队列的一维数组最小空间  
final int minSize = 10;  
//存储队列的数组空间  
private Object\[\] queueArray;  
private int front;//队首指针  
private int rear;//队尾指针  
/\*\*  
 \* 构造函数  
 \*/  
SequenceQueue()\{  
this.front =0;  
this.rear = 0;  
queueArray = new Object\[minSize\];  
\}  
SequenceQueue(int n)\{  
this.front = 0;  
this.rear = 0;  
if (n<=minSize) \{  
n = minSize;  
\}  
queueArray = new Object\[n\];  
\}  
  
  
@Override  
public void enter(Object obj) \{  
// 队列已满（有两种情形），分配双倍空间，并复制到新空间数组内  
if ((this.rear+1)%this.queueArray.length == this.front) \{  
Object\[\] p = new Object\[2\*this.queueArray.length\];  
//已满，队尾指针在后  
if (this.rear == this.queueArray.length-1) \{  
for (int i = 1; i <=this.rear; i++) \{  
p\[i\] = this.queueArray\[i\];  
\}  
\}else\{  
//已满，队尾指针在前  
//先复制队列前面元素，后复制队列后部分元素  
int k = 1;  
for (int i = this.front+1; i < this.queueArray.length-1; i++,k++) \{  
p\[k\] = this.queueArray\[i\];  
\}  
for (int j = 0; j <= this.rear; j++,k++) \{  
p\[k\] = this.queueArray\[j\];  
\}  
this.front = 0;  
this.rear = this.queueArray.length-1;   
\}  
queueArray=p;  
\}  
this.queueArray\[(this.rear+1)%this.queueArray.length\] = obj;  
\}  
  
@Override  
public Object leave() \{  
if (this.front == this.rear) \{  
return null;  
\}  
this.front = (this.front+1)%this.queueArray.length;//将队首指针指向下一个队首元素位置  
return queueArray\[this.front\];  
\}  
  
  
@Override  
public Object peek() \{  
if(this.front == this.rear)\{  
return null;  
\}  
 return queueArray\[(this.front+1)%this.queueArray.length\];  
\}  
  
  
@Override  
public boolean isEmpty() \{  
return this.front == this.rear;  
\}  
  
  
@Override  
public void clean() \{  
this.front = this.rear = 0;  
  
  
\}

## 链式存储结构 ##

![20180418122758203][]

/\*\*  
 \* 节点类  
 \* @author root  
 \*/  
public class Node \{  
 Object element;//值域  
 Node next;//指针域  
  
Node(Node next)\{  
this.next = next;  
\}  
Node(Object element,Node next)\{  
this.element = element;  
this.next = next;  
\}

/\*\*  
 \* 链式队列  
 \* @author root  
 \*/

public class LinkQueue implements Queue \{  
  
private Node front;  
private Node rear;  
LinkQueue()\{  
this.front = this.rear = null;  
\}  
  
@Override  
public void enter(Object obj) \{  
if (this.rear == null) \{  
this.front = this.rear = new Node(obj, null);  
\}else\{  
this.rear = this.rear.next = new Node(obj, null);  
\}  
\}  
  
  
@Override  
public Object leave() \{  
if (this.front == null) \{  
return null;  
\}  
Node x = this.front;  
this.front = this.front.next;  
if (this.front == null) \{  
this.rear = null;  
\}  
return x.element;  
\}  
  
  
@Override  
public Object peek() \{  
if (this.front == null) \{  
return null;  
\}  
return this.front.element;  
\}  
  
  
@Override  
public boolean isEmpty() \{  
// TODO Auto-generated method stub  
return this.front == null;  
\}  
  
  
@Override  
public void clean() \{  
this.front = this.rear = null;  
\}  
\}

[20180418092639691]: /images/20220527/54e5c1b9fff04d6899f108ab1eabcf52.png
[2018041809271040]: /images/20220527/084697349d62456485eb5cb407367988.png
[20180418122320660]: /images/20220527/81ffa1d0f232437999ef3de7c3ac8695.png
[20180418122758203]: /images/20220527/e63175c31f4548c6806eb84631b16d1e.png