栈是限制插入和删除仅仅能在一个位置上进行的表。该位置是表的末端，叫做栈的顶top。对栈的基本操作有进栈push和出栈pop，前者相当于插入。后者这是删除最后插入的元素。

栈有时又叫先进先出FIFO表。

因为栈操作是常数时间。因此除非在特殊情况下，栈不会产生明显改进。

栈的第一种实现方法是使用单链表。通过在表的顶端插入来实现push，通过删除表顶端元素实现pop。top操作仅仅是返回顶端元素的值。另外一种实现方法是使用数组，避免了链并且是更流行的解决方式。栈的栈顶用topOfStack来指向表示，对于空栈该值为-1。为将某个元素x推入栈中，我们使topOfStack加1然后置theItems[topOfStack]=x。

为了弹出栈顶元素，pop()返回theItems[topOfStack]然后topOfStack减1。

这些操作不仅以常数执行，并且是以非常快的常数时间执行。在某些机器上，若在带有自增和自减寻址功能的寄存器上操作，则整数的push和pop都能够写成一条机器指令。现代的计算机将栈操作作为指令系统的一部分，由此可见，栈非常可能是计算机在数组之后最主要的数据结构。

下面是一个用数组实现的栈，结构和数组非常像。但简化了操作，当中的main函数用作測试：

import java.util.Iterator;import java.util.NoSuchElementException;public class MyStack
     
       implements Iterable
      
        {	private static final int DEFAULT_CAPACITY = 10;	private int theSize;	private AnyType[] theItems;	private int topOfStack;	public MyStack() {		clear();	}	public void clear() {		theSize = 0;		topOfStack = -1;		ensureCapacity(DEFAULT_CAPACITY);	}	public int size() {		return theSize;	}	public boolean isEmpty() {		return size() == 0;	}	public void trumToSize() {		ensureCapacity(size());	}	@SuppressWarnings("unchecked")	public void ensureCapacity(int newCapacity) {		if (newCapacity < size()) {			return;		}		AnyType[] old = theItems;		theItems = (AnyType[]) new Object[newCapacity];		for (int i = 0; i <= topOfStack; i++) {			theItems[i] = old[i];		}		theSize = newCapacity;	}	public AnyType top() {		if (size() == 0) {			throw new NullPointerException();		}		return theItems[topOfStack];	}	public AnyType pop() {		if (size() == 0) {			throw new NullPointerException();		}		return theItems[topOfStack--];	}	public void push(AnyType x) {		if (topOfStack + 1 == size()) {			ensureCapacity(size() * 2 + 1);		}		theItems[++topOfStack] = x;	}	@Override	public Iterator
       
         iterator() {		return new StackIterator();	}	private class StackIterator implements Iterator
        
          {		private int current = 0;		public boolean hasNext() {			return current <= topOfStack;		}		public AnyType next() {			if (!hasNext()) {				throw new NoSuchElementException();			}			return theItems[current++];		}	}	public static void main(String[] args) {		MyStack
         
           stack = new MyStack
          
           (); stack.push(1); stack.push(2); stack.push(3); stack.pop(); stack.push(4); stack.push(5); Iterator
           
             iterator = stack.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } }}
           
          
         
        
       
      
     

输出结果：

1 2 4 5