Java模拟栈和队列数据结构的基本示例讲解

Java模拟栈和队列数据结构的基本示例讲解

栈和队列：

一般是作为程序员的工具，用于辅助构思算法，生命周期较短，运行时才被创建；

访问受限，在特定时刻，只有一个数据可被读取或删除；

是一种抽象的结构，内部的实现机制，对用户不可见，比如用数组、链表来实现栈。

模拟栈结构

同时，只允许一个数据被访问，后进先出

对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数，操作比较快

例，使用数组作为栈的存储结构

public class StackS {

private int max;

private T[] ary;

private int top; //指针，指向栈顶元素的下标

public StackS(int size) {

this.max = size;

ary = (T[]) new Object[max];

top = -1;

}

// 入栈

public void push(T data) {

if (!isFull())

ary[++top] = data;

}

// 出栈

public T pop() {

if (isEmpty()) {

return null;

}

return ary[top--];

}

// 查看栈顶

public T peek() {

return ary[top];

}

//栈是否为空

public boolean isEmpty() {

return top == -1;

}

//栈是否满

public boolean isFull() {

return top == max - 1;

}

//size

public int size() {

return top + 1;

}

public static void main(String[] args) {

StackS stack = new StackS(3);

for (int i = 0; i < 5; i++) {

stack.push(i);

System.out.println("size:" + stack.size());

}

for (int i = 0; i < 5; i++) {

Integer peek = stack.peek();

System.out.println("peek:" + peek);

System.out.println("size:" + stack.size());

}

for (int i = 0; i < 5; i++) {

Integer pop = stack.pop();

System.out.println("pop:" + pop);

http:// System.out.println("size:" + stack.size());

}

System.out.println("----");

for (int i = 5; i > 0; i--) {

stack.push(i);

System.out.println("size:" + stack.size());

}

for (int i = 5; i > 0; i--) {

Integer peek = stack.peek();

System.ouFEAFFiGOdt.println("peek:" + peek);

System.out.println("size:" + stack.size());

}

for (int i = 5; i > 0; i--) {

Integer pop = stack.pop();

System.out.println("pop:" + pop);

System.out.println("size:" + stack.size());

}

}

}

上面的例子，有一个maxSize的规定，因为数组是要规定大小的，若想无限制，可以使用其他结构来做存储，当然也可以new一个新的长度的数组。

例，使用LinkedList存储来实现栈

public class StackSS {

private LinkedList datas;

public StackSS() {

datas = new LinkedList();

}

// 入栈

public void push(T data) {

datas.addLast(data);

}

// 出栈

public T pop() {

return datas.removeLast();

}

// 查看栈顶

public T peek() {

return datas.getLast();

}

//栈是否为空

public boolean isEmpty() {

return datas.isEmpty();

}

//size

public int size() {

return datas.size();

}

public static void main(String[] args) {

StackS stack = new StackS(3);

for (int i = 0; i < 5; i++) {

stack.push(i);

System.out.println("size:" + stack.size());

}

for (int i = 0; i < 5; i++) {

Integer peek = stack.peek();

System.out.println("peek:" + peek);

System.out.println("size:" + stack.size());

}

for (int i = 0; i < 5; i++) {

Integer pop = stack.pop();

System.out.println("pop:" + pop);

System.out.println("size:" + stack.size());

}

System.out.println("----");

for (int i = 5; i > 0; i--) {

stack.push(i);

System.out.println("size:" + stack.size());

}

for (int i = 5; i > 0; i--) {

Integer peek = stack.peek();

System.out.println("peek:" + peek);

System.out.println("size:" + stack.size());

}

for (int i = 5; i > 0; i--) {

Integer pop = stack.pop();

System.out.println("pop:" + pop);

System.out.println("size:" + stack.size());

}

}

}

例，单词逆序，使用Statck结构

public class WordReverse {

public static void main(String[] args) {

reverse("株式会社");

}

static void reverse(String word) {

if (word == null) return;

StackSS stack = new StackSS();

char[] charArray = word.toCharArray();

int len = charArray.length;

for (int i = 0; i

stack.push(charArray[i]);

}

StringBuilder sb = new StringBuilder();

while (!stack.isEmpty()) {

sb.append(stack.pop());

}

System.out.println("反转后：" + sb.toString());

}

}

打印：

反转后：社会式株

模拟队列(一般队列、双端队列、优先级队列)

队列：

先进先出，处理类似排队的问题，先排的，先处理，后排的等前面的处理完了，再处理

