簡介
限定僅在表尾進(jìn)行插入和刪除操作的線性表森枪。允許插入和刪除的一端成為棧頂视搏，另一端成為棧低审孽，不含任何元素的棧成為空棧，棧又稱為先進(jìn)先出的線性表浑娜，簡稱LIFO結(jié)構(gòu)佑力。
棧的插入操作，叫做進(jìn)棧筋遭，也稱壓棧打颤，入棧。
棧的刪除操作宛畦，也叫出戰(zhàn)瘸洛，也有的叫做彈棧。
棧的附加功能
- Peep 窺視：返回堆棧的棧頂元素（不刪除）
- isEmpty：檢查堆棧是否為空次和。
- isFull：檢查堆棧是否已經(jīng)滿了反肋。
棧的存儲表示方法：
-
順序棧：利用順序存儲結(jié)構(gòu)實現(xiàn)的棧（①利用一組地址連續(xù)的存儲單元一次存放從棧底到棧頂?shù)臄?shù)據(jù)元素；②附設(shè)指針top指向棧頂元素的位置踏施，base指針指向棧底元素位置石蔗；③采用動態(tài)分配原則）
- 初始化：為順序棧分配一個數(shù)組空間（stacksize，棧的最大容量）畅形，base和top同時指向棧底养距，表示空棧。
- 入棧：判斷棧是否已滿日熬，滿則報錯棍厌，否則將元素壓入棧頂，top加一竖席。
- 出棧：判斷棧是否為空耘纱，空則報錯，否則將top減一毕荐，棧元素出棧束析。
-
鏈棧：采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧，通常用單鏈表表示（無頭節(jié)點）憎亚。
- 初始化：構(gòu)造一個空棧员寇，無頭結(jié)點，將棧頂指針置為空第美。
- 入棧：為新的棧頂元素分配結(jié)點空間蝶锋，將新結(jié)點插入到棧頂，修改棧頂指針斋日。
- 出棧：判斷棧是否為空牲览，空則報錯，否則取棧頂元素恶守，修改棧頂指針第献，釋放原棧頂元素空間。
順序棧與鏈棧的優(yōu)缺點：
- 順序棧受到最大空間容量的限制兔港，在滿員時擴(kuò)容工作量較大庸毫，在無法估計棧可能達(dá)到的最大容量時應(yīng)使用鏈棧衫樊。
棧的應(yīng)用：
- 表達(dá)式評估飒赃。
- 遞歸編程中實現(xiàn)函數(shù)調(diào)用。
入棧
出棧
實現(xiàn)一個棧
棧主要包含兩個操作科侈，入棧和出棧载佳，也就是在棧頂插入一個數(shù)據(jù)和從棧頂刪除一個數(shù)據(jù)。棧既可以用數(shù)組來實現(xiàn)臀栈，也可以用鏈表來實現(xiàn)蔫慧。用數(shù)組實現(xiàn)的棧，我們叫作順序棧权薯，用鏈表實現(xiàn)的棧姑躲，我們叫作鏈?zhǔn)綏！?br> 根據(jù)上一節(jié)我們實現(xiàn)的數(shù)組代碼我們來實現(xiàn)一個自己的棧盟蚣。
棧的抽象接口
public interface Stack<E> {
/**
* 棧的容量
* @return
*/
int getSize();
/**
* 棧是否為空
* @return
*/
boolean isEmpty();
/**
* 向棧中添加元素
* @param e
*/
void push(E e);
/**
* 向棧中取出元素
* @return
*/
E pop();
/**
* 查看棧頂?shù)脑? * @return
*/
E peek();
}
數(shù)組棧
public class ArrayStack<E> implements Stack<E> {
private E[] data;
private int size;
public ArrayStack(){
this(10);
}
public ArrayStack(int capacity){
this.data = (E[]) new Object[capacity];
this.size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 獲取棧的容量
* @return
*/
public int getCapacity(){
return data.length;
}
@Override
public void push(E e) {
addLast(e);
}
@Override
public E pop() {
return removeLast();
}
@Override
public E peek() {
return get(size - 1);
}
/**
* 獲取指定索引位置的值
* @param index
* @return
*/
private E get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed. index is illegal.");
}
return data[index];
}
/**
* 數(shù)組尾部新增元素
* @param e
*/
private void addLast(E e){
add(size, e);
}
/**
* 在指定位置插入元素
* @param index
* @param e
*/
private void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("AddLast failed. require index >=0 and index <= size");
}
if(size == data.length){
//擴(kuò)容
resize(2 * data.length);
}
for(int i = size - 1; i >= index; i --){
data[i + 1] = data[i];
}
data[index] = e;
size ++;
}
/**
* 數(shù)組擴(kuò)容
* @param newCapacity
*/
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 刪除棧中最后一個元素
* @return
*/
private E removeLast(){
return remove(size - 1);
}
/**
* 刪除棧數(shù)組中index位置的元素, 并返回刪除的元素
* @param index
* @return
*/
private E remove(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed. index is illegal.");
}
E ret = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size --;
data[size] = null;
if(size == data.length / 4 && data.length / 2 != 0){
//當(dāng)數(shù)組長度縮小為原數(shù)組的4分之一的時候才進(jìn)行數(shù)組的縮容黍析，
//縮小為原數(shù)組的2分之一，預(yù)留空間屎开，防止有數(shù)據(jù)添加導(dǎo)致擴(kuò)容浪費性能
resize(data.length / 2);
}
return ret;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("Stack: ");
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if(i != size - 1){
sb.append(", ");
}
}
sb.append("] top");
return sb.toString();
}
}
鏈表棧
public class LinkedListStack<E> implements Stack<E> {
private class Node<E>{
public E e;
public Node<E> next;
public Node(E e){
this.e = e;
}
@Override
public String toString() {
return e.toString();
}
}
private Node<E> dummyHead;
private Integer size;
public LinkedListStack(){
dummyHead = new Node<>(null);
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void push(E e) {
Node<E> node = new Node<>(e);
node.next = dummyHead.next;
dummyHead.next = node;
size++;
}
@Override
public E pop() {
if(isEmpty()){
throw new IllegalArgumentException("Cannot pop from an empty stack.");
}
Node<E> prev = dummyHead;
Node<E> retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size -- ;
return retNode.e;
}
@Override
public E peek() {
if(isEmpty()){
throw new IllegalArgumentException("Cannot pop from an empty stack.");
}
return dummyHead.next.e;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("Stack: top ");
Node<E> cur = dummyHead.next;
while (cur != null){
sb.append(cur + "->");
cur = cur.next;
}
sb.append("NULL");
return sb.toString();
}
}
棧應(yīng)用
函數(shù)應(yīng)用
操作系統(tǒng)給每個線程分配了一塊獨立的內(nèi)存空間阐枣，這塊內(nèi)存被組織成“棧”這種結(jié)構(gòu), 用來存儲函數(shù)調(diào)用時的臨時變量奄抽。每進(jìn)入一個函數(shù)蔼两，就會將臨時變量作為一個棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成如孝，返回之后宪哩，將這個函數(shù)對應(yīng)的棧幀出棧。
表達(dá)式求值
我將算術(shù)表達(dá)式簡化為只包含加減乘除四則運算第晰，比如：34+13*9+44-12/3锁孟。對于這個四則運算編譯器就是通過兩個棧來實現(xiàn)的。其中一個保存操作數(shù)的棧茁瘦，另一個是保存運算符的棧品抽。我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字甜熔，我們就直接壓入操作數(shù)棧圆恤；當(dāng)遇到運算符，就與運算符棧的棧頂元素進(jìn)行比較腔稀。
如果比運算符棧頂元素的優(yōu)先級高盆昙，就將當(dāng)前運算符壓入棧羽历；如果比運算符棧頂元素的優(yōu)先級低或者相同，從運算符棧中取棧頂運算符淡喜，從操作數(shù)棧的棧頂取 2 個操作數(shù)秕磷，然后進(jìn)行計算，再把計算 完的結(jié)果壓入操作數(shù)棧炼团，繼續(xù)比較澎嚣。
括號匹配
我們假設(shè)表達(dá)式中只包含三種括號，圓括號 ()瘟芝、方括號 [] 和花括號{}易桃，并且它們可以任意嵌套。比如锌俱，{[{}]}或 [{()}([])] 等都為合法格式晤郑，而{[}()] 或 [({)] 為不合法的格式。在給你一個包含三種括號的表達(dá)式字符串嚼鹉。我們用棧來保存未匹配的左括號贩汉，從左到右依次掃描字符串。當(dāng)掃描到左括號時锚赤，則將其壓入棧中匹舞；當(dāng)掃描到右括號時，從棧頂取出一個左括號线脚。如果能夠匹配赐稽，比 如“(”跟“)”匹配，“[”跟“]”匹配浑侥，“{”跟“}”匹配姊舵，則繼續(xù)掃描剩下的字符串。如果掃描的過程中寓落，遇到不 能配對的右括號括丁，或者棧中沒有數(shù)據(jù)，則說明為非法格式伶选。當(dāng)所有的括號都掃描完成之后史飞，如果棧為空，則說明字符串為合法格式仰税；否則构资，說明有未匹配的左括號，為非法格式陨簇。
/**
* @Author: huangyibo
* @Date: 2021/12/26 18:58
* @Description:
* 給定一個只包括 '('吐绵，')'，'{'，'}'己单，'['唉窃，']' 的字符串，判斷字符串是否有效荷鼠。
*
* 有效字符串需滿足：
*
* 左括號必須用相同類型的右括號閉合句携。
* 左括號必須以正確的順序閉合榔幸。
* 注意空字符串可被認(rèn)為是有效字符串允乐。
*/
public class LeetCodeQuestion {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c == '(' || c == '{' || c == '{'){
stack.push(c);
}else {
if(stack.isEmpty()){
return false;
}
Character pop = stack.pop();
if(c == ')' && pop != '('){
return false;
}
if(c == '}' && pop != '{'){
return false;
}
if(c == ']' && pop != '['){
return false;
}
}
}
//如果棧里面還有字符的話，那么也不行削咆，因為意味著還有字符沒辦法匹配
return stack.isEmpty();
}
}
參考：
https://blog.csdn.net/weixin_39084521/article/details/89820132
