关于栈的几个小算法

1.用静态数组模拟栈

    想法就是创建一个index变量,index指向含有值得下一个数组空间(假设数组中有两个值,index指向2)

/**
 * 用静态数组模拟栈
 * 用一个变量index来辅助
 */
public class Stack1 {
	
	public static void main(String[] args) {
		stack s = new stack(10);
		s.push(1);
		s.push(2);
		s.push(3);
		System.out.println(s.pop());
		System.out.println(s.pop());
		System.out.println(s.pop());
		System.out.println(s.pop());
	}
	
	public static class stack{
	static int [] arr ;
	int index;
	public stack(int size) {
		if(size<0) {
			throw new IllegalArgumentException("the array size is less than 0");
		}
		arr = new int[size];
	}
	//压栈
	public void push(int i) {
		if(index == arr.length) {
			throw new ArrayIndexOutOfBoundsException("stack is full"); 	
		}
		arr[index++] = i;
	}
	//出栈
	public int pop() {
		if(index == 0) {
			throw new IllegalArgumentException("the stack is null");
		}
		return arr[--index];
		
	}
	//返回栈顶值
	public int peek() {
		if(index == 0) {
			throw new ArrayIndexOutOfBoundsException("the stack is null");	
		}
		return arr[index-1];
	}
	}

}

2.实现一个特殊的栈,有栈的正常方法,能返回栈里的最小值。要求时间复杂度为O(1)    

    思路:创建两个栈,一个栈 data 放正常的数据。另一个栈 mins 放当前数据中的最小值。例如:若新添加的数据小于当前的最小值,两个栈都添加新的数据。若新添加的数据大于当前栈中的最小值,mins 仍然添加当前最小值。

而且,data出数据的时候,mins同时出栈。

import java.util.Stack;

/**
 * 实现一个特殊的栈,有栈的正常方法,还能返回栈里的最小值
 * 时间复杂度O(1)
 * @author hasee
 *
 */
public class stack2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		StackDemo demo = new StackDemo();
		demo.push(1);
		demo.push(2);
		demo.push(3);
		demo.push(4);
		System.out.println(demo.getMin());
		System.out.println(demo.getMin());
	}
	
	static class StackDemo {
		private Stack datas = new Stack();
		private Stack mins = new Stack();
		int min =Integer.MAX_VALUE;
		//出栈
		public int pop() {
			// TODO Auto-generated method stub
			mins.pop();
			return (int) datas.pop();
			
		}
		/**
		 * 入栈的时候,两个栈同时入,datas正常操作
		 * mins入当前数据中最小值。
		 */
		public void push(int i) {
			datas.push(i);
			min = min<i?min:i;//放入当前所有数据中的最小值
			mins.push(min);
		}
		public int getMin() {
			return (int) mins.peek();//返回当前栈顶最小值
		}
	}

}

3.用队列实现栈的功能

思路:创建两个队列,一个data ,一个help。当输入数据的时候,往data中添加。当要输出的时候,将data中的数据全部输出到help中,然后输出help的栈顶。输出后,再讲help中的所有数据输入到data 中。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 用队列实现栈的功能
 * @author hasee
 *
 */
public class stack3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 Stack3  stack = new Stack3();
		 stack.push(1);
		 stack.push(2);
		 stack.push(3);
		 stack.push(4);
		 System.out.println(stack.pop());
	}
	static class Stack3 {
		Queue<Integer> data = new LinkedList<Integer>();
		Queue<Integer> help = new LinkedList<Integer>();
		//压栈
		public void push(int i) {
			data.offer(i);
		}
		//出栈
		public int pop() {
			if(data.size()==0)
				throw new NullPointerException("the stack is null");
			int size1 = data.size();
			for(int i = 0;i < size1;i++) {
				help.add(data.remove());
			}
			int result = help.poll(); 
			int size2 = help.size();
			for(int j = 0;j < size2;j++) {
				data.add(help.poll());
			}
			return result;
		}
		//返回第一个元素 但不删除
		public int peek() {
			while(data.size()>0) {
				help.add(data.remove());
			}
			int result = help.peek();
			while(help.size()>0){
				data.add(help.poll());
			}
			return result;
		}
	}

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4425
来自专栏Android研究院

深入理解链表和手写链表以及面试中常问链表的问题

上一期 讲到了 顺序表与链表的基本知识 了解链表的基本知识。并且分析了ArrayList的源码。顺序表(随机访问速度快,插入和删除效率低)和链表(随机访问速度慢...

1.3K2
来自专栏书山有路勤为径

合法的出栈序列

poj 1363 Rails 已知从1至n的数字序列,按顺序入栈,每个数字入栈后即可出栈,也可在栈中 停留,等待后面的数字入栈出栈后,该数字再出栈,求该数字序...

832
来自专栏Android知识点总结

01--图解数据结构之数组实现集合

1334
来自专栏计算机视觉与深度学习基础

Leetcode 224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string. The expre...

2367
来自专栏程序你好

如何比较一个List对象Java 7 vs Java 8

1122
来自专栏程序员宝库

如何用JavaScript手动实现一个栈

在生活中也能发现很多栈的例子。例如,厨房里堆放的盘子,总是叠在上方的先被使用;输入框内容进行删除时,总是最后输入的先删除;弹夹中的子弹,越后装入的,越先发射.....

1194
来自专栏专注 Java 基础分享

从源码解析LinkedList集合

     上篇文章我们介绍了ArrayList类的基本的使用及其内部的一些方法的实现原理,但是这种集合类型虽然可以随机访问数据,但是如果需要删除中间的元素就...

2025
来自专栏一“技”之长

Swift专题讲解十七——Optional链 原

        Swift中的Optional值有这样的特性,当对其进行可选拆包时,即使用?进行Optional类型值的取值时,如果Optional值不为nil...

682
来自专栏尾尾部落

[剑指offer] 栈的压入、弹出序列 [剑指offer] 栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序...

1022

扫码关注云+社区

领取腾讯云代金券