浅谈数据结构之栈和队列及基础算法和面试真题（一）

女爷i 2021-12-01 13:24 153阅读 0赞

### 浅谈数据结构之栈和队列及基础算法和面试真题（一） ###

*   *  基本概念
     *   *  栈
         *  队列
         *  栈和队列的比较
     *  栈的基本操作
     *  队列的基本操作
     *  面试真题---利用两个栈，实现一个队列

## 基本概念 ##

### 栈 ###

我们可以把栈看成一个箱子  
a. 往箱子里放东西叫作入栈  
b. 从箱子里取东西叫作出栈  
c. 箱子的底部叫作栈底  
d. 箱子的顶部叫作栈顶  
栈的特性： 先进后出  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]

### 队列 ###

我们可以将队列看成小朋友排队  
a.有小朋友到指定的地点了–>出队  
b.有新的小朋友加入了–>入队  
队列的特性：先进先出  
![在这里插入图片描述][2019072019390414.png]

### 栈和队列的比较 ###

**栈（Stack）和队列（Queue）是两种操作受限的线性表**。这种受限表现在：栈的插入和删除操作只允许在表的尾端进行（在栈中成为“栈顶”），满足“First In Last Out”；队列只允许在表尾插入数据元素，在表头删除数据元素,满足“First In First Out”。都可以通过顺序结构和链式结构实现。插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。  
**栈（Stack）应用场景：**  
a. 括号问题的求解  
b. 表达式的转换和求值  
c. 函数调用和递归实现  
d. 深度优先搜索遍历  
**队列（Queue）应用场景：**  
a. 计算机系统中各种资源的管理  
b. 消息缓冲器的管理  
c. 广度优先搜索遍历

## 栈的基本操作 ##

**栈的两种实现**

1.  静态栈（数组）
2.  动态栈 (链表)

**栈的基本操作方法**

1.  进栈
2.  出栈
3.  遍历
4.  清空
5.  判断是否为空

**代码实现**

public class ListNode { 
       public int value;
       public ListNode next;
       public ListNode(int value) { 
       	this.value = value;
       }
    }

public class MyStack { 
       
       //顶
       public ListNode stackTop;
       //底
       public ListNode stackBottom;
       public MyStack(ListNode stackTop, ListNode stackBottom) { 
       	this.stackTop = stackTop;
       	this.stackBottom = stackBottom;
       }
    
       /** * 入栈 * @param myStack * @param value */
       public static void pushStack(MyStack myStack, int value) { 
       	ListNode node = new ListNode(value);
       	node.next = myStack.stackTop;
       	myStack.stackTop = node;
       }
       
       /** * 遍历 * @param myStack */
       public static void traverse(MyStack myStack) { 
       	ListNode stackTop = myStack.stackTop;
       	if (stackTop != myStack.stackBottom) { 
       		System.out.println(stackTop.value);
       		stackTop = stackTop.next;
       	}
       }
       
       /** * 判空 * @param myStack * @return */
       public static boolean isEmpty(MyStack myStack) { 
       	return myStack.stackTop == myStack.stackBottom ? true : false;
       }
       
       /** * 出栈 * @param myStack */
       public static void popStack(MyStack myStack) { 
       	if (isEmpty(myStack)) { 
       		ListNode stackTop = myStack.stackTop;
       		myStack.stackTop = stackTop.next;
       		System.out.println(stackTop.value);
       	}
       }
       
       public static void clearStack(MyStack myStack) { 
       	myStack.stackTop = null;
       	myStack.stackBottom = myStack.stackTop;
       }
    }

## 队列的基本操作 ##

**队列的两种实现**

1.  静态队列 (数组)
2.  动态队列 (链表)

**队列的操作方法**

1.  入队
2.  出队
3.  遍历
4.  判断是否为满
5.  判断是否为空

**代码实现**

/** * 循环队列 */
    public class MyQueue { 
    	
    	public int[] arrays;
    	public int front;//指向是第一个有效元素
    	public int rear;//指向最后一个有效元素的下一个元素(即无效元素)
    	public MyQueue(int[] arrays, int front, int rear) { 
    		this.arrays = arrays;
    		this.front = front;
    		this.rear = rear;
    	}
    	
    	/** * 判满 * @param myQueue * @return */
    	public static boolean isFull(MyQueue myQueue) { 
    		if ((myQueue.rear + 1) % myQueue.arrays.length == myQueue.front) { 
    			return true;
    		} else { 
    			return false;
    		}
    	}
    	
    	/** * 判空 * @param myQueue * @return */
    	public static boolean isEmpty(MyQueue myQueue){ 
    		if (myQueue.front == myQueue.rear) { 
    			return true;
    		} else { 
    			return false;
    		}
    	}
    	
    	/** * 入队 * @param myQueue * @param value */
    	public static void enQueue(MyQueue myQueue, int value) { 
    		if (!isFull(myQueue)) { 
    			myQueue.arrays[myQueue.rear] = value;
    			myQueue.rear = (myQueue.rear + 1) % myQueue.arrays.length;
    		}
    	}
    	
    	/** * 遍历 * @param myQueue */
    	public static void traverse(MyQueue myQueue) { 
    		int i = myQueue.front;
    		if (i != myQueue.rear) { 
    			System.out.println(myQueue.arrays[i]);
    			i = (i+1) % myQueue.arrays.length;
    		}
    	}
    	
    	/** * 出队 */
    	public static void outQueue(MyQueue myQueue) { 
    		if (!isEmpty(myQueue)) { 
    			int value = myQueue.arrays[myQueue.front];
    			System.out.println(value);
    			myQueue.front = (myQueue.front + 1) % myQueue.arrays.length;
    		}
    	}
    
    }

## 面试真题—利用两个栈，实现一个队列 ##

**必须要实现两点**

1.  如果stackPush要往stackPop中压数据，必须一次性把stackPush中的数据全部压入。
2.  如果stackPop不为空，stackPush绝对不能向stackPop中压入数据。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]

import java.util.Stack;
    
    /** * 两个栈实现一个队列 * */
    public class TwoStackOneQueue { 
    
    	public Stack<Integer> stackPush;
    	
    	public Stack<Integer> stackPop;
    
    	public TwoStackOneQueue(Stack<Integer> stackPush, Stack<Integer> stackPop) { 
    		super();
    		this.stackPush = stackPush;
    		this.stackPop = stackPop;
    	}
    	
    	/** * 新增 * @param value */
    	public void add(int value) { 
    		stackPush.push(value);
    	}
    	
    	/** * 弹出元素 * @return */
    	public int poll() { 
    		if (stackPush.isEmpty() && stackPop.isEmpty()) { 
    			throw new RuntimeException("Queue is empty");
    		} else if (stackPop.isEmpty()) { 
    			while (!stackPush.isEmpty()) { 
    				stackPop.push(stackPush.pop());
    			}
    		}
    		return stackPop.pop();
    	}
    	
    	/** * 弹出元素 并保留元素 * @return */
    	public int peek() { 
    		if (stackPush.isEmpty() && stackPop.isEmpty()) { 
    			throw new RuntimeException("Queue is empty");
    		} else if (stackPop.isEmpty()) { 
    			while (!stackPush.isEmpty()) { 
    				stackPop.push(stackPush.pop());
    			}
    		}
    		return stackPop.peek();
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]: /images/20211201/edf657d8c81f41cc97b1d73749d432aa.png
[2019072019390414.png]: /images/20211201/815013f366a14807894e074507e0deb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]: /images/20211201/db4ed436d0ff40429ab47a577aed2100.png