一个想法:分为三部分,如果插入其中一个栈满了,而数组没满,则移动栈。
第二个想法:利用数组实现链表。
面试题 03.01. 三合一 【简单题】
三合一。描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标,value表示压入的值。
构造函数会传入一个stackSize参数,代表每个栈的大小。
输入: ["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"] [[1], [0, 1], [0, 2], [0], [0], [0], [0]] 输出: [null, null, null, 1, -1, -1, true] 说明:当栈为空时`pop, peek`返回-1,当栈满时`push`不压入元素。 输入: ["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"] [[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]] 输出: [null, null, null, null, 2, 1, -1, -1]
题目讲解
【历史重难点题目】
【核心思想】
【代码】
class TripleInOne {
private int[] arr;
private int[] stackTop; // 每个栈当前可push的索引(对应到arr中的索引)
private int stackSize;
public TripleInOne(int stackSize) {
this.stackSize = stackSize;
arr = new int[stackSize * 3];
stackTop = new int[]{0, 1, 2};
}
public void push(int stackNum, int value) {
int curStackTop = stackTop[stackNum];
if (curStackTop / 3 == stackSize)
// 栈已满
return;
arr[curStackTop] = value;
stackTop[stackNum] += 3;
}
public int pop(int stackNum) {
if (isEmpty(stackNum))
return -1;
int value = arr[stackTop[stackNum] - 3];
stackTop[stackNum] -= 3;
return value;
}
public int peek(int stackNum) {
if (isEmpty(stackNum))
return -1;
return arr[stackTop[stackNum] - 3];
}
public boolean isEmpty(int stackNum) {
return stackTop[stackNum] < 3;
}
}
【备注】
关注微信公众号“算法岗从零到无穷”,更多算法知识点告诉你。
用数组结构实现大小固定的栈和队列,这是一个面试的常考题目,也是一个比较简单的题目。
1.实现栈结构:栈结构是先进后出的,只需要一个数组和一个记录位置的变量size,当进来一个元素,size就++,出去一个元素size就–。
2.实现队列结构:相对栈结构要难搞一些,队列的先进先出的,需要一个数组和三个变量,size记录已经进来了多少个元素,in记录刚进来的元素应该放在哪个位置,out表示用户要求弹出的元素所在的位置。size的作用不止于此,它还是in与out 的操作的关键信息,使得in与out解耦,避免的很多的麻烦,好像书本讲的是没有size这个变量的。当in或者out达到底部的时候就跳回0处。
- /**
- * 固定数组实现一个队列
- * 队列先进先出,方法有push,pull,peek
- */
- public class C02_ArrayToQueue {
- public static class MyQueue{
- private int out;//新进来的数 放这
- private int in;//用户要求弹出的数
- private int size;//已经进队列的个数
-
- private int arr[];
- public MyQueue(int iniSize){
- arr = new int[iniSize];
- size = 0;
- in = 0;
- out = 0;
- }
- public void push(int num){
- if(size==arr.length){
- throw new RuntimeException(“the queue is full!”);
- }
- size++;//大小扩展一个
- arr[in] = num;//赋值
- in = in==arr.length-1 ? 0 : in+1;//如果已经到达数组末尾就重新等于0
- }
- public int pull(){
- if(size==0){
- throw new RuntimeException(“the queue is empty!”);
- }
- size–;
- int t = out;//记录
- out = out==arr.length-1 ? 0 : out+1;//如果已经到达数组末尾就重新等于0
- return arr[t];
- }
- public int peek(){
- if(size==0){
- throw new RuntimeException(“the queue is empty!”);
- }
- return arr[out];
- }
- }
- public static void main(String[] args) {
- int iniSize = 3;
- MyQueue myQueue = new MyQueue(iniSize);
- myQueue.push(12);
- myQueue.push(13);
- myQueue.push(15);
- System.out.println(myQueue.pull());
- System.out.println(myQueue.pull());
- System.out.println(myQueue.pull());
- myQueue.push(23);
- myQueue.push(24);
- System.out.println(myQueue.pull());
- System.out.println(myQueue.peek());
- }
- }
- /**
- * 固定数组实现栈结构
- * 实现方法push,pop,peek
- * 当越界的时候抛出一个运行时异常
- * 简单面试题
- */
- public class C01_ArrayToStack {
- public static class MyStack{
- private int size;//指针位置,也表示栈已经压了多少
- private int[]arr;
- MyStack(int iniSize){//构造方法初始化数组
- arr = new int[iniSize];
- size = 0;
- }
- public void push(int num){
- if(size == arr.length){
- throw new RuntimeException("栈下标越界!");
- }
- arr[size++] = num;
- }
- public int pop(){
- if(size == 0){
- throw new RuntimeException("栈中已经没有元素可以弹出!");
- }
- return arr[--size];
- }
- public int peek(){
- if(size == 0){
- throw new RuntimeException("栈中已经没有元素可以弹出!");
- }
- return arr[size];
- }
- }
- public static void main(String[] args) {
- int len = 13;
- MyStack myStack = new MyStack(len);
- for (int i = 0; i < len; i++) {
- myStack.push(i);
- }
- for (int i = 0; i < len; i++) {
- System.out.println(myStack.pop());
- }
- }
- }
一个想法:分为三部分,如果插入其中一个栈满了,而数组没满,则移动栈。
第二个想法:利用数组实现链表。
转载于:https://www.cnblogs.com/xuehongyang/p/5373830.html
继续我提倡的抠门思想,也不枉我和青菜相交一场。
网上流传着两种方法;
方法1
采用交叉索引的方法
一号栈所占数组索引为0,2,4,6,8…(K*2)
二号栈所占数组索引为1,3,5,7,9,,,(K*2+1)
算法实现如下:
public class NewStack
{
object []arr;
int top1;
int top2;
public NewStack(int capticy)
{
arr = new object[capticy];
top1=-1;
top2=-2;
}
public void Push(int type,object element)
{
if(type == 1)
{
if(top1+2>=arr.Length)
throw new Exception(“The stack is full”);
else
{
top1+=2;
arr[top1 ] = element;
}
}
else//type==2
{
if(top2+2>=arr.length)
throw new Exception(“The stack is full”);
else
{
top2+=2;
arr[top2]=element;
}
}
}
public object Pop(int type)
{
object obj = null;
if(type == 1)
{
if(top1 == -1)
throw new Exception(“The stack is empty”);
else
{
obj = arr[top1];
arr[top1]=null;
top1=-2;
}
}
else//type == 2
{
if(top2==-2)
throw new Exception(“The stack is empty”);
else
{
obj = arr[top2];
arr[top] = null;
top2 = 2;
}
}
return obj;
}
public object Peek(int type)
{
if(type==1)
{
if(top1==-1)
throw new Exception(“The stack is empty”);
return arr[top1];
}
else/type ==2
{
if(top2==-2)
throw new Eception(“The stack is empty”);
return arr[top2];
}
}
}
方法二;
第一个栈A:从最左向右增长
第二个栈B:从最右向左增长;
代码实现如下:
public class NewStack
{
object[]arr;
int top 1;
int top 2;
public NewStack(int capticy)
{
arr= new object[capticy];
top1=0;
top2=capticy;
}
public void Push(int type,object element)
{
if(top1==top2)
throw new Exception(“The stack is full”);
if(type == 1)
{
arr[top1] = element;
top1++;
}
else//type==2
{
top2–;
arr[top2] = element;
}
}
public object Pop(int type)
{
object obj = null;
if(type == 1)
{
if(top1 ==0)
throw new Exception(“The stack is empty”);
else
{
top1–;
obj = arr[top1];
arr[top1]=null;
}
}
else//type == 2
{
if(top2 == arr.Length)
throw new Exception(“The stack is empty“);
else
{
obj =arr[top2];
arr[top2]=null;
top2++;
}
}
return obj;
}
public object Peek(int type)
{
if (type==1)
{
if(top1 == 0)
throw new Excetion(“The stack is empty”);
return arr[top1 - 1];
}
else//type ==2
{
if(top2==arr.Length)
throw new Exception(“The stack is empty”);
return arr[top2];
}
}
}
综合比较上述两种算法,我们发现,算法1实现的两个栈,每个都只有n/2个字间大小;而算法2实现的两个栈,如果其中一个很小,另一个则可以很大,它们的和为常数n。