劍指Offer系列(java版,詳細解析)09.用兩個棧實現隊列

程序員社區 2022-01-08 04:42:37 阅读数:574

offer 系列 java 解析

題目描述

劍指 Offer 09. 用兩個棧實現隊列

難度簡單190

用兩個棧實現一個隊列。隊列的聲明如下,請實現它的兩個函數 appendTaildeleteHead ,分別完成在隊列尾部插入整數和在隊列頭部删除整數的功能。(若隊列中沒有元素,deleteHead 操作返回 -1 )

示例 1:

輸入:["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]輸出:[null,null,3,-1]

示例 2:

輸入:["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]輸出:[null,-1,null,null,5,2]

提示:

  • 1 <= values <= 10000
  • 最多會對 appendTail、deleteHead 進行 10000 次調用

隊列的聲明如下:

/** * 構建隊列的聲明 */public class BuildQueue {
 Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) {
 } public int pop() {
 }}

測試用例

  • 往空的隊列添加、删除元素。
  • 往非空的隊列、添加删除元素。
  • 連續删除元素直至隊列為空。

題目考點

  • 考察應聘者對棧和隊列的理解。
  • 考察應聘者分析複雜問題的能力。(找規律)

解題思路

假設元素先進stack1棧,如果這個時候需要彈出元素時,分為兩種情况:當stack2棧為空時,我們把stack1棧的元素逐個彈出並壓入stack2棧,此時我們會發現最先進入的元素已經在stack2棧頂,可以直接彈出;當stack2棧不為空,在stack2中的棧頂元素就是最先進入隊列的元素,可以彈出。

參考解題

class CQueue {
 LinkedList<Integer> A, B; public CQueue() {
 A = new LinkedList<Integer>(); B = new LinkedList<Integer>(); } public void appendTail(int value) {
 A.addLast(value); } public int deleteHead() {
 if(!B.isEmpty()) return B.removeLast(); if(A.isEmpty()) return -1; while(!A.isEmpty()) B.addLast(A.removeLast()); return B.removeLast(); }}
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080442367542.html