一.棧（Stack）

1.定義

棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表

一般的表尾稱為棧頂? ? ? 表頭稱為棧底

棧具有“后進(jìn)先出”的特點(diǎn)

2.對(duì)棧的模擬

棧主要具有以下功能：

• push(Object item)：將元素item壓入棧頂。

• pop()：彈出棧頂元素，并將其從棧中刪除。

• peek()：返回棧頂元素，但不刪除它。

• isEmpty()：判斷棧是否為空，返回布爾值。具體模擬代碼我們可以用一個(gè)順序表來(lái)實(shí)現(xiàn)如下

而在Java 編程應(yīng)用idea中我們?cè)谑褂脮r(shí)無(wú)需再進(jìn)行模擬實(shí)現(xiàn)，可直接通過(guò)棧的實(shí)例化? 然后直接進(jìn)行調(diào)用棧的不同方法

實(shí)例化一個(gè)存儲(chǔ)字符串類型的棧

則可直接stack.pop（）....進(jìn)行調(diào)用方法

3.括號(hào)匹配問(wèn)題

鏈接如下：?

20. 有效的括號(hào) - 力扣（LeetCode）

該題目就需要我們對(duì)于棧的功能的熟練掌握

需我們考慮三種括號(hào)不匹配情況從而考慮入棧和出棧的適配問(wèn)題

以下是代碼：

二.隊(duì)列（Queue）

1.定義

與棧相反，隊(duì)列是一種先進(jìn)先出的線性表

插入一端成為隊(duì)尾，刪除一端稱為隊(duì)頭

2.對(duì)隊(duì)列的模擬

隊(duì)列具有以下功能：

• 1. offer(E e)：添加元素到隊(duì)列
  2.poll()：移除并返回隊(duì)列頭部的元素
• 3. peek()：獲取隊(duì)列頭部的元素，但不移除
  4.isEmpty()：檢查隊(duì)列是否為空

以下隊(duì)列的模擬我是借助鏈表來(lái)進(jìn)行模擬實(shí)現(xiàn)

Java中idea也具有Queue隊(duì)列 但隊(duì)列是作為一個(gè)抽象類 所以

在實(shí)例化對(duì)象時(shí)需要向上轉(zhuǎn)型

則可進(jìn)行調(diào)用隊(duì)列的方法：queue.offer();....

3.循環(huán)隊(duì)列

循環(huán)隊(duì)列是隊(duì)列的一大重點(diǎn)

與隊(duì)列不同的就是需要考慮隊(duì)尾與對(duì)頭的銜接

1.注意隊(duì)空與隊(duì)滿的判斷條件

隊(duì)空的條件：q.front==q.rear;

隊(duì)滿的條件：(q.rear+1)%MaxSize==q.front;

2.代碼詳解

三.棧對(duì)隊(duì)列的模擬以及隊(duì)列對(duì)棧的模擬

1.隊(duì)列對(duì)棧的模擬

225. 用隊(duì)列實(shí)現(xiàn)棧 - 力扣（LeetCode）

class MyStack {

Queue<Integer>queue1 ;//申請(qǐng)第一個(gè)隊(duì)列

Queue<Integer>queue2 ;//申請(qǐng)第二個(gè)隊(duì)列

? ? public MyStack() {

? ? ? ? queue1=new LinkedList<>();

? ? ? ? queue2=new LinkedList<>();

? ? }

? ?

? ? public void push(int x) {//在模擬棧入隊(duì)時(shí) 找兩個(gè)隊(duì)列中非空的隊(duì)列

? ? ? ? if(!queue1.isEmpty()){

? ? ? ? ? ? queue1.offer(x);

? ? ? ? }

? ? ? ? else if(!queue2.isEmpty()){

? ? ? ? ? ? queue2.offer(x);

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? queue1.offer(x);

? ? ? ? }

? ? }

? ?

? ? public int pop() {//出隊(duì)列時(shí)將非空隊(duì)列中size-1個(gè)元素入另一個(gè)隊(duì)列中，留下的即為模擬棧該出棧的元素

? ? ? ? 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 val=0;

? ? ? ? ? ? int size=queue1.size();

? ? ? ? ? for(int i=0;i<size;i++){

? ? ? ? ? ? val=queue1.poll();

? ? ? ? ? ? queue2.offer(val);

? ? ? ? ? }

? ? ? ? ? return val;

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? int val=0;

? ? ? ? ? ? int size=queue2.size();

? ? ? ? ? for(int i=0;i<size;i++){

? ? ? ? ? ? val=queue2.poll();

? ? ? ? ? ? queue1.offer(val);

? ? ? ? ? }

? ? ? ? ? return val;

? ? ? ? }

? ? }

? ? public boolean empty() {

? ? ? ? return queue1.isEmpty()&&queue2.isEmpty();

? ? }

}

2.棧對(duì)隊(duì)列的模擬

232. 用棧實(shí)現(xiàn)隊(duì)列 - 力扣（LeetCode）

注意結(jié)合棧的特性以兩個(gè)棧來(lái)結(jié)合使隊(duì)列的先進(jìn)后出成功進(jìn)行

class MyQueue {

public Stack <Integer> ?stack1;

public Stack <Integer> stack2;

? ? public MyQueue() {

? ? ? ? stack1=new Stack<>();

? ? ? ? stack2=new Stack<>();

? ? }

? ?

? ? public void push(int x) {

? ? ? ? if(empty()){

? ? ? ? ? ? stack1.push(x);

? ? ? ? }

? ? ? ? if(stack1.isEmpty()){

? ? ? ? ? ? stack2.push(x);

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? stack1.push(x);

? ? ? ? }

? ? }

? ? public int pop() {

? ? ? ? if(empty()){

? ? ? ? ? ? return -1;

? ? ? ? }

? ? ? ? if(!stack2.isEmpty()){

? ? ? ? ? ? return stack2.pop();

? ? ? ? }

? ? ? ? else{

? ? ? ? ?while(!stack1.isEmpty()){

? ? ? ? ? ? ? stack2.push(stack1.pop());

? ? ? ? ? ? }

? ? ? ? ? ? return stack2.pop();

? ? ? ? }

? ? }

? ?

? ? public int peek() {

? ? ? ? if(empty()){

? ? ? ? ? ? return -1;

? ? ? ? }

? ? ? ? if(stack1.isEmpty()){

? ? ? ? ? ? ?int sz=stack2.size();

? ? ? ? ? ? int num=0;

? ? ? ? ? ? for(int i=0;i<sz;i++){

? ? ? ? ? ? ? ? num=stack2.pop();

? ? ? ? ? ? ? stack1.push(num);

? ? ? ? ? ? }

? ? ? ? ? ? return stack1.peek();

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? int sz=stack1.size();

? ? ? ? ? ? int num=0;

? ? ? ? ? ? for(int i=0;i<sz;i++){

? ? ? ? ? ? ? ? num=stack1.pop();

? ? ? ? ? ? ? stack2.push(num);

? ? ? ? ? ? }

? ? ? ? ? ? return stack2.peek();

? ? ? ? }

? ? }

? ?

? ? public boolean empty() {

? ? ? ? return stack1.isEmpty()&&stack2.isEmpty();

? ? }

}