1. 棧數據結構簡單介紹
2. 簡單實現代碼及stl中stack簡單使用
3. 代碼下載?
1. 棧數據結構簡單介紹
棧是這樣的一種數據結構，遵循“先進后出”的原則。在stack上定義如下的operations：
1. 判空
2. 入棧push
3. 出棧pop，在棧的不同實現版本中，有的實現pop元素返回棧頂的元素，有的實現卻僅僅是將棧頂元素彈出，通過top函數得到棧頂元素
4. 判滿??
2. 實現代碼以及stl中stack的簡單使用
下面的棧使用數組來存儲元素。代碼如下：
#include <iostream>
using namespace std;
class MyStack
{
// 數據成員
private :
const int m_nStackSize;
int m_nTop;
// 數組在構造函數中產生
int* m_pData;
public :
// 構造函數
MyStack() : m_nStackSize(10)
{
// 初始化數據
m_nTop = -1;
// 生成數組
m_pData = new int[m_nStackSize];
}
MyStack(int size) : m_nStackSize(size)
{
m_nTop = -1;
m_pData = new int[m_nStackSize];
}
// 析構函數
~MyStack()
{
// 釋放內存
delete m_pData;
}
// 判空
bool isEmpty()
{
return (m_nTop == -1);
}
// 判滿
bool isFull()
{
return ( m_nTop == (m_nStackSize - 1) );
}
// 壓棧
void push(int ele)
{
// 如果棧滿
if(isFull())
return;
// 未滿，棧頂自增，壓入元素
m_nTop++;
m_pData[m_nTop] = ele;
}
// 彈棧
int pop()
{
// 棧空
if(isEmpty())
throw exception();
// 不空，彈棧，棧頂自減
int ele = m_pData[m_nTop];
m_nTop--;
return ele;
}
};
// 測試程序
int main()
{
MyStack stack;
// 初始為空
cout << "初始化時，棧為" << (stack.isEmpty() ? "空" : "非空" ) << endl;
// 壓棧
stack.push(1);
stack.push(2);
stack.push(3);
cout << "入棧之后，棧為" << (stack.isEmpty() ? "空" : "非空" ) << endl;
cout << "第一個出棧元素是" << stack.pop() << endl;
cout << "第二個出棧元素是" << stack.pop() << endl;
cout << "第三個出棧元素是" << stack.pop() << endl;
cout << "出棧之后，棧為" << (stack.isEmpty() ? "空" : "非空" ) << endl;
return 0;
}?
c++中stl已經為我們實現了一個泛型的stack，簡單的使用示例如下：
#include <iostream>
#include <stack>
using namespace std;
int main()
{
// 聲明棧
stack<int> context;
// 入棧
context.push(1);
context.push(2);
// 出棧
int ele = context.top();
context.pop();
cout << ele;
// 判空
context.empty();
// 判滿，該棧的長度會自動增加
// 除非出現內存不夠的情況，否則
// 不會出現滿的情況
return 0;
}
?3. 代碼下載
/Files/xuqiang/Stack.rar?
