栈的实现
写在前面
栈（Stack)是一种特殊的线性表，是一种只允许在表的一端进行插入和删除操作的线性表。栈中允许进行插入和删除操作的一端称为栈顶，另一端为栈底。栈顶的当前位置是动态的，标识栈顶当前位置的称为栈顶指示器（或栈顶指针）。栈的插入和删除操作通常称为入栈或进栈，栈的删除操作称为出栈或退栈。当栈中没有数据元素时称为空栈。
根据栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是当前栈顶元素，这样，最后进入堆栈的数据元素总是最先出栈，因此栈也被成为后进先出表。
1.栈的基本运算
- 初始化栈
- 销毁栈
- 判断栈是否为空
- 进栈
- 出栈
- 取栈顶元素
2.顺序栈四要素
- 栈空条件：
top==-1 - 栈满条件：
top==max_stack - 1 - item进栈操作：top++,将item放在top处
- 退栈操作：从top处取出元素item，top–
3.类说明
对于顺序栈Stack的实现，应创建一个数组来存放栈中的元素，并用一个始终指向栈顶的变量top来表示栈顶的位置。类定义如下：
typedef int Stack_Entry;
const int max_stack = 10;
class Stack
{
public:
Stack();
//构造函数
~Stack() {};
//析构函数
bool empty() const;
//判断栈是否为空
Stack_Entry pop();
//出栈数据元素
Stack_Entry Top(Stack_Entry &item) const;
//返回栈顶元素
void push(const Stack_Entry &item);
//数据元素item进栈
int getsize() const;
//获取栈中元素的个数
void clearstack();
//清空栈
private:
int top;//栈顶位置指示器
Stack_Entry entry[max_stack];//Stack_Entry类型的数组
};
4.具体实现
Stack::Stack()
{
top=-1;
}
bool Stack::empty() const
{
return (top==-1);
}
Stack_Entry Stack::pop()
{
if (top==-1)
{
cout << "Stack is empty" << endl;
}
return entry[top--];
}
Stack_Entry Stack::Top(Stack_Entry & item) const
{
if (top == -1)
{
cout << "Stack is empty" << endl;
}
return entry[top];
}
void Stack::push(const Stack_Entry & item)
{
if (top == max_stack - 1)
{
cout << "Stack is full" << endl;
}
top++;
entry[top] = item;
}
int Stack::getsize() const
{
return top+1;
}
void Stack::clearstack()
{
top = -1;
}
5.主函数
void test()
{
Stack stack;
for (int i = 0; i < 10; i++)
{
stack.push(i+10*i);
}
cout << "当前栈中元素数为：" << stack.getsize() << endl;
for (int i = 0; i < 10; i++)
{
Stack_Entry tmp;
tmp = stack.pop();
cout << "我是" << i << "号元素:"<<tmp << endl;
}
cout << "当前栈中元素数为：" << stack.getsize() << endl;
if (stack.empty())
{
cout << "Stack is empty" << endl;
}
else
{
cout << "Stack is not empty" << endl;
}
}
int main()
{
test();
system("pause");
return EXIT_SUCCESS;
}
输出结果如下图：
