# 【数据结构】链表与队列练习题

1. 括号配对问题

``````1.
class Solution {
public boolean isValid(String s) {
int l = s.length();
int top = 0;
char[] stack = new char[l];
for(int i = 0; i < l; i++){
if(s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '['){
stack[top++] = s.charAt(i);
}else if(top == 0){
return false;
}else{
if(stack[top -1] == '(' && s.charAt(i) == ')'
|| stack[top-1] == '[' && s.charAt(i) == ']'
|| stack[top-1] == '{' && s.charAt(i) == '}'){
top--;
}else{
return false;
}
}
}
if(top != 0){
return false;
}
return true;
}
}
2.
class Solution {
public boolean isValid(String s) {
//str -> char[]
char[] data = s.toCharArray();
Stack<Character> stack = new Stack<>();
for (char c : data
) {
//碰到左括号入栈
if (c == '{' || c == '[' || c == '('){
stack.push(c);
}else{
if (stack.isEmpty()){
return false;
}
else if (c == '}'){
char temp = stack.peek();
if (temp == '{'){
stack.pop();
//continue;
}else{
return false;
}
}
else if(c == ']'){
char temp = stack.peek();
if (temp == '['){
stack.pop();
// continue;
}else{
return false;
}
}
else if(c == ')'){
char temp = stack.peek();
if (temp == '('){
stack.pop();
//continue;
}else{
return false;
}
}
}
}
if (stack.isEmpty()){
return true;
}else{
return false;
}
}
}

``````

2. 用队列实现栈

``````class MyStack {
private Queue<Integer> queueA = new LinkedList<>();
private Queue<Integer> queueB = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {

}

//入栈
/** Push element x onto stack. */
public void push(int x) {
}

//删除栈顶元素
/** Removes the element on top of the stack and returns that element. */
public int pop() {
if (queueA.isEmpty()){
int len = queueB.size();
for (int i = 0;i < len - 1;i++){
//B队列除了最后一个元素外的其他元素依次放入队列A中
}
//队列B的最后一个元素一定是最后一个进入的
//所以可以将其认为是栈顶元素
int result = queueB.poll();
return result;
}else{
int len = queueA.size();
for (int i = 0;i < len - 1;i++){
//B队列除了最后一个元素外的其他元素依次放入队列A中
}
//队列B的最后一个元素一定是最后一个进入的
//所以可以将其认为是栈顶元素
int result = queueA.poll();
return result;
}
}

//得到栈顶元素
/** Get the top element. */
public int top() {
if (queueA.isEmpty()){
int len = queueB.size();
for (int i = 0;i < len - 1;i++){
//B队列除了最后一个元素外的其他元素依次放入队列A中
}
//队列B的最后一个元素一定是最后一个进入的
//所以可以将其认为是栈顶元素
int result = queueB.poll();
return result;
}else{
int len = queueA.size();
for (int i = 0;i < len - 1;i++){
//B队列除了最后一个元素外的其他元素依次放入队列A中
}
//队列B的最后一个元素一定是最后一个进入的
//所以可以将其认为是栈顶元素
int result = queueA.poll();
return result;
}
}

//判断是否为空
/** Returns whether the stack is empty. */
public boolean empty() {
return queueA.isEmpty() && queueB.isEmpty();
}
}
``````

3. 栈实现队列

``````class MyQueue {

private Stack<Integer> a;
private Stack<Integer> b;

public MyQueue() {
a = new Stack<>();
b = new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
a.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
//判断b栈是否为空，如果b栈不为空，那么说明a栈的元素已经倒入b了，所以直接弹出b即可
if(b.isEmpty()){
while(!a.isEmpty()){
b.push(a.pop());
}
}
return b.pop();
}

/** Get the front element. */
public int peek() {
if(b.isEmpty()){
while(!a.isEmpty()){
b.push(a.pop());
}
}
return b.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
return a.isEmpty() && b.isEmpty();
}
}

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
``````

4. 最小栈

``````class MinStack {

/** initialize your data structure here. */
private Stack<Integer> stack = new Stack<>();
public MinStack() {

}
//-2 0 -3
//-2 -2 0 -2 -3 -3
public void push(int x) {
if (stack.isEmpty()){
stack.push(x);
stack.push(x);
}else{
int temp = stack.peek();//-2
stack.push(x);//0
if (x < temp){
stack.push(x);
}else{
stack.push(temp);
}
}
}

public void pop() {
stack.pop();
stack.pop();
}

public int top() {
int temp = stack.pop();
int result = stack.peek();
stack.push(temp);
return result;
}

public int getMin() {
return stack.peek();
}
}

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
``````