精华内容
下载资源
问答
  • 用数组实现一个栈

    2011-09-16 11:42:37
    C++ 用数组实现一个栈 很经典的 大家可以看看 学习学习
  • 用数组实现一个栈结构

    万次阅读 2018-07-21 20:31:51
    通俗的讲相当于是一个容器,就我们生活中而言,我们可以在容器中装东西,也可以从中取出我们想要的物品。我们可以形象地画个示意图,如下所示:  假如,我们有几个(编号为1、2、3、4、5、6、7)物品按照如图...

        栈在计算机中是很常见的,栈到底是什么呢?用官方的话说栈(Stack) 类表示后进先出(LIFO)的对象堆栈。通俗的讲栈相当于是一个容器,就我们生活中而言,我们可以在容器中装东西,也可以从中取出我们想要的物品。我们可以形象地画个示意图,如下所示:

        假如,我们有几个(编号为1、2、3、4、5、6、7)物品按照如图装入容器中,顺序如图所示,假如我们要取出来,顺序一定是倒着的(即:7、6、5、4、3、2、1),这就是我们所谓的:LIFO(Last In First Out)。在栈中,我们称最先放入的元素称为栈底元素,最后放入的称为栈顶元素。将元素放在栈中称为入栈,取出称为出栈。现在我们想要用数组简单地实现栈结构。

        查API可知,在栈中存在5个方法,即:empty()、peek()、pop()、push()、search()。要想实现这几种方法,我们需要分别构造相应的方法,使之达到预期的效果。

    package stack01;
    import java.util.Arrays;
    import java.util.EmptyStackException;
    public class StackExer {
    	class ArrayStack{
    		private String[] data=new String[10];//存储数据
    		private int size;//记录个数
    //把item压入堆栈顶部
    		public void push(String str) {
    			//判断是否需要扩容
    			if (size>data.length) {
    				data=Arrays.copyOf(data, data.length*2);
    			}
    			data[size++]=str;
    		}
    		//查看堆栈顶部的对象,但不从堆栈中移除它
    		public String peek() {
    //判断栈是否为空
    			if (size==0) {
    				throw new EmptyStackException();
    			}
    			return data[size-1]; //获取栈顶元素
    		}
    		//移除堆栈顶部的对象,并作为此函数的值返回该对象
    		public String pop() {
    			String str=this.peek();//获取栈顶元素
    			size--;                //减少元素个数
    			return str;
    		}
    		//测试堆栈是否为空
    		public boolean empty() {
    			return size==0;
    		}
    
    
    		//返回对象在堆栈中的位置,以 1 为基数
    
    		public int research(String str) {
    			
    			//顺着放倒着拿(FILO/LIFO)
    for (int i = size-1; i >=0; i--) 
    {
    				if (str==data[i]||str!=null&&data[i].equals(str)) {
    					return size-i;   				}
    			}
    			return -1;    //返回栈中不存在该元素
    		}
    		
    	}
    
    	
    	
    }
    

     

    展开全文
  • Java用数组实现一个栈结构

    千次阅读 2019-06-25 23:08:27
    写在前面 这是瓜子二手车面试的第一道题目,如果之前没有手写过的话可能很晕,没错我就是这么晕,后来再...既然是实现栈的结构,那么我看需要实现一些基础的栈的方法,于是我们定义一个接口IStack,在这里定义那...

    写在前面

    这是瓜子二手车面试的第一道题目,如果之前没有手写过的话可能很晕,没错我就是这么晕,后来再仔细想想这个代码真的感觉自己面试尤其是算法题还是紧张,紧张到大脑短路,大脑一团浆糊但是自己的所谓结论就张口就来,面试官不怕你说错但是不希望看到你不经过大脑认真考虑瞎说瞎猜,特此记录一下这个面试题

    既然是实现栈的结构,那么我看需要实现一些基础的栈的方法,于是我们定义一个接口IStack,在这里定义那些栈中常用的方法

    public interface IStack {
        int push(int element);
    
        int pop();
    
        int peek();
    
        boolean empty();
    
        int size();
    
    }
    

    如果我们看过ArrayList源码的话还记得里面是用的数组做的,即数组存储元素,而且我们也知道数组的长度和ArrayList集合大小并不相等,一般的话都是数组长度大于集合长度,因为我们实际上存储数据用的是数组那么当然数组的长度大于元素的个数才可以存储呢。这就会遇到下面这个问题:

    如果集合长度和数组长度一样大,那么再放入一个元素怎么办?

    因为数组是不可以动态扩容的,所以我们只能通过拷贝数组的方式重新建立一个数组

    接下来看看我们的实现类

    public class IntStack implements IStack {
        //默认容量是10个
        private static final int CAPITILY = 10;
        //扩容因子,默认是扩充之前的两倍
        private static final int FACTOR = 2;
        //集合元素的个数
        private int mSize = 0;
        //核心数组,注意数组的长度>=集合长度(mArray.length>=mSize)
        private int[] mArray = new int[CAPITILY];
    
        @Override
        public int push(int element) {
            if(mSize>=mArray.length){
                //如果数据满了需要考虑扩容了,这里默认是扩容为之前的两倍
                //非常不推荐用Arrays.copy方法,其本质也是用了下面这个方法
                //System.arraycopy真的很重要,基本上数组扩容都是这个方法做的
                int[] newArray = new int[mArray.length*FACTOR];
                System.arraycopy(mArray,0,newArray,0,mArray.length);
                mArray = newArray;
    
            }
            mArray[mSize++] = element;
            return element;
        }
    
        @Override
        public int pop() {
            if(mSize>0){
                int result = mArray[mSize-1];
                mArray[mSize - 1] = 0;
                mSize--;
                return result;
            }else {
                throw new EmptyStackException();
            }
    
        }
    
        @Override
        public int peek() {
            if(mSize>0){
                return mArray[mSize - 1];
            }else {
                throw new EmptyStackException();
            }
        }
    
        @Override
        public boolean empty() {
            return mSize==0;
        }
    
        @Override
        public int size() {
            return mSize;
        }
    
    }
    

    最后想说,如果我们对知识知其一半等于不知道。

    展开全文
  • 一个数组实现两个(共享

    千次阅读 多人点赞 2018-08-23 20:10:52
    题目:   一个数组实现两个。 方法1:   下标为0的位置为1的底,下标为1的位置为2的底,1的元素存放在下标为偶数的位置上,2的元素放在下标为奇数的位置上。   如上图所示的数组:若1有...

    题目:
      一个数组实现两个栈。
    方法1:
      下标为0的位置为栈1的栈底,下标为1的位置为栈2的栈底,栈1的元素存放在下标为偶数的位置上,栈2的元素放在下标为奇数的位置上。
    这里写图片描述

      如上图所示的数组:若栈1有一个元素 2,栈2有6个元素 1,2,3,4,5,6,下标为0的位置为 2,下标为1,3,5,7,9的位置分别为1,2,3,4,5。6无法插入但数组中还有很多剩余的空间。。可见该方法会浪费大量的空间。

    这里写图片描述


    方法2:
      中间的两个下标分别作为栈1和栈2的栈底,栈1和栈2分别向左右扩展。
    这里写图片描述
      如方法1所示,方法2与方法1相似也会浪费大量的空间。


    方法3:
      下标为0的位置为栈1的栈底,栈2的栈底在下标最大的位置上。栈1向左扩展,栈2向后扩展。这种方法不会出现浪费内存的情况。
    这里写图片描述


    方法3的代码实现:

      首先应该定义一个共享栈:

    #define Max 10
    #define DataType int 
    typedef struct SharedStack
    {
        DataType data[Max];
        int top1;
        int top2;
    }sharedstack;

    共享栈初始化:

    //共享栈初始化
    void InitShared(sharedstack *s)
    {
        assert(s);
        s->top1 = 0;
        s->top2 = Max - 1;
        memset(s->data, 0, Max*sizeof(DataType));
    }

    入栈:

    //入栈
    void PushSharedStack(sharedstack *s, DataType d, int which)
    {
        assert(s);
        if (which == 1)
        {
            if (s->top1 <= s->top2)
            {
                s->data[s->top1++] = d;
            }
            else
            {
                printf("栈已满!\n");
                return;
            }
        }
        else
        {
            if (s->top1 <= s->top2)
            {
                s->data[s->top2--] = d;
            }
            else
            {
                printf("栈已满!\n");
                return;
            }
        }
    }
      which == 1 表示栈1,d表示要入栈的数据。

    出栈:

    //出栈
    void PopSharedStack(sharedstack *s, int which)
    {
        assert(s); 
        if (which == 1)
        {
            if (s->top1 == 0)
            {
                printf("栈空!\n");
                return;
            }
            else
            {
                s->top1--;
            }
        }
        else
        {
            if (s->top2 == Max-1)
            {
                printf("栈空!\n");
                return;
            }
            else
            {
                s->top2++;
            }
        }
    }

    栈顶元素:

    //栈顶
    DataType SharedStackTop(sharedstack *s, int which)
    {
        assert(s);
        if (which == 1)
        {
            if (s->top1 == 0)
            {
                printf("栈空!\n");
                return -1;
            }
            else
                return s->data[s->top1 - 1];
        }
        else
        {
            if (s->top2 == Max-1)
            {
                printf("栈空!\n");
                return -1;
            }
            else
                return s->data[s->top2 + 1];
        }
    }

    栈长短:

    //栈长短
    DataType SharedStackSize(sharedstack *s, int which)
    {
        assert(s);
        if (which == 1)
        {
            return s->top1;
        }
        else
            return Max - s->top2 - 1;
    }
    展开全文
  • 通过数组实现一个栈

    2019-02-01 10:04:32
    栈是一个先进后出的数据结构,所以实现栈就抓住栈的该特性,当然使用数组实现栈,需要考虑扩容问题,如果使用链表来实现的话就没有扩容问题了。 一、定义栈的方法接口 这里定义了栈的几个主要方法: public ...

    栈是一个先进后出的数据结构,所以实现栈就抓住栈的该特性,当然使用数组实现栈,需要考虑扩容问题,如果使用链表来实现的话就没有扩容问题了。

    一、定义栈的方法接口

    这里定义了栈的几个主要方法:

    public interface IStack<E> {
        /**
         * 栈元素大小
         * @return
         */
        int size();
    
        /**
         * 是否为空
         * @return
         */
        boolean empty();
    
        /**
         * 压栈
         * @param item
         */
        void push(E item);
    
        /**
         * 弹栈
         * @return
         */
        E pop();
    
        /**
         * 查看栈顶元素
         * @return
         */
        E peek();
    }
    

    二、实现

    /**
     * 通过数组实现一个栈
     * @param <E>
     */
    public class ArrayStack<E> implements IStack<E> {
        // 默认容量
        private static final int DEFAULT_CAPACITY = 10;
        // 保存元素的数组
        private E[] data;
    
        // 元素数量
        private int size;
    
        // 栈顶指针 索引
        private int top;
    
        public ArrayStack(){
            this(DEFAULT_CAPACITY);
        }
    
        public ArrayStack(int capacity){
            this.size = 0;
            this.top = -1;
            this.data = (E[]) new Object[capacity];
        }
    
        /**
         * 栈元素大小
         * @return
         */
        @Override
        public int size() {
            return size;
        }
    
        /**
         * 是否为空
         * @return
         */
        @Override
        public boolean empty() {
            return size == 0;
        }
    
        /**
         * 压栈
         * @param item
         */
        @Override
        public void push(E item) {
            if(data.length == size){
                // grow 扩容
                grow(2 * size);
            }
            data[++top] = item;
            size ++;
        }
    
        private void grow(int capacity){
            if(capacity <= DEFAULT_CAPACITY )
                return;
            data = Arrays.copyOf(data, capacity);
        }
    
        /**
         * 弹栈
         * @return
         */
        @Override
        public E pop() {
            if(size == 0){
                throw new EmptyStackException();
            }
    
            size --;
            if(size < (data.length>>1)){
                grow(data.length>>1);
            }
            return data[top--];
        }
    
        /**
         * 查看栈顶元素
         * @return
         */
        @Override
        public E peek() {
            if(size == 0){
                throw new EmptyStackException();
            }
            return data[top];
        }
    
        public static void main(String[] args) {
            IStack stack = new ArrayStack();
            for(int i=0; i<10; i++){
                stack.push(i+1);
            }
    
            System.out.println("弹出元素:"+stack.pop());
            System.out.println("弹出元素:"+stack.pop());
    
            for (int i = 0; i < 8; i++) {
                System.out.println("弹出剩余元素:"+stack.pop());
            }
        }
    }
    

    测试结果:

    弹出元素:10
    弹出元素:9
    弹出剩余元素:8
    弹出剩余元素:7
    弹出剩余元素:6
    弹出剩余元素:5
    弹出剩余元素:4
    弹出剩余元素:3
    弹出剩余元素:2
    弹出剩余元素:1
    


    展开全文
  • 利用一个数组实现两个

    千次阅读 2017-05-30 20:55:57
    问题分析:利用一个数组实现连个,有多种方式如:方法1:利用奇偶位,分别存储1和2的数据; 方法2:从中间开始将数组一分为二,左边为1,右边为2; 方法3:1从头开始增长,2从尾向头进行增长,相遇后...
  • 描述如何只用一个数组实现三个。 你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示下标,value表示压入的值。 构造函数会传入一个stackSize参数,代表...
  • 用一个数组实现两个

    千次阅读 2016-04-18 23:56:31
    题目:用一个数组实现两个 方案一:将数组的下标为0的位置当做第一个栈底,下标为1的位置当做第二个底,将数组的偶数位置看做第一个栈的存储空间,奇数位置看做第二个的存储空间。 方案二:从中间...
  • 一,用一个数组实现两个(先进后出),有以下几种方法: ①数组的奇数位置存储一个栈的元素,偶数位置存储另一个栈的元素; ②两个分别从数组的中间向两头增长; 数组的中间位置看做两个底,压栈时栈顶...
  • //该程序仅用一个数组实现两个的例程。 //除非数组的每一个单元都被使用 //否则你的例程不能有溢出声明 #include <stdio.h> #include <stdlib.h> #define MinStackSize (5) typedef struct Node ...
  • JAVA数组自己实现一个栈

    千次阅读 2019-01-26 20:47:44
    在数组中,若知道数据项的下标,便可立即访问该数据项,或者通过顺序搜索数据项,访问到数组中的各个数据项。 但是和队列不同,它们的访问是受限制的... * 数组实现一个队列 * 队列是先进先出,只能访问头部数据 ...
  • java用数组实现一个栈

    2021-04-07 14:50:59
    1.我们需要先声明一个数组来模拟 2.通过一个指针来让数据出栈和入栈 public class Stack { //声明一个数组 private int[] arr; //声明头结点 private int flage = 0; public Stack(int size) { arr = new...
  • 通过一个数组实现两个(C语言)

    千次阅读 2018-04-17 20:06:01
    通过一个数组实现的两个也叫作共享。我们可以将一个数组一分为二,供两个栈使用。 也有另外一种虽然也是讲一个数组一分为二供两个栈使用,但在具体实现上有所不同。 牢记1的区间是[0,top1)的左闭右开区间...
  • public class TwoStack { private Object[] stack;... //1在数组中的下标 private int size1; //2在数组中的下标 private int size2; //初始化数组的大小 public TwoStack(int length){ stack=new Objec
  • 主要为大家详细介绍了利用数组实现栈,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • java用数组实现栈

    2020-08-16 16:26:35
    一个先入后 出(FILO-First In Last Out)的有序列表。 (stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的...
  • 用一个数组实现3个 实现3个,可以将数组分成 1:3n+0 2: 3n+1 3: 3n+2 代码: package Test; public class ThreeStack { Object[] stack; int s1,s2,s3; //每个的长度 public ThreeStack(int ...
  • 利用数组实现一个简单的

    千次阅读 2018-03-23 17:05:32
    * 用数组实现一个简单的 * 方法: * 压入元素 push() * 弹出栈顶元素 pop() * 的大小 size() * 是否为空 isEmpty() */ public class ArrayToStack&lt;Item&gt; { int N =0; Item arr[] ; ....
  • 一个数组实现两个

    2018-03-07 11:18:19
    方法二:既然方法一可以从两边开始,那么我们也可以从中间开始向两边延伸,但这样有可能就会造成空间浪费,比如某一个栈分配了大量的空间,可是实际其只有一两个数据。方法三:在讨论中,有的同学建...
  • class double_stack{ //两个栈的长度 private int length; private int top1,top2; private int[] arr; public double_stack(int length){ this.length=length; arr=new int[length]...
  • 所用方法为,第一个栈数组底部开始,第二个数组顶部开始,第三个数组中间开始,并且向右。过程中需要不断的debug push操作的判断:第一步就是需要判断整个数组是否满了 第二步就是判断是否满了,满了...
  • 如何在一个数组A[1…n]中实现两个,使得当两个的元素个数之和不为n时,两者都不会发生上溢。 要求push和pop操作的运行时间为O(1)。 实现: 两个分别从数组的两端开始,向中间push元素,直到两个指针相遇。 ...
  • 的实现(C语言)数组实现以及链表实现源码,以及各个功能测试代码函数等 和后缀式转前缀式的用例
  • 主要介绍了Java中使用数组实现栈数据结构实例,本文先是讲解了实现栈至少应该包括以下几方法等知识,然后给出代码实例,需要的朋友可以参考下
  • Java使用数组实现栈

    2019-09-22 17:40:31
    看到了一个面试题,使用数组创建一个栈。 所以亲自动手实现一个,没有查资料,按照自己的想法去实现的,若存在不合理或者错误的地方,欢迎指出,谢谢! 的特性:先进后出 的方法: 优点:指定泛型存储(任意...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 298,880
精华内容 119,552
关键字:

如何用数组实现一个栈