栈和队列及其背后的数据结构

  一、栈(Stack)
 
  1.栈的基本概念
 
  栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
 
  压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
 
  出栈:栈的删除操作叫做出栈。出数据在栈顶。
 
  栈顶指针:顾名思义,栈顶指针是指向栈顶的一个指针。但Java当中没有指针这一说法,因此也可以当作下标来进行处理。
 
  需要注意的是:栈顶指针指向的是可以存放元素的栈的位置,一旦有元素放入后它再加1。
 
  Stack中的方法有:
 
  push为压栈,pop为出栈(返回值为出栈的值),peek为栈顶元素,empty为判断栈是否为空,search为找出某个元素在栈中的第几个位置,返回下标。
 
  2.用顺序表实现栈
 
  用顺序表实现的栈称为顺序栈,只是该顺序表的实际操作也是一样要遵循栈的基本操作——先进后出。
 
  public class MyStack {
 
  private int[] elem ;
 
  private int top = 0 ;
 
  public MyStack() {
 
  this.elem = new int[3];
 
  }
 
  public void push(int item) {
 
  if(top==elem.length) {
 
  Arrays.copyOf(elem,5);
 
  return;
 
  }
 
  elem[top]=item;
 
  top++;
 
  }
 
  public int pop() {
 
  if(top==0) {
 
  throw new UnsupportedOperationException(”栈为空”);
 
  }
 
  top–;
 
  int ret = this.elem[top];
 
  return ret;
 
  }
 
  public int peek() {
 
  if(top==0) {
 
  throw new UnsupportedOperationException(”栈为空”);
 
  }
 
  return this.elem[top-1];
 
  }
 
  public int search(int item) {
 
  return 0;
 
  }
 
  }
 
  3.用链表实现栈
 
  **用链表实现栈要注意一个点:因为栈遵循的是先进后出,因此我们在入栈时的操作为单链表的头插法,出栈时的操作为删除单链表的头结点,并使得头结点指向下一结点。**只有这样用单链表实现栈才能做到时间复杂度为O(1)。

如需转载,请注明文章出处和来源网址:http://www.divcss5.com/html/h64772.shtml

张贴在3