棧

定義:

? ?棧（Stack）是一個后進先出（Last in first out,LIFO）的線性表，它要求只在表尾進行刪除和插入操作。

? ? 圖如下：

特點：

? ?一、棧特殊的線性表（順序表、鏈表），它在操作上有一些特殊的要求和限制：棧的元素必須“后進先出”。

? ?三、棧的表尾稱為棧的棧頂（top），相應的表頭稱為棧底（bottom）

? ?二、棧的操作只能在這個線性表的表尾進行。

順序棧的實現(xiàn)：

push()、pop()、peek()方法的時間復雜度為O(1),當需要擴充棧容量時push()方法的時間復雜度為O(n)

package com.ds.stack; import java.util.Arrays; public class Stack<T> {// Java數(shù)組實現(xiàn)，可以使用java泛型數(shù)組。如需使用，請使用Java提供的容器private Object[] stack;// 棧的默認初始大小private final static int INIT_SIZE = 2;// 棧頂索引private int index;/*** 默認構(gòu)造方法** 棧的初始大小 默認*/public Stack() {this.stack = new Object[INIT_SIZE];index = -1;}/*** 構(gòu)造方法** @param initSize* 棧的初始大小*/public Stack(int initSize) {if (initSize < 0)throw new IllegalArgumentException();this.stack = new Object[initSize];index = -1;}/*** 出棧操作** @return 棧頂對象*/public synchronized T pop() { //return this.top == -1 ? null :(T)this.element[this.top--]; if (!isEmpty()) {T temp = peek();stack[index--] = null;return temp;}return null;}/*** 出棧操作** @return 棧頂對象*/public synchronized void push(T item) {if (isFull()) {// 如果棧滿，則創(chuàng)建空間為當前棧空間兩倍的棧Object[] temp = stack;temp = new Object[2 * stack.length];stack = Arrays.copyOf(temp, temp.length);}stack[++index] = item;}/*** 查看棧頂對象** @return 棧頂對象*/public T peek() { //return this.top == -1 ? null : (T)this.element[this.top];if (!isEmpty()) {return (T) stack[index];}return null;}/*** 查看棧是否為空** @return 如果棧為空返回true，否則返回false*/public boolean isEmpty() {return index == -1;}/*** 查看棧是否滿** @return 如果棧滿返回true,否則返回false*/public boolean isFull() {return index == stack.length - 1;}public static void main(String[] args) {Stack<Integer> stack = new Stack<Integer>(3);for (int i = 0; i < 5; i++) {stack.push(i);}System.out.println("stack.top : " + stack.peek());} }

如果存在問題，我們隨時交流！

轉(zhuǎn)載于:https://blog.51cto.com/zhaohaibo/1288757

總結(jié)

以上是生活随笔為你收集整理的【Java数据结构】3.1 顺序栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。