对于插入和移除操作的时间复杂度都为O(1)，从后面插入，从前面移除

双端队列：

即在队列两端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight

含有栈和队列的功能，如去掉insertLeft、removeLeft，那就跟栈一样了；如去掉insertLeft、removeRight，那就跟队列一样了

一般使用频率较低，时间复杂度 O(1)

优先级队列：

内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置，时间复杂度O(N)， 删除O(1)

/*

* 队列 先进先出，一个指针指示插入的位置，一个指针指示取出数据项的位置

*/

public class QueueQ {

private int max;

private T[] ary;

private int front; //队头指针 指示取出数据项的位置

private int rear; //队尾指针 指示插入的位置

private int nItems; //实际数据项个数

public QueueQ(int size) {

this.max = size;

ary = (T[]) new Object[max];

front = 0;

rear = -1;

nItems = 0;

}

//插入队尾

public void insert(T t) {

if (rear == max - 1) {//已到实际队尾，从头开始

rear = -1;

}

ary[++rear] = t;

nItems++;

}

//移除队头

public T remove() {

T temp = ary[front++];

if (front == max) {//列队到尾了，从头开始

front = 0;

}

nItems--;

return temp;

}

//查看队头

public T peek() {

return ary[front];

}

public boolean isEmpty() {

return nItems == 0;

}

public boolean isFull() {

return nItems == max;

}

public int size() {

return nItems;

}

public static void main(String[] args) {

QueueQ queue = new QueueQ(3);

for (int i = 0; i < 5; i++) {

queue.insert(i);

System.out.println("size:" + queue.size());

}

for (int i = 0; i < 5; i++) {

Integer peek = queue.peek();

System.out.println("peek:" + peek);

System.out.println("size:" + queue.size());

}

for (int i = 0; i < 5; i++) {

Integer remove = queue.remove();

System.out.println("remove:" + remove);

System.out.println("size:" + queue.size());

}

System.out.println("----");

for (int i = 5; i > 0; i--) {

queue.insert(i);

System.out.println("size:" + http://queue.size());

}

for (int i = 5; i > 0; i--) {

Integer peek = queue.peek();

System.out.println("peek:" + peek);

System.out.println("size:" + queue.size());

}

for (int i = 5; i > 0; i--) {

Integer remove = queue.remove();

System.out.println("remove:" + remove);

System.out.println("size:" + queue.size());

}

}

}

/*

* 双端队列 两端插入、删除

*/

public class QueueQT {

private LinkedList list;

public QueueQT() {

list = new LinkedList();

}

// 插入队头

public void insertLeft(T t) {

list.addFirst(t);

}

// 插入队尾

public void insertRight(T t) {

list.addLast(t);

}

// 移除队头

public T removeLeft() {

return list.removeFirst();

}

// 移除队尾

public T removeRight() {

return list.removeLast();

}

// 查看队头

public T peekLeft() {

return list.getFirst();

}

// 查看队尾

public T peekRight() {

return list.getLast();

}

public boolean isEmpty() {

return list.isEmpty();

}

public int size() {

return list.size();

}

}

/*

* 优先级队列 队列中按优先级排序，是一个有序的队列

*/

public class QueueQP {

private int max;

private int[] ary;

private int nItems; //实际数据项个数

public QueueQP(int size) {

this.max = size;

ary = new int[max];

nItems = 0;

}

//插入队尾

public void insert(int t) {

int j;

if (nItems == 0) {

ary[nItems++] = t;

} else {

for (j = nItems - 1; j >= 0; j--) {

if (t > ary[j]) {

ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后 相当于用了插入排序，给定序列本来就是有序的，所以效率O(N)

} else {

break;

}

}

ary[j + 1] = t;

nItems++;

}

System.out.println(Arrays.toString(ary));

}

//移除队头

public int remove() {

return ary[--nItems]; //移除优先级小的

}

//查看队尾 优先级最低的

public int peekMin() {

return ary[nItems - 1];

}

public boolean isEmpty() {

return nItems == 0;

}

public boolean isFull() {

return nItems == max;

}

public int size() {

return nItems;

}

public static void main(String[] args) {

QueueQP queue = new QueueQP(3);

queue.insert(1);

queue.insert(2);

queue.insert(3);

int remove = queue.remove();

System.out.println("remove:" + remove);

}

}

stack.push(charArray[i]);

}

StringBuilder sb = new StringBuilder();

while (!stack.isEmpty()) {

sb.append(stack.pop());

}

System.out.println("反转后：" + sb.toString());

}

}

