Java數(shù)據(jù)結(jié)構(gòu)專(zhuān)題解析之棧和隊(duì)列的實(shí)現(xiàn)
1. 棧
1.1 概念
- 棧:是一種特殊的線(xiàn)性表,其只允許在固定的一端進(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í)就類(lèi)似是一個(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)算(如二叉樹(shù)、堆棧的方法計(jì)算)
- 題三: 通過(guò)棧返回后綴表達(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ù)組,并且它擁有壓棧、出棧等等方法,借助這些我們來(lái)自己實(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];
}
// 判斷棧是否已滿(mǎn)
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 問(wèn)題
我們上述的棧是用數(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)
綜上分析,棧可以通過(guò)單鏈表的頭插頭刪法實(shí)現(xiàn)
1.5 棧的單鏈表實(shí)現(xiàn)
接下來(lái)將使用單鏈表實(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)行刪除操作的特殊線(xiàn)性表。
- 特點(diǎn):隊(duì)列具有先進(jìn)先出的特點(diǎn)
- 對(duì)頭:進(jìn)行刪除操作的一端
- 隊(duì)尾:進(jìn)行插入操作的一段

2.2 問(wèn)題
在我們實(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ù)組,我們上述通過(guò)它實(shí)現(xiàn)了棧,而棧的特點(diǎn)其實(shí)是先進(jìn)后出,與隊(duì)列的先進(jìn)先出原則矛盾。使用數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列會(huì)很麻煩。
2.3 隊(duì)列的單鏈表實(shí)現(xiàn)
根據(jù) Java 中隊(duì)列的一些方法,接下來(lái)我們來(lái)實(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ù)一端)
問(wèn)題1:如何判斷 front = rear 時(shí)是空還是滿(mǎn)?
為了能夠區(qū)別是空還是滿(mǎn),我們常假定當(dāng) front = rear 時(shí)為空。而對(duì)于滿(mǎn)的話(huà),我們則會(huì)將這個(gè)數(shù)組保留一個(gè)空的位置,那么當(dāng) rear+1 = front 時(shí),則隊(duì)列滿(mǎn)了

問(wèn)題2:當(dāng) front 在數(shù)組最后一個(gè)位置時(shí),如何再移它到數(shù)組的第一個(gè)位置呢?
(下標(biāo)+1)%數(shù)組長(zhǎng)度
接下來(lái)讓我們實(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ì)列是否滿(mǎn)了
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ì)列為滿(mǎn)的方式,我們其實(shí)是保留了一個(gè)位置是不能存放數(shù)據(jù)的。因此對(duì)于這種題目我們可以將我們的數(shù)組開(kāi)大一位
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 ,判斷字符串是否有效。
有效字符串需滿(mǎn)足:左括號(hào)必須用相同類(lèi)型的右括號(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ì)列無(wú)法滿(mǎn)足實(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 用來(lái)入隊(duì),s2 用來(lái)出隊(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è)棧就是用來(lái)存儲(chǔ)刪除元素,另一個(gè)就是專(zhuān)門(mén)用來(lái)存儲(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ì)列是一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu),其操作表現(xiàn)基于 FIFO(先進(jìn)先出)原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)。它也被稱(chēng)為“環(huán)形緩沖器”。
題解:
通過(guò) (下標(biāo)+1)%數(shù)組長(zhǎng)度 的方式將數(shù)組形成一個(gè)循環(huán),先設(shè)定好數(shù)組為空和為滿(mǎn)的條件。注意防止題目將數(shù)組存滿(mǎn),開(kāi)數(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ì)列是否滿(mǎn)了
public boolean isFull() {
return (this.rear+1)%this.elem.length==this.front;
}
}
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)專(zhuān)題解析之棧和隊(duì)列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java 棧和隊(duì)列的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Java 棧與隊(duì)列超詳細(xì)分析講解
- Java?棧與隊(duì)列實(shí)戰(zhàn)真題訓(xùn)練
- 一起來(lái)學(xué)習(xí)Java的棧和隊(duì)列
- Java棧和基礎(chǔ)隊(duì)列的實(shí)現(xiàn)詳解
- Java 棧和隊(duì)列的相互轉(zhuǎn)換詳解
- Java深入了解數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列的詳解
- Java數(shù)據(jù)結(jié)構(gòu)之棧與隊(duì)列實(shí)例詳解
- Java使用跳轉(zhuǎn)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列和棧流程詳解
相關(guān)文章
java實(shí)現(xiàn)簡(jiǎn)單快遞系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)簡(jiǎn)單快遞系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03
mybatis中的if?test判斷入?yún)⒌闹祮?wèn)題
這篇文章主要介紹了mybatis中的if?test判斷入?yún)⒌闹祮?wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-06-06
java設(shè)計(jì)模式之單例模式的詳解及優(yōu)點(diǎn)
這篇文章主要介紹了java設(shè)計(jì)模式之單例模式的詳解及優(yōu)點(diǎn)的相關(guān)資料,如果一個(gè)類(lèi)始終只能創(chuàng)建一個(gè)實(shí)例,那么這個(gè)類(lèi)被稱(chēng)為單例類(lèi),這種設(shè)計(jì)模式被稱(chēng)為單例模式,需要的朋友可以參考下2017-08-08
Spring BeanName 的自動(dòng)生成原理示例詳解
這篇文章主要介紹了Spring BeanName 的自動(dòng)生成原理示例詳解,本文通過(guò)示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-09-09
詳解spring中使用Elasticsearch的代碼實(shí)現(xiàn)
本篇文章主要介紹了詳解spring中使用Elasticsearch的代碼實(shí)現(xiàn),具有一定的參考價(jià)值,有興趣的可以了解一下2017-05-05

