課堂學習
棧（stack）
是一種遵循先入后出邏輯的線性數據結構。
我們可以將棧類比為桌面上的一摞盤子，如果想取出底部的盤子，則需要先將上面的盤子依次移走。我們將盤子替換為各種類型的元素（如整數、字符、對象等），就得到了棧這種數據結構。
如圖 5-1 所示，我們把堆疊元素的頂部稱為“棧頂”，底部稱為“棧底”。將把元素添加到棧頂的操作叫作“入棧”，刪除棧頂元素的操作叫作“出棧”。
棧是 OI 中常用的一種線性數據結構。請注意，本文主要講的是棧這種數據結構，而非程序運行時的系統棧/棧空間。
棧的修改與訪問是按照后進先出的原則進行的，因此棧通常被稱為是后進先出（last in first out）表，簡稱 LIFO 表。
棧的常用操作
棧的常用操作如下所示，具體的方法名需要根據所使用的編程語言來確定。在此，我們以常見的?push()、pop()、peek()?命名為例。
通常情況下，我們可以直接使用編程語言內置的棧類。然而，某些語言可能沒有專門提供棧類，這時我們可以將該語言的“數組”或“鏈表”當作棧來使用，并在程序邏輯上忽略與棧無關的操作。
- 棧的操作是可以出棧、入棧交替進行的所以出棧序列并不一定是倒序
- 注意：已經出棧的數據不要重復入棧
- 注意：并不是所有的出棧序列都可以被操作出來
/* 初始化棧 */
stack<int> stack;/* 元素入棧 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);/* 訪問棧頂元素 */
int top = stack.top();/* 元素出棧 */
stack.pop(); // 無返回值/* 獲取棧的長度 */
int size = stack.size();/* 判斷是否為空 */
bool empty = stack.empty();練一練
總結：
棧的概念
- 數據的操作只從一端完成，如存、取等；
- 數據存放遵循，先進后出，后進先出的原則；
棧的操作
- 入棧、出棧；
- 棧頂元素、棧底元素、空棧、滿棧：
- 判斷出棧順序
棧的實現
為了深入了解棧的運行機制，我們來嘗試自己實現一個棧類。
棧遵循先入后出的原則，因此我們只能在棧頂添加或刪除元素。然而，數組和鏈表都可以在任意位置添加和刪除元素，因此棧可以視為一種受限制的數組或鏈表。換句話說，我們可以“屏蔽”數組或鏈表的部分無關操作，使其對外表現的邏輯符合棧的特性。
入棧
?出棧
取棧頂元素
清空棧
#include<bits/stdc++.h>
using namespace std;
int a[6], top = -1; // 初始化top為 -1，表示棧空void push(int x) { // 入棧函數if (top < 5) {top++;a[top] = x;}return;
}void pop() { // 出棧函數if (top > -1) { // 這里應該是top > -1 ，原代碼top>0邏輯有誤，棧空時top為 -1top--;}return;
}int getTop() { // 顯示棧頂元素if (top > -1) {return a[top];}return -1; // 棧空時返回 -1 作為標識
}void clear() { // 清空棧top = -1;return;
}int main() {push(1); // 示例入棧操作push(2);cout << getTop() << endl; // 輸出棧頂元素pop();cout << getTop() << endl;clear();return 0;
}- 頭文件和命名空間：
#include<bits/stdc++.h>?包含了大量常用的頭文件，using namespace std;?引入標準命名空間，方便使用標準庫函數和類型。 - 變量定義：定義了數組?
a?用于模擬棧，top?用于表示棧頂元素的下標，初始化為 -1 表示棧為空。 - 函數實現
push?函數：將元素?x?壓入棧中，前提是棧未滿（top < 5?，因為數組大小為 6 ，下標從 0 到 5 ）。pop?函數：彈出棧頂元素，條件是棧非空（top > -1?）。getTop?函數：獲取棧頂元素，棧非空時返回棧頂元素值，棧空返回 -1 。clear?函數：將?top?重置為 -1 ，清空棧。
main?函數：進行了一些棧操作的示例，包括入棧、獲取棧頂元素、出棧、再次獲取棧頂元素和清空棧等操作，并輸出相關結果。
課堂訓練
4145?棧的操作
描述
輸入5個整數，將這5個整數進行入棧，接下來做三次出棧操作，按照出棧順序輸出出棧元素，以上操作完成后輸出此時的棧頂元素。
輸入描述
輸入5個整數，用空格隔開。
輸出描述
輸出2行，第1行輸出出棧元素，按照出棧順序輸出，用空格隔開。第2行輸出完成出棧操作后的棧頂元素。
樣例輸入 1?
4 9 12 6 7
樣例輸出 1?
7 6 12 9
提示
1≤整數≤1000
#include<bits/stdc++.h>
using namespace std;
int a[6], top;
void push(int x) { //入棧函數if (top<5) {top++;a[top]=x;}return;
}
void pop() { //出棧函數if (top>0) {top--;}return;
}
int getTop() { //顯示棧頂元素return a[top];
}
void clear() { //清空棧top=0;return;
}
int main() {int num=0;//入棧for (int i=1;i<=5;i++) {cin>>num;push(num);}//出棧并輸出出棧元素for (int i=1;i<=3;i++) {cout<<getTop()<<" ";pop();}//輸出棧頂元素cout<<endl<<getTop();return 0;
} 2858?小魚的數字游戲
描述
小魚最近被要求參加一個數字游戲，要求它把看到的一串數字a1、a2、a3…an-1、an?，反著念出來。如：1、2、3，反著念為：3、2、1。這對小魚的那點記憶力來說實在是太難了，所以請你幫小魚編程解決這個問題。
輸入描述
第一行輸入一個整數n(1<n<10)。
第二行輸入n個數字，以空格間隔。
輸出描述
一行內倒序輸出n個數字，以空格間隔。
樣例輸入 1?
7 3 65 23 5 34 1 30
樣例輸出 1?
30 1 34 5 23 65 3
#include<bits/stdc++.h>
using namespace std;
int s[101];
int top=0;
//入棧
void push(int x) {if (top<100) {top++;s[top]=x;}return;
}
//出棧
void pop() {if (top>0) {top--;}return;
}
//顯示棧頂
int getTop() {return s[top];
}int main() {int n = 0, num = 0;cin>>n;//輸入并入棧for (int i = 0; i < n; i++) {cin >> num;push(num); //入棧}//輸出并出棧while (top > 0) { //判斷棧不為空cout << getTop() << " "; //輸出棧頂pop(); //出棧}return 0;
}2857?小括號問題
描述
假設表達式中只允許包含一種括號：圓括號，需要成對出現。即(( ))或(( )( ))等為正確的格式，(( )或 ( ))或(((均為不正確的格式。
給定一串括號輸入（換行作為結束符），檢測格式是否正確，若正確輸出YES；錯誤輸出NO。
（括號數量≤100）
輸入描述
無
輸出描述
無
樣例輸入 1?
(())
樣例輸出 1?
YES
#include<bits/stdc++.h>
using namespace std;
char s[101], a[101];
int top=0;
//入棧
void push(char x) {if (top<200) {top++;s[top]=x;}return;
}
//出棧
void pop() {if (top>0) {top--;}return;
}
//顯示棧頂
char getTop() {return s[top];
}
int main() {cin >> a;//獲取字符串int len=strlen(a);for (int i=0; i<len; i++) {//左括號入棧if (a[i]=='('){push(a[i]);} else if (getTop()=='(') {pop();} else {cout << "NO";return 0; }}//棧空時if (top==0) {cout << "YES";//棧非空時} else {cout << "NO";}return 0;
}
2859?括號匹配問題
描述
假設表達式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，但需要成對出現。即()或 [([ ][ ])]等為正確的格式，[ ( ] )或 ( [ ( ) )或( ( ) ] )均為不正確的格式。
給定一串括號輸入（換行作為結束符），檢測格式是否正確，若正確輸出YES；錯誤輸出NO。
（括號數量≤100）
輸入描述
無
輸出描述
無
樣例輸入 1?
([]())
樣例輸出 1?
YES
#include<bits/stdc++.h>
using namespace std;
char s[101], a[101];
int top=0;
//入棧
void push(char x) {if (top<200) {top++;s[top]=x;}return;
}
//出棧
void pop() {if (top>0) {top--;}return;
}
//顯示棧頂
char getTop() {return s[top];
}
int main() {cin >> a;//獲取字符串int len=strlen(a);for (int i=0; i<len; i++) {//左括號入棧if (a[i]=='['||a[i]=='('){push(a[i]);//右括號對比} else if (a[i]==')' && getTop()=='(') {pop();} else if (a[i]==']' && getTop()=='[') {pop();//既匹配不了棧頂也無法入棧} else {cout << "NO";return 0;}}//棧空時if (top==0) {cout << "YES";//棧非空時} else {cout << "NO";}return 0;
}
課后作業
2879? 字母的讀寫
2880 中括號問題
5296 括號成加對數量
1680 調度員的煩惱
