栈的创建, 出栈, 入栈, 遍历栈(思路分析) [数据结构][Java]

栈的创建,出栈,入栈,遍历栈(思路分析)

实现栈的思路分析:

1. 我们使用一个数组来模拟栈

   • 其实使用链表也是可以实现实现栈结构的,后面我们同样会使用链表来实现栈结构

2. 定义一个top指针指向栈顶,初始化为 -1

3. 入栈的操作:

   top++; //让我们的栈顶指针后移
   stack[top] = data; //将要入栈的值赋值给后移之后的栈顶指针
   1
   2

4. 出栈的操作:

   int value = stack[top]; //将我们要出栈的栈顶指针指向的元素先暂时保存到一个临时变量中
   top--; //将栈顶指针前移(这一步其实就是将我们原本的栈顶位置的元素删除掉了)
   return value; //将出栈的元素返回
   1
   2
   3

注意: 我们的栈中只需要一个指针,需要一个指针指向栈顶元素就可以了,对于栈尾元素不需要专门定义一个指针指向栈尾

• 因为我们的栈结构中只有栈顶元素和栈尾元素会发生改变,所以我们只需要通过栈顶的变化来完成对栈结构的操作,我们也就不需要使用到栈尾指针
• 我们之前将队列的时候我们讲过队列中要定义一个队尾和队首指针 —> 因为我们的队列是需要通过修改队尾和队首元素来进行一些指定的操作的
  • 所以就是我们如果有对首部元素或者是对尾部元素要进行操作的时候我们就要定义一个首部和尾部指针,通过这个指针就可以访问到对应的结点 , 而如果我们不允要操作队首或者队尾指针,那么我们也就不用声明对应的指针来指向它们

判断栈满: top = maxSize - 1

• maxSize就是栈的长度(也就是实现栈的底层数组的长度),由于我们的栈顶指针是从0开始的所以最后栈满的时候top指针就应该等于maxSize - 1

判断栈空: top = -1

• 当top指向-1的时候就是表示栈中没有元素(也就是表示栈为空)

数组模拟实现栈的思路分析图: