【問(wèn)題描述】[簡(jiǎn)單]

用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒(méi)有元素，deleteHead 操作返回 -1 )示例 1：輸入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 輸出：[null,null,3,-1]

【解答思路】

一個(gè)棧添加元素 一個(gè)棧逆轉(zhuǎn)數(shù)組

時(shí)間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)

class CQueue { LinkedList<Integer> A, B;public CQueue() {A = new LinkedList<Integer>();B = new LinkedList<Integer>();}public void appendTail(int value) {A.offer(value);}public int deleteHead() {if(!B.isEmpty()){return B.poll();}if(A.isEmpty()){return -1;}while(!A.isEmpty()){B.add(A.poll());}return B.poll();} }

【總結(jié)】

1.棧使用LinkedList，不使用Stack（Stack繼承Vector，本質(zhì)數(shù)組，效率低）

參考文章https://mp.weixin.qq.com/s/Ba8jrULf8NJbENK6WGrVWg

2.LinkedList 基本使用

添加

刪除

獲取

隊(duì)列 offer/add poll/remove peek

棧 offer/push poll/pop peek


總結(jié)

3.兩個(gè)棧可以有很多擴(kuò)展

題目動(dòng)畫(huà)詳解參考鏈接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/

LinkedList參考鏈接：https://www.cnblogs.com/yijinqincai/p/10964188.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[09]题[用两个栈实现队列][LinkedList]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。