棧的定義：
? ? ?棧是只能在一端進行數(shù)據(jù)插入和刪除的線性表媒熊。
棧的性質(zhì)：
? ? ?后進先出（FILO）吞获，后面進去的元素渔嚷，先出來，先進去的元素后出來
棧的操作：
? ? ?棧的操作很簡單媳握，就是入棧和出棧碱屁，如下圖所示
棧的表示：
用一個一維數(shù)組，加一個指針蛾找，表示棧娩脾，代碼如下：
#include <iostream>
using namespace std;
const int N =10;//定義棧的長度
int a[N];? ? ? //定義棧（數(shù)組）
int TOP =0;? ? //定義棧的指針
void push(int x);? //入棧
int pop();? ? ? ? //出棧
void print();? ? //棧元素輸出
int main()
{
? ? for (int i=1;i<=11;i++)
? ? {
? ? push(i);
? ? }
? ? print();
? ? cout<<pop()<<endl;
cout<<pop()<<endl;
cout<<pop()<<endl;
print();
return 0;
}
void print()
{
for (int i=0;i<TOP;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int pop()
{
int x;
if (TOP == -1)
{
? cout<<"棧已空"<<endl;
? return 0;
}
x=a[TOP-1];
TOP--;
? ? return x;
}
void push(int x)
{
? if (TOP == N)
? {
? cout<<"棧已滿"<<endl;
? return ;
? }
? a[TOP] = x;
? TOP ++;
}
棧的應(yīng)用：
求前綴、后綴表達式的值腋粥，有關(guān)前綴晦雨、后綴表達式架曹，在后面二叉樹時介紹隘冲，應(yīng)用代碼如下：
#include <iostream>
#include <cstring>
using namespace std;
const int N =255;//定義棧的長度
int a[N];? ? ? //定義棧（數(shù)組）
int TOP =0;? ? //定義棧的指針
void push(int x);? //入棧
int pop();? ? ? ? //出棧
void jisuan(string ss);
int main()
{
string ss="34+5*6-";? //34+5*6-
jisuan(ss);
cout<<"表達式的值是："<<pop()<<endl;
return 0;
}
void jisuan(string ss)
{
for (int i=0;i<ss.length();i++)
{
int x=0,y=0;
if (ss[i] == '+')
{
x=pop();
y=pop();
push(x+y);
continue;
}
if (ss[i] == '-')
{
x=pop();
y=pop();
push(x-y);
continue;
}
if (ss[i] == '*')
{
x=pop();
y=pop();
push(x*y);
continue;
}
if (ss[i] == '/')
{
x=pop();
y=pop();
push(x/y);
continue;
}
push(ss[i]-48);
}
}
int pop()
{
int x;
if (TOP == -1)
{
? cout<<"棧已空"<<endl;
? return 0;
}
x=a[TOP-1];
TOP--;
? ? return x;
}
void push(int x)
{
? if (TOP == N)
? {
? cout<<"棧已滿"<<endl;
? return ;
? }
? a[TOP] = x;
? TOP ++;
}
棧相關(guān)題目：
在信息學奧賽中，有關(guān)棧的知識考查绑雄，主要以選擇題居多展辞，考查棧的基本概念和操作
如下面的題目：
? ? ?某個車站呈狹長型，寬度只能容下一臺車万牺，并且只有一個出入口罗珍。已知某時刻該車站狀態(tài)為空洽腺，從這一時刻開始的出入記錄為“進，出覆旱，進蘸朋，進，進扣唱，出藕坯，出，進噪沙，進炼彪，進，出正歼，出”辐马，假設(shè)車輛入站的順序為1,2,3,..則車輛的出站順序為（）
A.1,2,3,4,5? ? ?B.1,2,4,5,7 C.1,4,3,7,6 ?D.1,4,3,7,2
