Java数据结构之栈与队列实例详解

Java数据结构之栈与队列实例详解

目录一，栈1，概念2，栈的操作3，栈的实现4，实现mystack二，队列1，概念2，队列的实现3，实现myqueue栈、队列与数组的区别？总结

一，栈

1，概念

在我们软件应用 ，栈这种后进先出数据结构的应用是非常普遍的。比如你用浏 览器上网时不管什么浏览器都有 个"后退"键，你点击后可以接访问顺序的逆序加载浏览过的网页。

很多类似的软件，比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作，也是用栈这种方式来实现的，当然不同的软件具体实现会有很大差异，不过原理其实都是一样的。

栈( stack )是限定仅在表尾进行插入和删除的线性表

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

2，栈的操作

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

3，栈的实现

①入栈

public static void main(String[] args) {

Stack stack = new Stack<>();

stack.push(1);

stack.push(2);

stack.push(3);

stack.push(4);

int ret = stack.push(4);

System.out.println(ret);

}

②出栈

public static void main(String[] args) {

Stack stack = new Stack<>();

stack.push(1);

stack.push(2);

stack.push(3);

int ret1 = stack.pop();

int ret2 = stack.pop();

System.out.println(ret1);

System.out.println(ret2);

}

③获取栈顶元素

public static void main(String[] args) {

Stack stack = new Stack<>();

stack.push(1);

stack.push(2);

stack.push(3);

int ret1 = stack.pop();

int ret2 = stack.pop();

int ret3 = stack.peek();

System.out.println(ret1);

System.out.println(ret2);

System.out.println(ret3);

}

④判断栈是否为空

public static void main(String[] args) {

Stack stack = new Stack<>();

stack.push(1);

stack.push(2);

stack.push(3);

int ret1 = stack.pop();

int ret2 = stack.pop();

int ret3 = stack.peek();

System.out.println(ret1);

System.out.println(ret2);

System.out.println(ret3);

stack.pop();

boolean flag = stack.empty();

System.out.println(flag);

}

4，实现mystack

public class MyStack {

private T[] elem;//数组

private int top;//当前可以存放数据元素的下标-》栈顶指针

public MyStack() {

this.elem = (T[])new Object[10];

}

/**

* 入栈操作

* @param item 入栈的元素

*/

public void push(T item) {

//1、判断当前栈是否是满的

if(isFull()){

this.elem = Arrays.copyOf(this.elem,2*this.elem.length);

}

//2、elem[top] = item top++;

this.elem[this.top++] = item;

}

public boolean isFull(){

return this.elem.length == this.top;

}

/**

* 出栈

* @return 出栈的元素

*/

public T pop() {

if(empty()) {

throw new UnsupportedOperationException("栈为空！");

}

T ret = this.elem[this.top-1];

this.top--;//真正的改变了top的值

return ret;

}

/**

* 得到栈顶元素，但是不删除

* @return

*/

public T peek() {

if(empty()) {

throw new UnsupportedOperationException("栈为空！");

}

//this.top--;//真正的改变了top的值

return this.elem[this.top-1];

}

public boolean empty(){

return this.top == 0;

}

}

public class MyStack {

private T[] elem;//数组

private int top;//当前可以存放数据元素的下标-》栈顶指针

public MyStack() {

this.elem = (T[])new Object[10];

}

/**

* 入栈操作

* @param item 入栈的元素

*/

public void push(T item) {

//1、判断当前栈是否是满的

if(isFull()){

this.elem = Arrays.copyOf(this.elem,2*this.elem.length);

}

//2、elem[top] = item top++;

this.elem[this.top++] = item;

}

public boolean isFull(){

return this.elem.length == this.top;

}

/**

* 出栈

* @return 出栈的元素

*/

public T pop() {

if(empty()) {

throw new UnsupportedOperationException("栈为空！");

}

T ret = this.elem[this.top-1];

this.top--;//真正的改变了top的值

return ret;

}

/**

* 得到栈顶元素，但是不删除

* @return

*/

public T peek() {

if(empty()) {

throw new UnsupportedOperationException("栈为空！");

}

//this.top--;//真正的改变了top的值

return this.elem[this.top-1];

}

public boolean empty(){

return this.top == 0;

}

}

