-
栈和队列的相似点在于，它们都可以把不能立刻处理的数据暂时存储起来；不同点在于，栈对所存储数据的存取方式是LIFO的，而队列对所存储数据的存取方式是FIFO的。
-
同样是数组，处理手段不同，得到的数据结构也会不同，数组有时可以转化为栈，有时可以转化为队列。
-
栈的实现（顺序栈）
在实现栈这种数据结构时，首先要定义一个数组和一个变量。数组中所包含的元素个数就是栈的大小（栈中最多能存放多少个数据）。变量中则存储着一个索引，指向存储在栈中最顶端的数据，该变量被称为“栈顶指针”。栈的大小可以根据程序的需求任意指定。假设最多也就有100个数据，那么定义一个能把它们都存储下来的栈就可以了，这样的话就可以定义一个元素数为100的数组。这个数组就是栈的基础。接下来编写两个函数，一个函数用于把数据存入到栈中，也叫作压入到栈中；另一个函数用于从栈中把数据取出来，也叫作从栈中弹出来。在这两个函数中，都需要更新栈中所存储的数据的总数，以及更新栈顶指针的位置。也就是说通过使用由数组、栈顶指针以及入栈函数和出栈函数所构成的集合，就能实现栈这种数据结构了。 代码如下：
public interface IStack{ public void clear(); //将栈置空 public boolean isEmpty(); //判断栈是否为空 public int size(); //返回栈的数据元素个数 public T top() throws Exception; //返回栈顶元素 public void push(T t) throws Exception; //将数据元素入栈，压入栈顶 public T pop() throws Exception; //出栈，取出栈顶元素 public void display(); //输出栈中所有元素}
- 具体实现
public class MyStackLookBack implements IStack{ private int[] nums = new int[100]; //用于存储数据的数组，作为栈本质的数组 /* * 栈顶指针，这里是指向栈顶元素的下一个位置 * 所以如果top==0，栈为空; * top==nums.length,栈满;比如length==3，可供存放的位置索引是0,1,2,但top==3，说明栈满 * */ private int top = 0; @Override public void clear() { // TODO Auto-generated method stub top = 0; nums = new int[100]; } @Override public boolean isEmpty() { // TODO Auto-generated method stub if(top == 0) { return true; } return false; } @Override public int size() { // TODO Auto-generated method stub return top; } @Override public Integer top() throws Exception { // TODO Auto-generated method stub if(isEmpty()) { throw new Exception("栈为空"); } return nums[top - 1]; } @Override public void push(Integer t) throws Exception { if(top == nums.length) { throw new Exception("栈满"); } nums[top] = t; top++; // TODO Auto-generated method stub } @Override public Integer pop() throws Exception { // TODO Auto-generated method stub if(isEmpty()) { throw new Exception("栈为空"); } top--; return nums[top]; } @Override public void display() { // TODO Auto-generated method stub for(int i = top - 1; i >= 0; i--) { System.out.print(nums[i] + " "); } }}
测试：
public class MyStackLookBackTest { public static void main(String[] args) throws Exception { MyStackLookBack stack = new MyStackLookBack(); stack.push(1); stack.push(2); stack.push(3); stack.display(); System.out.println(); System.out.println("----------"); int i = stack.pop(); System.out.println(i); stack.display(); System.out.println(); System.out.println("----------"); stack.clear(); stack.display(); }} 结果如下
- 总结 以上便是对栈的基本操作的实现