Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)
1. 棧
1.1 概念
- 棧：是一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。
- 特點(diǎn)：棧中的數(shù)據(jù)元素遵循先進(jìn)后出的原則，但要注意進(jìn)的同時(shí)也可以出，元素不是要全部進(jìn)展后才能出棧
- 棧頂：進(jìn)行數(shù)據(jù)插入和刪除操作的一端
- 棧底：棧頂?shù)牧硪欢?/li>
- 壓棧：棧的插入操作就做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂
- 出棧：棧的刪除操作就叫做出棧，出數(shù)據(jù)在棧頂
1.2 助解圖題
助解圖：
手槍的彈夾其實(shí)就類似是一個(gè)棧
當(dāng)我們壓子彈的時(shí)候，就是壓棧
當(dāng)我們上膛后，打槍時(shí)，就是出棧
助解題：
- 題一： 一個(gè)棧的入棧順序是 a、b、c、d、e，該棧不可能的出棧順序是（ ）
A.edcba B.decba C.dceab D.abcde
結(jié)果為：C
- 題二： 中綴表達(dá)式為 a + b * c + ( d * e + f ) * g，那么它的后綴表達(dá)式為什么？
結(jié)果為：a b c * + d e * f + g * +
方法步驟（快捷方法）：
該方法中將括號(hào)的運(yùn)算符移到括號(hào)前面得到的結(jié)果就是前綴表達(dá)式
本題背景：我們平常使用的表達(dá)式一般為中綴表達(dá)式，中綴表達(dá)式便于人們的理解與計(jì)算。而后綴表達(dá)式的運(yùn)算符更方便計(jì)算機(jī)的運(yùn)算（如二叉樹、堆棧的方法計(jì)算）
- 題三： 通過棧返回后綴表達(dá)式 a b c * + d e * f + g * + 計(jì)算的結(jié)果
結(jié)果為：a + b * c + ( d * e + f ) * g
方法：當(dāng)參數(shù)是數(shù)字時(shí)就壓棧。當(dāng)參數(shù)為運(yùn)算符時(shí)，出棧第一個(gè)數(shù)作為運(yùn)算符后的參數(shù)，出棧第二個(gè)參數(shù)作為運(yùn)算符前的參數(shù)，將結(jié)果再壓入棧中。
1.3 棧的數(shù)組實(shí)現(xiàn)
在 Java 中棧的底層其實(shí)是一個(gè)數(shù)組，并且它擁有壓棧、出棧等等方法，借助這些我們來自己實(shí)現(xiàn)一個(gè)棧
public class MyStack{
// 定義一個(gè)整型的數(shù)組，也可以直接使用泛型
public int[] elem;
// 定義數(shù)組已經(jīng)使用的長(zhǎng)度，初始時(shí)為0
public int usedSize;
// 創(chuàng)建 MyStack 的構(gòu)造方法
public MyStack(){
// 用 Mystack 創(chuàng)建對(duì)象時(shí)初始化數(shù)組的長(zhǎng)度為10
this.elem=new int[10];
}
// 判斷棧是否已滿
public boolean isFull(){
return usedSize==this.elem.length;
}
// 壓棧
public int push(int val){
if(isFull()){
// 擴(kuò)容
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize++]=val;
return val;
}
// 出棧
public int pop(){
if(empty()){
throw new RuntimeException("棧為空");
}
this.usedSize--;
return this.elem[this.usedSize];
}
// 查看棧頂元素，不刪除
public int peek(){
if(empty()){
throw new RuntimeException("棧為空");
}
return this.elem[this.usedSize-1];
}
// 判斷棧是否為空
public boolean empty(){
return usedSize==0;
}
}
1.4 問題
我們上述的棧是用數(shù)組實(shí)現(xiàn)的，入棧和出棧的時(shí)間復(fù)雜度都為 O(1)
那么棧能否用單鏈表實(shí)現(xiàn)呢？
- 使用頭插法：入棧時(shí)間復(fù)雜度為 O(1)，出棧時(shí)間復(fù)雜度為 O(1)
- 使用尾插法：入棧時(shí)間復(fù)雜度為 O(N)，出棧時(shí)間復(fù)雜度為 O(N)
綜上分析，棧可以通過單鏈表的頭插頭刪法實(shí)現(xiàn)
1.5 棧的單鏈表實(shí)現(xiàn)
接下來將使用單鏈表實(shí)現(xiàn)棧，注意要使用頭插頭刪法
class Node{
public int val;
public Node next;
public Node(int val){
this.val=val;
}
}
public class MyStack{
Node head=null;
// 壓棧
public int push(int val){
Node node=new Node(val);
node.next = head;
head = node;
return head.val;
}
// 出棧
public int pop(){
if(empty()){
throw new RuntimeException("棧為空");
}
int val=head.val;
head=head.next;
return val;
}
// 查看棧頂元素，不刪除
public int peek(){
if(empty()){
throw new RuntimeException("棧為空");
}
return head.val;
}
// 判斷棧是否為空
public boolean empty(){
return head==null;
}
}
2. 隊(duì)列
2.1 概念
- 隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除操作的特殊線性表。
- 特點(diǎn)：隊(duì)列具有先進(jìn)先出的特點(diǎn)
- 對(duì)頭：進(jìn)行刪除操作的一端
- 隊(duì)尾：進(jìn)行插入操作的一段
2.2 問題
在我們實(shí)現(xiàn)隊(duì)列前，要思考隊(duì)列是靠數(shù)組實(shí)現(xiàn)呢還是拿鏈表實(shí)現(xiàn)呢？
在 Java 當(dāng)中，隊(duì)列是由 LinkedList 實(shí)現(xiàn)的，它的底層是一個(gè)雙向鏈表。
- 對(duì)于雙向鏈表：我們只要在尾節(jié)點(diǎn)進(jìn)行入隊(duì)操作，在頭節(jié)點(diǎn)進(jìn)行出隊(duì)操作就很容易實(shí)現(xiàn)
- 對(duì)于單鏈表：我們只要增加一個(gè)尾巴節(jié)點(diǎn)，然后尾巴節(jié)點(diǎn)進(jìn)行入隊(duì)操作，頭節(jié)點(diǎn)進(jìn)行出隊(duì)操作也能實(shí)現(xiàn)
至于數(shù)組，我們上述通過它實(shí)現(xiàn)了棧，而棧的特點(diǎn)其實(shí)是先進(jìn)后出，與隊(duì)列的先進(jìn)先出原則矛盾。使用數(shù)組來實(shí)現(xiàn)隊(duì)列會(huì)很麻煩。
2.3 隊(duì)列的單鏈表實(shí)現(xiàn)
根據(jù) Java 中隊(duì)列的一些方法，接下來我們來實(shí)現(xiàn)自己的隊(duì)列
class Node{
public int val;
public Node next;
public Node(int val){
this.val=val;
}
}
public class MyQueueLinked {
private Node front;
private Node rear;
private int usedSize;
// 入隊(duì)列
public void offer(int val){
Node node=new Node(val);
if(this.front==null){
this.front=node;
this.rear=node;
}else{
this.rear.next=node;
this.rear=node;
}
this.usedSize++;
}
// 出隊(duì)列
public int poll(){
if(isEmpty()){
throw new RuntimeException("隊(duì)列為空");
}
int val=this.front.val;
if(this.front.next==null){
this.front=null;
this.rear=null;
}else{
this.front=this.front.next;
}
this.usedSize--;
return val;
}
// 得到隊(duì)頭元素不刪除
public int peek(){
if(isEmpty()){
throw new RuntimeException("隊(duì)列為空");
}else{
return this.front.val;
}
}
// 判斷隊(duì)列是否為空
public boolean isEmpty(){
return this.usedSize==0;
}
// 得到隊(duì)列長(zhǎng)度
public int size(){
return this.usedSize;
}
}
上述隊(duì)列是用單鏈表實(shí)現(xiàn)的，也叫鏈?zhǔn)疥?duì)列。大家也可以自行嘗試一下雙鏈表實(shí)現(xiàn)隊(duì)列。
2.4 數(shù)組實(shí)現(xiàn)隊(duì)列
假設(shè)現(xiàn)在我們用數(shù)組模擬入隊(duì)列和出隊(duì)列的模型
解決方法：
- 方法一：出隊(duì)時(shí)，移動(dòng)數(shù)組將后面的元素往前覆蓋（時(shí)間復(fù)雜度為 O(N)）
- 方法二：使用循環(huán)的方法，實(shí)現(xiàn)循環(huán)隊(duì)列（時(shí)間復(fù)雜度為 O(1)）
2.5 循環(huán)隊(duì)列
循環(huán)隊(duì)列即數(shù)組使用了循環(huán)的方式，讓數(shù)組方便隊(duì)列的入隊(duì)和出隊(duì)。那么怎么實(shí)現(xiàn)呢？模型如下
- front：指向的位置就是隊(duì)列的頭，既已經(jīng)存放數(shù)據(jù)的第一個(gè)下標(biāo)（刪除數(shù)據(jù)一端）
- rear：指向的位置就是隊(duì)列的尾巴，即可以存放數(shù)據(jù)的第一個(gè)下標(biāo)（插入數(shù)據(jù)一端）
問題1：如何判斷 front = rear 時(shí)是空還是滿？
為了能夠區(qū)別是空還是滿，我們常假定當(dāng) front = rear 時(shí)為空。而對(duì)于滿的話，我們則會(huì)將這個(gè)數(shù)組保留一個(gè)空的位置，那么當(dāng) rear+1 = front 時(shí)，則隊(duì)列滿了
問題2：當(dāng) front 在數(shù)組最后一個(gè)位置時(shí)，如何再移它到數(shù)組的第一個(gè)位置呢？
(下標(biāo)+1)%數(shù)組長(zhǎng)度
接下來讓我們實(shí)現(xiàn)循環(huán)隊(duì)列
public class MyCircularQueue {
private int[] elem;
private int front;
private int rear;
public MyCircularQueue(int k){
this.elem=new int[k+1];
}
// 判斷隊(duì)列是否滿了
public boolean isFull(){
return (this.rear+1)%this.elem.length==this.front;
}
// 判斷隊(duì)列是否為空
public boolean isEmpty(){
return this.front==this.rear;
}
// 入隊(duì)
public void enQueue(int val){
if(isFull()){
this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.rear]=val;
this.rear=(this.rear+1)%this.elem.length;
}
// 出隊(duì)
public int deQueue(){
if(isEmpty()){
throw new RuntimeException("隊(duì)列為空");
}
int val=this.elem[this.front];
this.front=(this.front+1)%this.elem.length;
return val;
}
// 得到隊(duì)頭元素
public int getFront(){
if(isEmpty()){
throw new RuntimeException("隊(duì)列為空");
}
return this.elem[this.front];
}
// 得到隊(duì)尾元素
public int getRear(){
if(isEmpty()){
throw new RuntimeException("隊(duì)列為空");
}
if(this.rear==0){
return this.elem[this.elem.length-1];
}
return this.elem[this.rear - 1];
}
}
注意：
假設(shè)一個(gè)數(shù)組長(zhǎng)度為3，做題時(shí)可能人家用例入隊(duì)了3次，但是按照上述隊(duì)列為滿的方式，我們其實(shí)是保留了一個(gè)位置是不能存放數(shù)據(jù)的。因此對(duì)于這種題目我們可以將我們的數(shù)組開大一位
2.6 雙端隊(duì)列
- 雙端隊(duì)列：是指允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列
- 特點(diǎn)：元素可以從隊(duì)頭出隊(duì)和入隊(duì)，也可以從隊(duì)尾出隊(duì)和入隊(duì)
雙端隊(duì)列較簡(jiǎn)單，可以使用雙向鏈表實(shí)現(xiàn)，這里就展示一下雙端隊(duì)列的模型
3. 棧和隊(duì)列練習(xí)題
3.1 有效的括號(hào)
題目（OJ 鏈接）：
給定一個(gè)只包括 ‘('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：左括號(hào)必須用相同類型的右括號(hào)閉合，左括號(hào)必須以正確的順序閉合。
題解：使用棧，遍歷字符串，是左括號(hào)就進(jìn)行入棧，是右括號(hào)就與棧頂元素比較。
public boolean isValid(String s) {
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
switch(ch){
case ')':
if(stack.empty()||stack.pop()!='('){
return false;
}
break;
case '}':
if(stack.empty()||stack.pop()!='{'){
return false;
}
break;
case ']':
if(stack.empty()||stack.pop()!='['){
return false;
}
break;
default:
stack.push(ch);
break;
}
}
if(stack.empty()){
return true;
}
return false;
}
3.2 用隊(duì)列實(shí)現(xiàn)棧
題目（OJ鏈接）：
請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
題解：
由于隊(duì)列是先進(jìn)先出，棧是先進(jìn)后出，故一個(gè)隊(duì)列無法滿足實(shí)現(xiàn)棧的能力。而使用兩個(gè)隊(duì)列，對(duì)于入棧，我們我只要找到棧不為空的隊(duì)列進(jìn)行入隊(duì)就行；對(duì)于出棧，我們只要將不為空的隊(duì)列的除最后一個(gè)入隊(duì)的元素全部轉(zhuǎn)移到另一個(gè)空隊(duì)列中，再將留下的元素出隊(duì)
代碼：
class MyStack {
private Queue<Integer> q1;
private Queue<Integer> q2;
public MyStack() {
q1=new LinkedList<>();
q2=new LinkedList<>();
}
// 入棧
public void push(int x) {
if(!q1.isEmpty()){
q1.offer(x);
}else if(!q2.isEmpty()){
q2.offer(x);
}else{
q1.offer(x);
}
}
// 出棧
public int pop() {
if(empty()){
throw new RuntimeException("棧為空");
}
if(!q1.isEmpty()){
int val1=0;
while(!q1.isEmpty()){
val1=q1.poll();
if(!q1.isEmpty()){
q2.offer(val1);
}
}
return val1;
}else{
int val2=0;
while(!q2.isEmpty()){
val2=q2.poll();
if(!q2.isEmpty()){
q1.offer(val2);
}
}
return val2;
}
}
// 得到棧頂元素不刪除
public int top() {
if(empty()){
throw new RuntimeException("棧為空");
}
if(!q1.isEmpty()){
int val1=0;
while(!q1.isEmpty()){
val1=q1.poll();
q2.offer(val1);
}
return val1;
}else{
int val2=0;
while(!q2.isEmpty()){
val2=q2.poll();
q1.offer(val2);
}
return val2;
}
}
// 判斷棧是否為空
public boolean empty() {
return q1.isEmpty()&&q2.isEmpty();
}
}
3.3 用棧實(shí)現(xiàn)隊(duì)列
題目（OJ 鏈接）：
請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。
題解：
我們可以創(chuàng)建兩個(gè)棧 s1、s2，s1 用來入隊(duì)，s2 用來出隊(duì)
代碼：
class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public MyQueue() {
s1=new Stack<>();
s2=new Stack<>();
}
// 入隊(duì)
public void push(int x) {
s1.push(x);
}
// 出隊(duì)
public int pop() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
// 返回隊(duì)首元素，不刪除
public int peek() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
// 判斷隊(duì)列是否為空
public boolean empty() {
return s1.empty()&&s2.empty();
}
}
3.4 實(shí)現(xiàn)一個(gè)最小棧
題目（OJ 鏈接）：
設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
題解：
我們可以創(chuàng)建兩個(gè)棧，一個(gè)棧就是用來存儲(chǔ)刪除元素，另一個(gè)就是專門用來存儲(chǔ)最小值的棧。注意這個(gè)最小值是存儲(chǔ)該元素時(shí)該棧的最小值
代碼：
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack=new Stack<>();
minStack=new Stack<>();
}
// 入棧
public void push(int val) {
stack.push(val);
if(minStack.empty()){
minStack.push(val);
}else{
if(val<=minStack.peek()){
minStack.push(val);
}
}
}
// 出棧
public void pop() {
int val=stack.pop();
if(minStack.peek()==val){
minStack.pop();
}
}
// 得到棧頂元素，不刪除
public int top() {
return stack.peek();
}
// 得到此時(shí)棧的最小值
public int getMin() {
return minStack.peek();
}
}
3.5 設(shè)計(jì)循環(huán)隊(duì)列
題目（OJ 鏈接）：
設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)。 循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱為“環(huán)形緩沖器”。
題解：
通過 (下標(biāo)+1)%數(shù)組長(zhǎng)度 的方式將數(shù)組形成一個(gè)循環(huán)，先設(shè)定好數(shù)組為空和為滿的條件。注意防止題目將數(shù)組存滿，開數(shù)組時(shí)的大小要注意。
代碼：
class MyCircularQueue {
private int[] elem;
private int front;
private int rear;
public MyCircularQueue(int k) {
this.elem=new int[k+1];
}
// 入隊(duì)列
public boolean enQueue(int value) {
if(isFull()){
return false;
}
this.elem[rear]=value;
this.rear=(this.rear+1)%this.elem.length;
return true;
}
// 出隊(duì)列
public boolean deQueue() {
if(isEmpty()){
return false;
}
this.front=(this.front+1)%this.elem.length;
return true;
}
// 得到隊(duì)首元素，不刪除
public int Front() {
if(isEmpty()){
return -1;
}
return this.elem[front];
}
// 得到隊(duì)尾元素，不刪除
public int Rear() {
if(isEmpty()){
return -1;
}
if(this.rear==0){
return this.elem[this.elem.length-1];
}
return this.elem[this.rear-1];
}
// 判斷隊(duì)列是否為空
public boolean isEmpty() {
return this.rear==this.front;
}
// 判斷隊(duì)列是否滿了
public boolean isFull() {
return (this.rear+1)%this.elem.length==this.front;
}
}
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)專題解析之棧和隊(duì)列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java 棧和隊(duì)列的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java并發(fā)編程：CountDownLatch與CyclicBarrier和Semaphore的實(shí)例詳解
這篇文章主要介紹了Java并發(fā)編程：CountDownLatch與CyclicBarrier和Semaphore的實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-09-09
Spring boot項(xiàng)目使用thymeleaf模板過程詳解
這篇文章主要介紹了Spring boot項(xiàng)目使用thymeleaf模板過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了RocketMQ中的消息發(fā)送與消費(fèi)詳解,RocketMQ是一款高性能、高可靠性的分布式消息中間件,消費(fèi)者是RocketMQ中的重要組成部分,消費(fèi)者負(fù)責(zé)從消息隊(duì)列中獲取消息并進(jìn)行處理,需要的朋友可以參考下2023-10-10
這篇文章主要為大家詳細(xì)介紹了Java堆排序算法的相關(guān)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-09-09
Eclipse插件開發(fā)實(shí)現(xiàn)控制臺(tái)輸出信息的方法
今天小編就為大家分享一篇關(guān)于Eclipse插件開發(fā)實(shí)現(xiàn)控制臺(tái)輸出信息的方法，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-01-01
這篇文章主要為大家詳細(xì)介紹了java原碼補(bǔ)碼反碼的關(guān)系，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
使用Spring方法攔截器MethodInterceptor
這篇文章主要介紹了使用Spring方法攔截器MethodInterceptor，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
詳解Java中的數(shù)組與字符串相關(guān)知識(shí)
這篇文章主要介紹了詳解Java中的數(shù)組與字符串相關(guān)知識(shí),包括操作字符串的一些基本方法列舉,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了IO流相關(guān)知識(shí)，包括File，字節(jié)流，字符流，特殊操作流（標(biāo)準(zhǔn)輸入流，標(biāo)準(zhǔn)輸出流，對(duì)象序列化與反序列化，properties與IO流結(jié)合）相關(guān)知識(shí)的總結(jié)2021-08-08
用Rational Rose逆向工程(java)生成類圖(教程和錯(cuò)誤解決)
Rational Rose有個(gè)很方便的功能，將項(xiàng)目中的JAVA代碼自動(dòng)轉(zhuǎn)換成UML類圖2013-02-02