#棧和隊列
---
##棧
---
棧只允許訪問一個數據項:即最后插入的數據。溢出這個數據才能訪問倒數第二個插入的數據項。它是一種"后進先出"的數據結構。
棧最基本的操作是出棧(Pop)、入棧(Push),還有其他擴展操作,如查看棧頂元素,判斷棧是否為空、是否已滿,讀取棧的大小等。
```
/**
* 棧是先進后出
* 只能訪問棧頂的數據
* @author dream
*
*/
/**
* 基于數組來實現棧的基本操作
* 數據項入棧和出棧的時間復雜度均為O(1)
* @author dream
*
*/
public class ArrayStack {
private long[] a;
private int size; //棧數組的大小
private int top; //棧頂
public ArrayStack(int maxSize){
this.size = maxSize;
this.a = new long[size];
this.top = -1; //表示空棧
}
public void push(long value){ //入棧
if(isFull()){
System.out.println("棧已滿!");
return;
}
a[++top] = value;
}
public long peek(){ //返回棧頂內容,但不刪除
if(isEmpty()){
System.out.println("棧中沒有數據");
return 0;
}
return a[top];
}
public long pop(){ //彈出棧頂內容
if(isEmpty()){
System.out.println("棧中沒有數據!");
return 0;
}
return a[top--];
}
public int size(){
return top + 1;
}
/**
* 判斷是否滿了
* @return
*/
public boolean isFull(){
return (top == size - 1);
}
/**
* 是否為空
* @return
*/
public boolean isEmpty(){
return (top == -1);
}
public void display(){
for (int i = top; i >= 0; i--) {
System.out.println(a[i] + " ");
}
System.out.println("");
}
}
```
##隊列
---
依然使用數組作為底層容器來實現一個隊列的封裝
```
/**
* 隊列也可以用數組來實現,不過這里有個問題,當數組下標滿了后就不能再添加了,
* 但是數組前面由于已經刪除隊列頭的數據了,導致空。所以隊列我們可以用循環數組來實現,
* @author dream
*
*/
public class RoundQueue {
private long[] a;
private int size; //數組大小
private int nItems; //實際存儲數量
private int front; //頭
private int rear; //尾
public RoundQueue(int maxSize){
this.size = maxSize;
a = new long[size];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(long value){
if(isFull()){
System.out.println("隊列已滿");
return;
}
rear = ++rear % size;
a[rear] = value; //尾指針滿了就循環到0處,這句相當于下面注釋內容
nItems++;
}
public long remove(){
if(isEmpty()){
System.out.println("隊列為空!");
return 0;
}
nItems--;
front = front % size;
return a[front++];
}
public void display(){
if(isEmpty()){
System.out.println("隊列為空!");
return;
}
int item = front;
for(int i = 0;i < nItems; i++){
System.out.println(a[item++ % size] + " ");
}
System.out.println("");
}
public long peek(){
if(isEmpty()){
System.out.println("隊列為空!");
return 0;
}
return a[front];
}
public boolean isFull(){
return (nItems == size);
}
public boolean isEmpty(){
return (nItems == 0);
}
public int size(){
return nItems;
}
}
```
和棧一樣,隊列中插入數據項和刪除數據項的時間復雜度均為O(1)
還有個優先級隊列,優先級隊列是比棧和隊列更專用的數據結構。優先級隊列與上面普通的隊列相比,主要區別在于隊列中的元素是有序的,關鍵字最小(或者最大)的數據項總在隊頭。數據項插入的時候會按照順序插入到合適的位置以確保隊列的順序。優先級隊列的內部實現可以用數組或者一種特別的樹——堆來實現。這里用數組實現優先級隊列。
```
public class PriorityQueue {
private long[] a;
private int size;
private int nItems; //元素個數
public PriorityQueue(int maxSize){
size = maxSize;
nItems = 0;
a = new long[size];
}
public void insert(long value){
if(isFull()){
System.out.println("隊列已滿!");
return;
}
int j;
if(nItems == 0){ //空隊列直接添加
a[nItems++] = value;
}else {
//將數組中的數字依照下標按照從大到小排列
for(j=nItems-1; j>=0; j--){
if(value > a[j]){
a[j+1] = a[j];
}
else {
break;
}
}
a[j+1] = value;
nItems++;
}
}
public long remove(){
if(isFull()){
System.out.println("隊列為空!");
return 0;
}
return a[--nItems];
}
public long peekMin(){
return a[nItems - 1];
}
public boolean isFull(){
return (nItems == size);
}
public boolean isEmpty(){
return (nItems == 0);
}
public int size(){
return nItems;
}
public void display(){
for(int i = nItems - 1;i >= 0; i--){
System.out.println(a[i] + " ");
}
System.out.println(" ");
}
}
```
優先級隊列中,插入操作需要O(N)的時間,而刪除操作則需要O(1)的時間。
- JavaSE(Java基礎)
- Java基礎知識
- Java中的內存泄漏
- String源碼分析
- Java集合結構
- ArrayList源碼剖析
- HashMap源碼剖析
- Hashtable簡介
- Vector源碼剖析
- LinkedHashMap簡介
- LinkedList簡介
- JVM(Java虛擬機)
- JVM基礎知識
- JVM類加載機制
- Java內存區域與內存溢出
- 垃圾回收算法
- Java并發(JavaConcurrent)
- Java并發基礎知識
- 生產者和消費者問題
- Thread和Runnable實現多線程的區別
- 線程中斷
- 守護線程與阻塞線程的情況
- Synchronized
- 多線程環境中安全使用集合API
- 實現內存可見的兩種方法比較:加鎖和volatile變量
- 死鎖
- 可重入內置鎖
- 使用wait/notify/notifyAll實現線程間通信
- NIO
- 數據結構(DataStructure)
- 數組
- 棧和隊列
- Algorithm(算法)
- 排序
- 選擇排序
- 冒泡排序
- 快速排序
- 歸并排序
- 查找
- 順序查找
- 折半查找
- Network(網絡)
- TCP/UDP
- HTTP
- Socket
- OperatingSystem(操作系統)
- Linux系統的IPC
- android中常用設計模式
- 面向對象六大原則
- 單例模式
- Builder模式
- 原型模式
- 簡單工廠
- 策略模式
- 責任鏈模式
- 觀察者模式
- 代理模式
- 適配器模式
- 外觀模式
- Android(安卓面試點)
- Android基礎知識
- Android內存泄漏總結
- Handler內存泄漏分析及解決
- Android性能優化
- ListView詳解
- RecyclerView和ListView的異同
- AsyncTask源碼分析
- 插件化技術
- 自定義控件
- ANR問題
- Art和Dalvik的區別
- Android關于OOM的解決方案
- Fragment
- SurfaceView
- Android幾種進程
- APP啟動過程
- 圖片三級緩存
- Bitmap的分析與使用
- 熱修復的原理
- AIDL
- Binder機制
- Zygote和System進程的啟動過程
- Android中的MVC,MVP和MVVM
- MVP
- Android開機過程
- EventBus用法詳解
- 查漏補缺
- Git操作