精华内容
下载资源
问答
  • 描述如何只用一个数组实现个栈。 你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标,value表示压入的值。 构造函数会传入一个stackSize参数,代表...

    面试题 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]
    

    题目讲解

    【历史重难点题目】

    【核心思想】

    • 数组的下标为[0, 0 + 3, … , 0 + 3 * (stackSize - 1)] 存放stack0;
    • 数组的下标为[1, 1 + 3, … , 1 + 3 * (stackSize - 1)] 存放stack1;
    • 数组的下标为[2, 2 + 3, … , 2 + 3 * (stackSize - 1)] 存放stack2;

    【代码】

    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;
        }
    }
    

    【备注】

    • 帮到你了的话,点个在看吧

    关注微信公众号“算法岗从零到无穷”,更多算法知识点告诉你。

    展开全文
  • 如何用数组实现队列和

    千次阅读 2018-07-12 10:11:32
    用数组结构实现大小固定的和队列,这是一个面试的常考题目,也是一个比较简单的题目。1.实现栈结构:结构是先进后出的,只需要一个数组和一个记录位置的变量size,当进来一个元素,size就++,出去一个元素size就...

    用数组结构实现大小固定的栈和队列,这是一个面试的常考题目,也是一个比较简单的题目。

    1.实现栈结构:栈结构是先进后出的,只需要一个数组和一个记录位置的变量size,当进来一个元素,size就++,出去一个元素size就–。

    2.实现队列结构:相对栈结构要难搞一些,队列的先进先出的,需要一个数组和三个变量,size记录已经进来了多少个元素,in记录刚进来的元素应该放在哪个位置,out表示用户要求弹出的元素所在的位置。size的作用不止于此,它还是in与out 的操作的关键信息,使得in与out解耦,避免的很多的麻烦,好像书本讲的是没有size这个变量的。当in或者out达到底部的时候就跳回0处。

    1. /**
    2. * 固定数组实现一个队列
    3. * 队列先进先出,方法有push,pull,peek
    4. */
    5. public class C02_ArrayToQueue {
    6. public static class MyQueue{
    7. private int out;//新进来的数 放这
    8. private int in;//用户要求弹出的数
    9. private int size;//已经进队列的个数
    10. private int arr[];
    11. public MyQueue(int iniSize){
    12. arr = new int[iniSize];
    13. size = 0;
    14. in = 0;
    15. out = 0;
    16. }
    17. public void push(int num){
    18. if(size==arr.length){
    19. throw new RuntimeException(“the queue is full!”);
    20. }
    21. size++;//大小扩展一个
    22. arr[in] = num;//赋值
    23. in = in==arr.length-1 ? 0 : in+1;//如果已经到达数组末尾就重新等于0
    24. }
    25. public int pull(){
    26. if(size==0){
    27. throw new RuntimeException(“the queue is empty!”);
    28. }
    29. size–;
    30. int t = out;//记录
    31. out = out==arr.length-1 ? 0 : out+1;//如果已经到达数组末尾就重新等于0
    32. return arr[t];
    33. }
    34. public int peek(){
    35. if(size==0){
    36. throw new RuntimeException(“the queue is empty!”);
    37. }
    38. return arr[out];
    39. }
    40. }
    41. public static void main(String[] args) {
    42. int iniSize = 3;
    43. MyQueue myQueue = new MyQueue(iniSize);
    44. myQueue.push(12);
    45. myQueue.push(13);
    46. myQueue.push(15);
    47. System.out.println(myQueue.pull());
    48. System.out.println(myQueue.pull());
    49. System.out.println(myQueue.pull());
    50. myQueue.push(23);
    51. myQueue.push(24);
    52. System.out.println(myQueue.pull());
    53. System.out.println(myQueue.peek());
    54. }
    55. }

    1. /**
    2. * 固定数组实现栈结构
    3. * 实现方法push,pop,peek
    4. * 当越界的时候抛出一个运行时异常
    5. * 简单面试题
    6. */
    7. public class C01_ArrayToStack {
    8. public static class MyStack{
    9. private int size;//指针位置,也表示栈已经压了多少
    10. private int[]arr;
    11. MyStack(int iniSize){//构造方法初始化数组
    12. arr = new int[iniSize];
    13. size = 0;
    14. }
    15. public void push(int num){
    16. if(size == arr.length){
    17. throw new RuntimeException("栈下标越界!");
    18. }
    19. arr[size++] = num;
    20. }
    21. public int pop(){
    22. if(size == 0){
    23. throw new RuntimeException("栈中已经没有元素可以弹出!");
    24. }
    25. return arr[--size];
    26. }
    27. public int peek(){
    28. if(size == 0){
    29. throw new RuntimeException("栈中已经没有元素可以弹出!");
    30. }
    31. return arr[size];
    32. }
    33. }
    34. public static void main(String[] args) {
    35. int len = 13;
    36. MyStack myStack = new MyStack(len);
    37. for (int i = 0; i < len; i++) {
    38. myStack.push(i);
    39. }
    40. for (int i = 0; i < len; i++) {
    41. System.out.println(myStack.pop());
    42. }
    43. }
    44. }

    展开全文
  • 一个想法:分为三部分,如果插入其中一个栈满了,而数组没满,则移动栈。 第二个想法:利用数组实现链表。 转载于:https://www.cnblogs.com/xuehongyang/p/5373830.html...

    一个想法:分为三部分,如果插入其中一个栈满了,而数组没满,则移动栈。

    第二个想法:利用数组实现链表。

    转载于:https://www.cnblogs.com/xuehongyang/p/5373830.html

    展开全文
  • 继续我提倡的抠门思想,也不枉我和青菜相交场。 网上流传着两种方法; 方法1 采用交叉索引的方法 一号所占数组索引为0,2,4,6,8…(K*2) 二号所占数组索引为1,3,5,7,9,,,(K*2+1) 算法实现如下: ...

    继续我提倡的抠门思想,也不枉我和青菜相交一场。
    网上流传着两种方法;
    方法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。

    展开全文
  • 一个数组实现个栈

    千次阅读 2017-05-08 18:21:21
    数组形式一般用来实现一个栈, 现在我们如何用一个数组 来实现 两个栈保存数据呢。 一般来说,有三种思路:  1. 将数组的下标为0的位置当做第一个栈的栈底,下标为1的位置当做第二个栈的栈底,将数组的偶数位置...
  • 我们可以很容易地一个数组实现一个栈,压栈就往数组里插入值,栈顶指针加1; 出栈就直接将栈顶指针减1;取栈顶值就把栈顶指针指向的单元的值返回; 判断是否为空就直接看栈顶指针是否为-1。 如果要在一个数组里...
  • 数组在内存中是按顺序存放的,那么在实现栈的时候刚好就可以取最后一个元素即为栈顶,第一个栈实现还是很简单的,重点在于第二个栈如何数组中存放,才会让操作变得简单。由图可以看出 ,在第二个栈存放时,我们...
  • 说明如何用一个数组A[1..n]来实现个栈,使得两个栈中的元素总和不到n时,两个都不会发生上溯。注意PUSH和POP操作的时间应为O(1) 二、思考 分别用数组的两端作为两个栈的起点,向中间扩展,两个栈中的元素总和不...
  • 用一个数组实现个栈

    千次阅读 2016-03-31 17:30:23
    要注意的是如何判断整个是否满了,以及每个栈是否能再继续进栈。第三个栈有些特殊。 编程很多时候并不能一步到位,需要不断debug,然后不停更改。当然开始的思路方向是很重要的。 stack.h typedef in
  • 1、用数组简单模拟一个栈 // 基于数组实现的顺序栈 public class ArrayStack { private String[] items; // 数组 private int count; // 栈中元素个数 private int n; // 栈的大小 // 初始化数组,申请一个...
  • 如何只用一个数组实现个栈? 分两种情况:1)固定的栈,即栈和栈之间无法共享空间,每个栈都只有固定的空间。n个栈顶指针来记录栈顶位置即可。 2)非固定的栈:有必要构造一个StackData的类来存放...
  • 说明如何用一个数组A[1...n]来实现个栈,使得两个栈中的元素总数不到n时,两者都不会发生上溢。注意PUSH和POP操作的时间应为O(1)。 解法: 用top1指向数组一个元素,用top2指向数组最后一个元素,然后PUSH的...
  • 如何只用一个数组实现两个栈?并且保证只要数组中海油剩余空间,不抛出异常 思路 1.初始化两个下标变量分别指向数组的左右两端 2.左边的下标指示第一个栈,右边的下标指示第二个栈 3.如果需要对第一个栈执行元素入栈...
  • 分析:栈是后进先出,先把问题简化为如何用一个数组实现一个栈 数组每次插入时插入在最后,取出时取出最后一个元素即可 暂未想到。难道对数组三等分,每个生成一个栈? 书上解法: 1 将栈三等分,维持一个数组,...
  • 实现队列结构:相对结构要难搞一些,队列的先进先出的,需要一个数组和三个...* 固定数组实现一个队列 * 队列先进先出,方法有push,pull,peek */ public static class MyQueue<Item>{ private int siz...
  • 问题描述:说明如何用一个数组A[1..n]来实现个栈,使得两个栈中的元素总数不到n时,两者都不会发生上溢,注意PUSH和POP操作的时间应为O(1)。(算法导论第三版P131) 思路:stack1,stack2的base分别在数组的两端。...
  • 作为一个刚刚学C语言只有几个月的新手,在写程序题的时候总会发现有很多题其实用到会简单很多,但是之前一直处于一种只知道是一种后进先出的数据结构,不知道怎么去具体操作它,今天仔细想了想,发现以我现有的...
  • 1、用数组实现 ... * 如何用数组实现栈 */ public class ArrayImplStack { int[] arr = new int[5]; int index = 0; public void push(int x) { if (index == arr.length) { throw new RuntimeException
  • 前言 栈是一种只能在一端进行插入或删除的线性数据结构,栈的主要特点是...栈的实现较为简单,并且可以由两种数据结构:链表、数组来实现,这篇文章要讲的就是如何用数组和链表来实现一个栈,同时简单讲讲两种实现...
  • 数组实现栈操作

    2021-02-22 21:04:30
    对于我们来说,其实是一种先进后出的格式,我们需要用数组实现栈操作的时候其实也是遵守这个原则即可. 那么如何实现先进后出的形式呢 我们可以想到什么,没错,就是通过一个外部变量来指向后面输入进来的数值.当我们...
  • 一、实现栈:就是用一个数组来实现栈这个数据结构/** * 因为所有的数据结构必然是要落地的,所以在Java中如何去吧和队列这两个数据结构表现出来呢 * 我们用的是数组来实现的 * @author zhmm * */ //用数组来...
  • 03-数组实现栈与队列

    2018-11-21 01:33:00
    题目二 实现一个特殊的 ,实现返回中最小元素的操作 在实现的基本功能的基础上,再实现返回中最小元素的操作。 【要求】 1.pop、push、getMin操作的时间复杂度都是O(1)。 2.设计的类型...
  • 用数组实现Stack结构

    2019-03-28 09:08:52
    上节说了Stack结构的特点,以及在java中是如何实现的。java代码中Stack实现原理 ...那么现在我们直接自己写的数组类来实现一下的结构吧。 增强的数组Array package java.it.data; public class Stack<T> ...
  • 0x02作业:写一个队列 0x00动态内存分配一般在什么地方? 数组必须规定大小,一定得等到程序结束,才能释放内存。 为了防止内存浪费,我们一般都要使用动态内存分配。动态内存分配能够及时的把开出的内存释放掉...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 386
精华内容 154
关键字:

如何用数组实现一个栈