Java模擬棧和隊列數(shù)據(jù)結(jié)構(gòu)的基本示例講解
更新時間：2016年04月13日 08:53:21 作者：匆忙擁擠repeat
這篇文章主要介紹了Java模擬棧和隊列數(shù)據(jù)結(jié)構(gòu)的基本示例,棧的后進先出和隊列的先進先出是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的知識,本文則又對Java實現(xiàn)棧和隊列結(jié)構(gòu)的方法進行了細分,需要的朋友可以參考下
棧和隊列：
一般是作為程序員的工具，用于輔助構(gòu)思算法，生命周期較短，運行時才被創(chuàng)建；
訪問受限，在特定時刻，只有一個數(shù)據(jù)可被讀取或刪除；
是一種抽象的結(jié)構(gòu)，內(nèi)部的實現(xiàn)機制，對用戶不可見，比如用數(shù)組、鏈表來實現(xiàn)棧。
模擬棧結(jié)構(gòu)
同時，只允許一個數(shù)據(jù)被訪問，后進先出
對于入棧和出棧的時間復(fù)雜度都為O(1),即不依賴棧內(nèi)數(shù)據(jù)項的個數(shù)，操作比較快
例，使用數(shù)組作為棧的存儲結(jié)構(gòu)
public class StackS<T> {
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<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());
}
}
}
上面的例子，有一個maxSize的規(guī)定，因為數(shù)組是要規(guī)定大小的，若想無限制，可以使用其他結(jié)構(gòu)來做存儲，當然也可以new一個新的長度的數(shù)組。
例，使用LinkedList存儲來實現(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());
}
}
打印：
反轉(zhuǎn)后：社會式株
模擬隊列(一般隊列、雙端隊列、優(yōu)先級隊列)
隊列：
先進先出，處理類似排隊的問題，先排的，先處理，后排的等前面的處理完了，再處理
對于插入和移除操作的時間復(fù)雜度都為O(1)，從后面插入，從前面移除
雙端隊列：
即在隊列兩端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight
含有棧和隊列的功能，如去掉insertLeft、removeLeft，那就跟棧一樣了；如去掉insertLeft、removeRight，那就跟隊列一樣了
一般使用頻率較低，時間復(fù)雜度 O(1)
優(yōu)先級隊列：
內(nèi)部維護一個按優(yōu)先級排序的序列。插入時需要比較查找插入的位置，時間復(fù)雜度O(N)， 刪除O(1)
/*
* 隊列 先進先出，一個指針指示插入的位置，一個指針指示取出數(shù)據(jù)項的位置
*/
public class QueueQ<T> {
private int max;
private T[] ary;
private int front; //隊頭指針 指示取出數(shù)據(jù)項的位置
private int rear; //隊尾指針 指示插入的位置
private int nItems; //實際數(shù)據(jù)項個數(shù)
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<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());
}
}
}
/*
* 雙端隊列<span style="white-space:pre"> </span>兩端插入、刪除
*/
public class QueueQT<T> {
private LinkedList<T> list;
public QueueQT() {
list = new LinkedList<T>();
}
// 插入隊頭
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();
}
}
/*
* 優(yōu)先級隊列 隊列中按優(yōu)先級排序，是一個有序的隊列
*/
public class QueueQP {
private int max;
private int[] ary;
private int nItems; //實際數(shù)據(jù)項個數(shù)
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]; //移除優(yōu)先級小的
}
//查看隊尾 優(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)文章
java線程池ThreadPoolExecutor實現(xiàn)原理詳解
這篇文章主要介紹了java線程池ThreadPoolExecutor實現(xiàn)原理詳解,ThreadPoolExecutor是線程池實現(xiàn)類,會動態(tài)創(chuàng)建多個線程,并發(fā)執(zhí)行提交的多個任務(wù),需要的朋友可以參考下2023-12-12
前提：本文假設(shè)讀者已經(jīng)具有使用JUnit 4以前版本的經(jīng)驗。2008-09-09
Mybatis注解開發(fā)單表、多表操作的實現(xiàn)代碼
這篇文章主要介紹了Mybatis高級:Mybatis注解開發(fā)單表操作,Mybatis注解開發(fā)多表操作,構(gòu)建sql語句,綜合案例學(xué)生管理系統(tǒng)使用接口注解方式優(yōu)化,需要的朋友可以參考下2021-02-02
這篇文章主要介紹了mybatis實現(xiàn)特殊字段加密，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-03-03
Java中的HashTable是一種線程安全的哈希表實現(xiàn),它可以高效地存儲和快速查找數(shù)據(jù),本文將介紹Java中的HashTable的實現(xiàn)原理、常用方法和測試用例,需要的小伙伴可以參考一下2023-09-09
這篇文章主要介紹了淺談單例模式和線程安全問題,再某些特殊的情況下，存在一個類僅能用來產(chǎn)生一個唯一對象的必要性,因此需要單例模式,需要的朋友可以參考下2023-04-04
在做項目中，經(jīng)常會遇到一種情況，需要將一個小word文檔的內(nèi)容插入到一個大word（主文檔）中。本文就為大家準備了Java實現(xiàn)合并word文檔的方法，需要的可以參考一下2022-08-08
這篇文章主要介紹了java中對List分段操作的實例的相關(guān)資料,希望通過本文大家能夠掌握list的分段實現(xiàn)方法，需要的朋友可以參考下2017-09-09
單元測試就是針對最小的功能單元編寫測試代碼，Junit是使用Java語言實現(xiàn)的單元測試框架，它是開源的，Java開發(fā)者都應(yīng)當學(xué)習(xí)并使用Junit編寫單元測試。本文就來講講Junit框架的使用教程，需要的可以參考一下2022-05-05
java實現(xiàn)jdbc批量插入數(shù)據(jù)
這篇文章主要為大家詳細介紹了java實現(xiàn)jdbc批量插入數(shù)據(jù)，三種JDBC批量插入編程方法進行比較，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-05-05