打印：

反转后：社会式株

模拟队列(一般队列、双端队列、优先级队列)

队列：

先进先出，处理类似排队的问题，先排的，先处理，后排的等前面的处理完了，再处理

对于插入和移除操作的时间复杂度都为O(1)，从后面插入，从前面移除

双端队列：

即在队列两端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight

含有栈和队列的功能，如去掉insertLeft、removeLeft，那就跟栈一样了；如去掉insertLeft、removeRight，那就跟队列一样了

一般使用频率较低，时间复杂度 O(1)

优先级队列：

内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置，时间复杂度O(N)， 删除O(1)

/*

* 队列 先进先出，一个指针指示插入的位置，一个指针指示取出数据项的位置

*/

public class QueueQ {

private int max;

private T[] ary;

private int front; //队头指针 指示取出数据项的位置

private int rear; //队尾指针 指示插入的位置

private int nItems; //实际数据项个数

public QueueQ(int size) {

this.max = size;

ary = (T[]) new Object[max];

front = 0;

rear = -1;

nItems = 0;

}

//插入队尾

public void insert(T t) {

if (rear == max - 1) {//已到实际队尾，从头开始

rear = -1;

}

ary[++rear] = t;

nItems++;

}

//移除队头

public T remove() {

T temp = ary[front++];

if (front == max) {//列队到尾了，从头开始

front = 0;

}

nItems--;

return temp;

}

//查看队头

public T peek() {

return ary[front];

}

public boolean isEmpty() {

return nItems == 0;

}

public boolean isFull() {

return nItems == max;

}

public int size() {

return nItems;

}

public static void main(String[] args) {

QueueQ queue = new QueueQ(3);

for (int i = 0; i < 5; i++) {

queue.insert(i);

System.out.println("size:" + queue.size());

}

for (int i = 0; i < 5; i++) {

Integer peek = queue.peek();

System.out.println("peek:" + peek);

System.out.println("size:" + queue.size());

}

for (int i = 0; i < 5; i++) {

Integer remove = queue.remove();

System.out.println("remove:" + remove);

System.out.println("size:" + queue.size());

}

System.out.println("----");

for (int i = 5; i > 0; i--) {

queue.insert(i);

System.out.println("size:" + http://queue.size());

}

for (int i = 5; i > 0; i--) {

Integer peek = queue.peek();

System.out.println("peek:" + peek);

System.out.println("size:" + queue.size());

}

for (int i = 5; i > 0; i--) {

Integer remove = queue.remove();

System.out.println("remove:" + remove);

System.out.println("size:" + queue.size());

}

}

}

/*

* 双端队列 两端插入、删除

*/

public class QueueQT {

private LinkedList list;

public QueueQT() {

list = new LinkedList();

}

// 插入队头

public void insertLeft(T t) {

list.addFirst(t);

}

// 插入队尾

public void insertRight(T t) {

list.addLast(t);

}

// 移除队头

public T removeLeft() {

return list.removeFirst();

}

// 移除队尾

public T removeRight() {

return list.removeLast();

}

// 查看队头

public T peekLeft() {

return list.getFirst();

}

// 查看队尾

public T peekRight() {

return list.getLast();

}

public boolean isEmpty() {

return list.isEmpty();

}

public int size() {

return list.size();

}

}

/*

* 优先级队列 队列中按优先级排序，是一个有序的队列

*/

public class QueueQP {

private int max;

private int[] ary;

private int nItems; //实际数据项个数

public QueueQP(int size) {

this.max = size;

ary = new int[max];

nItems = 0;

}

//插入队尾

public void insert(int t) {

int j;

if (nItems == 0) {

ary[nItems++] = t;

} else {

for (j = nItems - 1; j >= 0; j--) {

if (t > ary[j]) {

ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后 相当于用了插入排序，给定序列本来就是有序的，所以效率O(N)

} else {

break;

}

}

ary[j + 1] = t;

nItems++;

}

System.out.println(Arrays.toString(ary));

}

//移除队头

public int remove() {

return ary[--nItems]; //移除优先级小的

}

//查看队尾 优先级最低的

public int peekMin() {

return ary[nItems - 1];

}

public boolean isEmpty() {

return nItems == 0;

}

public boolean isFull() {

return nItems == max;

}

public int size() {

return nItems;

}

public static void main(String[] args) {

QueueQP queue = new QueueQP(3);

queue.insert(1);

queue.insert(2);

queue.insert(3);

int remove = queue.remove();

System.out.println("remove:" + remove);

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。