Java 棧和隊列的交互實現
隊列和棧的區(qū)別
棧和隊列都是常用的數據結構，它們的主要區(qū)別在于數據的插入和刪除順序。
棧 (Stack) 是一種后進先出 (Last-In-First-Out, LIFO) 的數據結構，只允許在一端進行插入和刪除操作，這一端稱為棧頂。新元素插入后成為新的棧頂，而刪除時也只能刪除棧頂元素。
隊列 (Queue) 是一種先進先出 (First-In-First-Out, FIFO) 的數據結構，允許在兩端進行插入和刪除操作，插入在隊尾，刪除在隊頭。新元素插入時成為新的隊尾，而刪除時也只能刪除隊頭元素。
一.用隊列模擬實現棧
1.void push(int x) 將元素 x 壓入棧頂。
2.int pop() 移除并返回棧頂元素。
3.int top() 返回棧頂元素。
4.boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。
如上便是需要用隊列來實現棧的四個基本操作。
我們試想，實現這些棧的操作，一個隊列可以完成嗎？
顯然不可以，我們使用兩個隊列來實現棧的模擬
大體流程
1.入棧時：
如果兩個都為空，那么想
1.1入棧
當我們要放入18 25 35 48 這一串數字入棧時，先放入18 25 35（放入時選擇的隊列是不為空的隊列），模擬入隊以及入棧時的狀況，如下圖
public void push(int x) {
if(empty()){
queue1.offer(x);
return;
}
if(!queue1.isEmpty()){
queue1.offer(x);
}else {
queue2.offer(x);
}
}
1.2出棧
此時如果我們要將35出棧時，又該如何操作呢？此時我們就需要用到第二個隊列，將隊列一的前size－1個元素（也就是18 25)從隊列一中出隊，放入隊列二中。此時隊列一中的元素為35，隊列二的元素為18 25 如下圖。
當初棧完成時，我們此時要將48入棧時，又該放入哪個棧中呢？我們考慮棧的特點（先入后出），我們將再入棧的元素放到不為空的隊列中。
public int pop() {
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
int size = queue1.size();
for (int i = 0; i < size-1; i++) {
queue2.offer(queue1.poll());
}
return queue1.poll();
}else {
int size = queue2.size();
for (int i = 0; i < size-1; i++) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
1.3返回棧頂元素
在實現pop的基礎上，我們將聲明一個變量temp來儲存每次要移除的元素。
public int top() {
if(empty()){
return -1;
}
if (!queue1.isEmpty()){
int temp = -1;
int size = queue1.size();
for (int i = 0; i < size; i++) {
temp = queue1.poll();
queue2.offer(temp);
}
return temp;
}else {
int size = queue2.size();
int temp = -1;
for (int i = 0; i < size; i++) {
temp = queue2.poll();
queue1.offer(temp);
}
return temp;
}
}
1.4判斷棧是否為空
當隊列一和隊列二都為空時，此時棧就為空。
public boolean empty() {
return queue1.isEmpty()&&queue2.isEmpty();
}
二.用棧模擬實現隊列
我們也是用兩個棧來模擬實現隊列
2.1 入隊
我們將所有入隊的元素都放入棧一中，如下圖
public void push(int x) {
stack1.push(x);
}
2.2出隊
要出棧時，如果棧二不為空，就出棧二中的元素，如果棧二為空，將棧一中的所有元素一次性的全部push到棧二中，此時就將入棧的元素全部倒轉過來了,(例如入棧時在棧中的入棧順序依次排序為18 25 35，棧二中此時的元素入棧順序是35 25 18，出棧時就先出18,就完成了轉換）如下圖
public int pop() {
if(empty()){
return -1;
}
if (stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
2.3peek
peek只是將出隊時的pop換成peek，就可以完成要求。
public int peek() {
if(empty()){
return -1;
}
if (stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
2.4判斷隊列是否為空
如果棧一和棧二都為空時，那么隊列就為空。
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
三.完整代碼
3.1 隊列模擬實現棧
class MyStack {
Queue<Integer> queue1 ;
Queue<Integer> queue2 ;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
if(empty()){
queue1.offer(x);
return;
}
if(!queue1.isEmpty()){
queue1.offer(x);
}else {
queue2.offer(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
int size = queue1.size();
for (int i = 0; i < size-1; i++) {
queue2.offer(queue1.poll());
}
return queue1.poll();
}else {
int size = queue2.size();
for (int i = 0; i < size-1; i++) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
public int top() {
if(empty()){
return -1;
}
if (!queue1.isEmpty()){
int temp = -1;
int size = queue1.size();
for (int i = 0; i < size; i++) {
temp = queue1.poll();
queue2.offer(temp);
}
return temp;
}else {
int size = queue2.size();
int temp = -1;
for (int i = 0; i < size; i++) {
temp = queue2.poll();
queue1.offer(temp);
}
return temp;
}
}
public boolean empty() {
return queue1.isEmpty()&&queue2.isEmpty();
}
}
3.2棧模擬實現隊列
class MyQueue {
public Stack<Integer> stack1 ;
public Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(empty()){
return -1;
}
if (stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if(empty()){
return -1;
}
if (stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}到此這篇關于Java 棧和隊列的交互實現的文章就介紹到這了,更多相關Java 棧和隊列交互內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了IDEA的.idea文件夾和iml文件使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
Eclipse/MyEclipse轉IntelliJ IDEA完全攻略(圖文)
這篇文章主要介紹了Eclipse/MyEclipse轉IntelliJ IDEA完全攻略(圖文)，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-01-01
這篇文章主要介紹了jdbc中class.forname的作用，使用示例說明了他作用及使用方法，大家參考使用吧2014-01-01
mybatis-generator自動生成dao、mapping、bean配置操作
這篇文章主要介紹了mybatis-generator自動生成dao、mapping、bean配置操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08
這篇文章主要介紹了在java面試過程中hibernate比較常見的問題，包括Hibernate的檢索方式，Hibernate中對象的狀態(tài)，Hibernate的3種檢索策略是什么，Session的find()方法以及Query接口的區(qū)別等方面問題的總結,需要的朋友可以參考下2015-07-07
這篇文章主要介紹了Java基于余弦方法實現的計算相似度算法,簡單說明了余弦相似性的概念、原理并結合實例形式分析了java實現余弦相似性算法的相關操作技巧,需要的朋友可以參考下2017-08-08
這篇文章主要介紹了spring如何使用命名空間p簡化bean的配置,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-01-01
Java源碼解析阻塞隊列ArrayBlockingQueue介紹
今天小編就為大家分享一篇關于Java源碼解析阻塞隊列ArrayBlockingQueue介紹，小編覺得內容挺不錯的，現在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
這篇文章主要介紹了JavaScript中Map用法的相關資料,通過實例講解了Map的創(chuàng)建、常用方法和迭代方式,還探討了Map與對象的區(qū)別,并通過一個例子展示了如何使用Map來統計字符出現的次數,需要的朋友可以參考下2025-03-03
本文主要介紹了java如何實現獲取客戶端ip地址，主要包括java獲取客戶端ip地址工具類使用實例、應用技巧，文中通過示例代碼介紹的非常詳細，感興趣的小伙伴們可以參考一下2022-04-04