Java模仿棧和隊列數據構造的根本示例講授。本站提示廣大學習愛好者：（Java模仿棧和隊列數據構造的根本示例講授）文章只能為提供參考，不一定能成為您想要的結果。以下是Java模仿棧和隊列數據構造的根本示例講授正文
棧和隊列：
普通是作為法式員的對象，用於幫助構想算法，性命周期較短，運轉時才被創立；
拜訪受限，在特准時刻，只要一個數據可被讀取或刪除；
是一種籠統的構造，外部的完成機制，對用戶弗成見，好比用數組、鏈表來完成棧。
模仿棧構造
同時，只許可一個數據被拜訪，落後先出
關於入棧和出棧的時光龐雜度都為O(1),即不依附棧內數據項的個數，操作比擬快
例，應用數組作為棧的存儲構造
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的劃定，由於數組是要劃定年夜小的，若想無窮制，可使用其他構造來做存儲，固然也能夠new一個新的長度的數組。
例，應用LinkedList存儲來完成棧
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構造
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("反轉後：" + sb.toString());
}
}
打印：
反轉後：社會式株
模仿隊列(普通隊列、雙端隊列、優先級隊列)
隊列：
先輩先出，處置相似列隊的成績，先排的，先處置，後排的等後面的處置完了，再處置
關於拔出和移除操作的時光龐雜度都為O(1)，從前面拔出，早年面移除
雙端隊列：
即在隊列兩頭都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight
含有棧和隊列的功效，如去失落insertLeft、removeLeft，那就跟棧一樣了；如去失落insertLeft、removeRight，那就跟隊列一樣了
普通應用頻率較低，時光龐雜度 O(1)
優先級隊列：
外部保護一個按優先級排序的序列。拔出時須要比擬查找拔出的地位，時光龐雜度O(N)， 刪除O(1)
/*
* 隊列 先輩先出，一個指針指導拔出的地位，一個指針指導掏出數據項的地位
*/
public class QueueQ<T> {
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<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 > </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();
}
}
/*
* 優先級隊列 隊列中按優先級排序，是一個有序的隊列
*/
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);
}
}
