Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例講解
更新時(shí)間：2016年04月13日 08:53:21 作者：匆忙擁擠repeat
這篇文章主要介紹了Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例,棧的后進(jìn)先出和隊(duì)列的先進(jìn)先出是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的知識,本文則又對Java實(shí)現(xiàn)棧和隊(duì)列結(jié)構(gòu)的方法進(jìn)行了細(xì)分,需要的朋友可以參考下
棧和隊(duì)列：
一般是作為程序員的工具，用于輔助構(gòu)思算法，生命周期較短，運(yùn)行時(shí)才被創(chuàng)建；
訪問受限，在特定時(shí)刻，只有一個(gè)數(shù)據(jù)可被讀取或刪除；
是一種抽象的結(jié)構(gòu)，內(nèi)部的實(shí)現(xiàn)機(jī)制，對用戶不可見，比如用數(shù)組、鏈表來實(shí)現(xiàn)棧。
模擬棧結(jié)構(gòu)
同時(shí)，只允許一個(gè)數(shù)據(jù)被訪問，后進(jìn)先出
對于入棧和出棧的時(shí)間復(fù)雜度都為O(1),即不依賴棧內(nèi)數(shù)據(jù)項(xiàng)的個(gè)數(shù)，操作比較快
例，使用數(shù)組作為棧的存儲結(jié)構(gòu)
public class StackS<T> {
private int max;
private T[] ary;
private int top; //指針，指向棧頂元素的下標(biāo)
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<Integer> stack = new StackS<Integer>(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());
}
}
}
上面的例子，有一個(gè)maxSize的規(guī)定，因?yàn)閿?shù)組是要規(guī)定大小的，若想無限制，可以使用其他結(jié)構(gòu)來做存儲，當(dāng)然也可以new一個(gè)新的長度的數(shù)組。
例，使用LinkedList存儲來實(shí)現(xiàn)棧
public class StackSS<T> {
private LinkedList<T> datas;
public StackSS() {
datas = new LinkedList<T>();
}
// 入棧
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<Integer> stack = new StackS<Integer>(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結(jié)構(gòu)
public class WordReverse {
public static void main(String[] args) {
reverse("株式會社");
}
static void reverse(String word) {
if (word == null) return;
StackSS<Character> stack = new StackSS<Character>();
char[] charArray = word.toCharArray();
int len = charArray.length;
for (int i = 0; i <len; i++ ) {
stack.push(charArray[i]);
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
System.out.println("反轉(zhuǎn)后：" + sb.toString());
}
}
打?。?/p>
反轉(zhuǎn)后：社會式株
模擬隊(duì)列(一般隊(duì)列、雙端隊(duì)列、優(yōu)先級隊(duì)列)
隊(duì)列：
先進(jìn)先出，處理類似排隊(duì)的問題，先排的，先處理，后排的等前面的處理完了，再處理
對于插入和移除操作的時(shí)間復(fù)雜度都為O(1)，從后面插入，從前面移除
雙端隊(duì)列：
即在隊(duì)列兩端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight
含有棧和隊(duì)列的功能，如去掉insertLeft、removeLeft，那就跟棧一樣了；如去掉insertLeft、removeRight，那就跟隊(duì)列一樣了
一般使用頻率較低，時(shí)間復(fù)雜度 O(1)
優(yōu)先級隊(duì)列：
內(nèi)部維護(hù)一個(gè)按優(yōu)先級排序的序列。插入時(shí)需要比較查找插入的位置，時(shí)間復(fù)雜度O(N)， 刪除O(1)
/*
* 隊(duì)列 先進(jìn)先出，一個(gè)指針指示插入的位置，一個(gè)指針指示取出數(shù)據(jù)項(xiàng)的位置
*/
public class QueueQ<T> {
private int max;
private T[] ary;
private int front; //隊(duì)頭指針 指示取出數(shù)據(jù)項(xiàng)的位置
private int rear; //隊(duì)尾指針 指示插入的位置
private int nItems; //實(shí)際數(shù)據(jù)項(xiàng)個(gè)數(shù)
public QueueQ(int size) {
this.max = size;
ary = (T[]) new Object[max];
front = 0;
rear = -1;
nItems = 0;
}
//插入隊(duì)尾
public void insert(T t) {
if (rear == max - 1) {//已到實(shí)際隊(duì)尾，從頭開始
rear = -1;
}
ary[++rear] = t;
nItems++;
}
//移除隊(duì)頭
public T remove() {
T temp = ary[front++];
if (front == max) {//列隊(duì)到尾了，從頭開始
front = 0;
}
nItems--;
return temp;
}
//查看隊(duì)頭
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<Integer> queue = new QueueQ<Integer>(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:" + 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());
}
}
}
/*
* 雙端隊(duì)列<span style="white-space:pre"> </span>兩端插入、刪除
*/
public class QueueQT<T> {
private LinkedList<T> list;
public QueueQT() {
list = new LinkedList<T>();
}
// 插入隊(duì)頭
public void insertLeft(T t) {
list.addFirst(t);
}
// 插入隊(duì)尾
public void insertRight(T t) {
list.addLast(t);
}
// 移除隊(duì)頭
public T removeLeft() {
return list.removeFirst();
}
// 移除隊(duì)尾
public T removeRight() {
return list.removeLast();
}
// 查看隊(duì)頭
public T peekLeft() {
return list.getFirst();
}
// 查看隊(duì)尾
public T peekRight() {
return list.getLast();
}
public boolean isEmpty() {
return list.isEmpty();
}
public int size() {
return list.size();
}
}
/*
* 優(yōu)先級隊(duì)列 隊(duì)列中按優(yōu)先級排序，是一個(gè)有序的隊(duì)列
*/
public class QueueQP {
private int max;
private int[] ary;
private int nItems; //實(shí)際數(shù)據(jù)項(xiàng)個(gè)數(shù)
public QueueQP(int size) {
this.max = size;
ary = new int[max];
nItems = 0;
}
//插入隊(duì)尾
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]; //前一個(gè)賦給后一個(gè) 小的在后 相當(dāng)于用了插入排序，給定序列本來就是有序的，所以效率O(N)
} else {
break;
}
}
ary[j + 1] = t;
nItems++;
}
System.out.println(Arrays.toString(ary));
}
//移除隊(duì)頭
public int remove() {
return ary[--nItems]; //移除優(yōu)先級小的
}
//查看隊(duì)尾 優(yōu)先級最低的
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);
}
}
相關(guān)文章
對象進(jìn)行對象的轉(zhuǎn)換是一個(gè)操作重復(fù)且繁瑣的工作，于是市面上就有許多的對象轉(zhuǎn)換工具來解決這個(gè)問題，下面我們就來看看幾個(gè)比較常用的工具（mapstruct，Spring BeanUtils，Apache BeanUtils）使用方式及其性能2023-04-04
SpringMVC響應(yīng)視圖和結(jié)果視圖詳解
這篇文章主要介紹了SpringMVC響應(yīng)視圖和結(jié)果視圖，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了java final關(guān)鍵字的使用，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2021-01-01
LFU（Least Frequently Used）算法根據(jù)數(shù)據(jù)的歷史訪問頻率來淘汰數(shù)據(jù),其核心思想是“如果數(shù)據(jù)過去被訪問多次,那么將來被訪問的頻率也更高”,本文為大家整理了Java實(shí)現(xiàn)LFU算法的示例代碼,需要的可以參考下2023-11-11
這篇文章主要介紹了Java object類及正則表達(dá)式原理解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
MyBatis-Plus攔截器對敏感數(shù)據(jù)實(shí)現(xiàn)加密
做課程項(xiàng)目petstore時(shí)遇到需要加密屬性的問題，而MyBatis-Plus為開發(fā)者提供了攔截器的相關(guān)接口，本文主要介紹通過MyBatis-Plus的攔截器接口自定義一個(gè)攔截器類實(shí)現(xiàn)敏感數(shù)據(jù)如用戶密碼的加密功能，感興趣的可以了解一下2021-11-11
Tomcat 實(shí)現(xiàn)WebSocket詳細(xì)介紹
這篇文章主要介紹了Tomcat 如何實(shí)現(xiàn)WebSocket的相關(guān)資料,對WebSocket協(xié)議通信的過程進(jìn)行了詳細(xì)介紹，需要的朋友可以參考下2016-12-12
解決springcloud-eureka注冊時(shí)的ip問題
這篇文章主要介紹了解決springcloud-eureka注冊時(shí)的ip問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08
AQS?提供一套基礎(chǔ)的機(jī)制來實(shí)現(xiàn)線程的同步、阻塞與喚醒、等待隊(duì)列等功能，也就是想要深入學(xué)習(xí)線程工具類，這個(gè)同步隊(duì)列就必須得掌握，這篇文章主要介紹了Java中的AQS同步隊(duì)列問題,需要的朋友可以參考下2022-06-06
這篇文章主要介紹了Java 手動解析不帶引號的JSON字符串的操作，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-10-10