本文共 4702 字，大约阅读时间需要 15 分钟。

1、实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间 复杂度为O(1)

方法1：使用一个栈实现，交叉栈

#pragma once#include
   
    #define MAX_VALUE 100typedef struct MinStack{	int array[MAX_VALUE];	int top;}MinStack;//实现一个栈，要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间,复杂度为O(1)/*两个方法：1、一个栈，交叉栈；2、两个栈*/void Init(MinStack *pMs){	//一个栈	pMs->top = 0;}void Push(MinStack *pMs, int data){	//一个栈	int min = data;	if (pMs->top != 0 && pMs->array[pMs->top - 1] < min){		min = pMs->array[pMs->top - 1];	}	pMs->array[pMs->top++] = data;//先放普通数据	pMs->array[pMs->top++] = min;//再放当前最小数}void Pop(MinStack *pMs){	pMs->top -= 2;}int Min(MinStack *pMs){	return pMs->array[pMs->top - 1];}int Top(MinStack *pMs){	return pMs->array[pMs->top - 2];}void test1(){	MinStack ms;	Init(&ms);	int arr[] = { 3, 2, 5, 6, 8, 3, 1, 9 };	for (int i = 0; i < sizeof(arr) / sizeof(int); i++){		Push(&ms, arr[i]);	}	printf("%d ", Min(&ms));	Pop(&ms);	printf("%d ", Min(&ms));	Pop(&ms);	printf("%d ", Min(&ms));}
   

 

方法2：使用两个栈

#pragma once#include
   
    #define MAX_VALUE 100//两个栈typedef struct MinStack{	int array1[MAX_VALUE];	int top1;//普通数据	int array2[MAX_VALUE];	int top2;//最小数据}MinStack;//实现一个栈，要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间,复杂度为O(1)/*两个方法：1、一个栈，交叉栈；2、两个栈*/void Init(MinStack *pMs){	//两个栈	pMs->top1 = pMs->top2 = 0;}void Push(MinStack *pMs, int data){	//两个栈	/*int min = data;	if (pMs->top2 != 0 && pMs->array2[pMs->top2 - 1] < data) {	min = pMs->array2[pMs->top2 - 1];	}	pMs->array1[pMs->top1++] = data;	pMs->array2[pMs->top2++] = min;*/	//不再每次都入最小栈	pMs->array1[pMs->top1++] = data;	if (pMs->top2 == 0 || data <= pMs->array2[pMs->top2 - 1]) {		pMs->array2[pMs->top2++] = data;	}}void Pop(MinStack *pMs){	/*pMs->top1--;	pMs->top2--;*/	//不再每次都入最小栈	if (pMs->array1[pMs->top1 - 1] == pMs->array2[pMs->top2 - 1]) {		pMs->top2--;	}	pMs->top1--;}int Min(MinStack *pMs){	return pMs->array2[pMs->top2 - 1];}int Top(MinStack *pMs){	return pMs->array1[pMs->top1 - 1];}void test2(){	MinStack ms;	Init(&ms);	int arr[] = { 3, 2, 5, 6, 8, 3, 1, 9 };	for (int i = 0; i < sizeof(arr) / sizeof(int); i++){		Push(&ms, arr[i]);	}	printf("%d ", Min(&ms));	Pop(&ms);	printf("%d ", Min(&ms));	Pop(&ms);	printf("%d ", Min(&ms));}
   

所用栈方法可见：

2、递归栈逆置

//top：栈大小public class ReverseStack {	public int[] reverseStackRecursively(int[] stack, int top) {		if (top <= 1) {			return stack;		}		if (top <= stack.length / 2) {			return stack;		}		int tmp = stack[top - 1];		stack[top - 1] = stack[stack.length - top];		stack[stack.length - top] = tmp;		return reverseStackRecursively(stack, top - 1);	}}

3、题目描述：堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。Push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。

输入：      对于每组测试数据，第一行是一个正整数 n，0<n<=10000(n=0 结束)。而后的 n 行，      每行的第一个字符可能是'P’或者'O’或者'A’；      如果是'P’，后面还会跟着一个整数，表示把这个数据压入堆栈；      如果是'O’，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；      如果是'A’，表示询问当前栈顶的值，如果当时栈为空，则输出'E'。堆栈开始为空。 输出：     对于每组测试数据，根据其中的命令字符来处理堆栈；     并对所有的'A’操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E’。     当每组测试数据完成后，输出一个空行。

public class Main {	public Stack
   
     stack = null;	@SuppressWarnings("resource")	public void solution() {		Scanner sc = new Scanner(System.in);		while (sc.hasNext()) {			stack = new Stack
    
     ();			int n = Integer.parseInt(sc.nextLine());			int i = n;			while (i-- > 0) {				char[] data = sc.nextLine().toCharArray();				// P 3：此时空格也算一个，所以数组的长度最大应为3				judge(data);			}			System.out.println();		}	}	private void judge(char[] data) {		switch (data[0]) {		case 'A': {			if (stack.isEmpty()) {				System.out.println("E");			} else {				System.out.println(stack.peek());			}		}			break;		case 'P': {			stack.push(data[2] - '0');		}			break;		case 'O': {			if (!stack.isEmpty()) {				System.out.println(stack.pop());			} else {				System.out.println();			}		}			break;		}	}}
    
   

4、字符串数组运算

eg:

String[] str = {"2", "4", "+", "9", "*"};

public class Solution {	public int evalRPN(String[] tokens) {		Stack
   
     s = new Stack
    
     ();// 栈		for (int i = 0; i < tokens.length; i++) {			if (tokens[i].equals("+") || tokens[i].equals("-") ||					tokens[i].equals("*") || tokens[i].equals("/")) {				int y = s.pop();				int x = s.pop();				s.push(Calculate(tokens[i], x, y));			} else {				s.push(Integer.parseInt(tokens[i]));// 把不是运算符的存储在栈里面			}		}		return s.pop();	}	public int Calculate(String str, int a, int b) {		switch (str) {		case "+":			return a + b;		case "-":			return a - b;		case "*":			return a * b;		case "/":			return a / b;		default:			return 0;		}	}}
    
   

 5、使用两个栈实现一个队列

public class Solution {	Stack
   
     stack1 = new Stack
    
     ();	Stack
     
       stack2 = new Stack
      
       ();	public void push(int node) {		// 入栈都在stack1		stack1.push(new Integer(node));	}	public int pop() {		if (stack2.isEmpty()) {			while (!stack1.isEmpty()) {				stack2.push(stack1.pop());			}		}		return stack2.pop().intValue();	}}
      
     
    
   

 

转载地址：http://udlkk.baihongyu.com/