二，队列

1，概念

像移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人员都占线的情况下，客户会被要求等待，直到有某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。

操作系统和客服系统中，都是应用了种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

队列(queue) 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）

2，队列的实现

①入队

public static void main(String[] args) {

Deque queue = new LinkedList<>();

queue.offer(1);

queue.offer(2);

queue.offer(3);

queue.offer(4);

}

②出队

public static void main(String[] args) {

Deque queue = new LinkedList<>();

queue.offer(1);

queue.offer(2);

queue.offer(3);

queue.offer(4);

System.out.println(queue.poll());

System.out.println(queue.poll());

}

③获取队首元素

public static void main(String[] args) {

Deque queue = new LinkedList<>();

queue.offer(1);

queue.offer(2);

queue.offer(3);

queue.offer(4);

System.out.println(queue.poll());

System.out.println(queue.poll());

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

System.out.println(queue.peek());

}

3，实现myqueue

class Node {

private int val;

private Node next;

public int getVal() {

return val;

}

public void setVal(int val) {

this.val = val;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

public Node(int val) {

this.val = val;

}

}

public class MyQueue {

private Node first;

private Node last;

//入队

public void offer(int val) {

//尾插法 需要判断是不是第一次插入

Node node = new Node(val);

if(this.first == null) {

this.first = node;

this.last = node;

}else {

this.last.setNext(node);//last.next = node;

this.last = node;

}

}

//出队

public int poll() {

//1判断是否为空的

if(isEmpty()) {

throw new UnsupportedOperationException("队列为空！");

}

//this.first = this.first.next;

int ret = this.first.getVal();

this.first = this.first.getNext();

return ret;

}

//得到队头元素但是不删除

public int peek() {

//不要移动first

if(isEmpty()) {

throw new UnsupportedOperationException("队列为空！");

}

return this.first.getVal();

}

//队列是否为空

public boolean isEmpty() {

return this.first == null;

}

}

public static void main(String[] args) {

MyQueue myQueue = new MyQueue();

myQueue.offer(1);

myQueue.offer(2);

myQueue.offer(3);

System.out.println(myQueue.peek());

System.out.println(myQueue.poll());

System.out.println(myQueue.poll());

System.out.println(myQueue.poll());

System.out.println(myQueue.isEmpty());

}

栈、队列与数组的区别？

A: 栈、队列和优先级队列与数组主要有如下三个区别：

A: (一)程序员工具

数组和其他的结构（栈、队列、链表、树等等）都适用于数据库应用中作为数据记录。它们常用于记录那些对应于现实世界的对象和活动的数据，如职员档案等，这些结构便于数据的访问：它们易于进行插入、删除和查找特定数据项的操作。

然而，本篇要讲解的数据结构和算法更多的是作为程序员的工具来运用。它们主要作为构思算法的辅助工具，而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短得多。在程序操作执行期间它们才被创建，通常用它们去执行某项特殊的任务；当完成任务之后，它们则被销毁。

A: (二)受限访问

在数组中，若知道数据项的下标，便可以立即访问该数据项；而在本篇的数据结构中，访问是受限制的，即在特定时刻只有一个数据项可以被读取或者删除。

这些结构接口的设计增强了这种受限访问，访问其他数据项理论上是不允许的。

A: (三)更加抽象

栈、队列和优先队列是比数组和其他数据存储结构更为抽象的结构。主要是通过接口对栈、队列和优先队列进行定义，接口表明了它们可以完成的操作，而主要实现机制对用户来说是不可见的。

例如：栈的实现机制可以用数组实现，本篇的示例就是这样处理的，但它也可以用链表来实现。优先级队列的内部实现可以用数组或一种特别的树-堆来实现。

总结

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