java数据结构与算法——栈与队列_java中队列和栈的时间复杂度

本节目标：

1.掌握栈的原理与应用

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

栈和队列都属于线性表

栈

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

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

特点：后进先出

时间复杂度：O(1)

顺序存储结构

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

top=-1时表示栈空；

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

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

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

/**
 * 栈的基本基本功能
 * @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

/**
 * 节点类
 * @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取模后是否等于队首指针作为判断满队的条件。

**

}

/**
 * 顺序队列
 * @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;


}

}

链式存储结构