栈在计算机中是很常见的，栈到底是什么呢？用官方的话说栈（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;    //返回栈中不存在该元素
		}
		
	}

	
	
}
 
 

写在前面
 
 
 
这是瓜子二手车面试的第一道题目，如果之前没有手写过的话可能很晕，没错我就是这么晕，后来再仔细想想这个代码真的感觉自己面试尤其是算法题还是紧张，紧张到大脑短路，大脑一团浆糊但是自己的所谓结论就张口就来，面试官不怕你说错但是不希望看到你不经过大脑认真考虑瞎说瞎猜，特此记录一下这个面试题
 
 
既然是实现栈的结构，那么我看需要实现一些基础的栈的方法，于是我们定义一个接口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;
    }

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

题目：
   一个数组实现两个栈。 
 方法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;
}

栈是一个先进后出的数据结构，所以实现栈就抓住栈的该特性，当然使用数组实现栈，需要考虑扩容问题，如果使用链表来实现的话就没有扩容问题了。
 
一、定义栈的方法接口
 
这里定义了栈的几个主要方法：
 
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