|
栈是只能在一端进行插入删除的线性表，操作只能在一端（栈顶）完成。栈内元素的出入顺序为先进后出.
以下为两种栈的存储结构：
顺序栈
基本思想
1.使用C++类实现功能的封装
2.存储通过顺序栈数组实现，下标小的为栈底，下标大的为栈顶。
存储栈的数组长度为Size.栈满时top指向Size-1，栈空时top为-1.
注意：
1.入栈时考虑栈满
2.出栈时考虑栈空
3.由于顺序存储，空间静态分配，无需手动写析构函数销毁空间
实现
前期准备——类的声明
class Seq{
public:
Seq();
~Seq();
void push(int x);
int pop();
int gettop();
int empty();
void print();
private:
int data[Size]; //数组存储栈
int top;
};
类的实现
构造与析构
Seq::Seq(){
top=-1;
}
出、入栈
入栈时top+1(由于top初始值为-1，使用++top)，出栈时top-1（top–）
入栈
void Seq::push(int x){
//入栈考虑栈满
if(top==Size-1) throw"栈已满，无法入栈!";
data[++top]=x;
}
出栈
int Seq::pop(){
//出栈考虑栈空
if(top==-1) throw"无法完成出栈操作！" ;
int t;
t=data[top];
top--;
return t;
}
判空
int Seq::empty(){
if(top==-1) return 1;
else return 0;
}
取栈顶元素
返回栈顶
完整代码
#include<iostream>
using namespace std;
const int Size=10;
class Seq{
public:
Seq();
~Seq();
void push(int x);
int pop();
int gettop();
int empty();
void print();
private:
int data[Size]; //数组存储栈
int top;
};
Seq::Seq(){
top=-1;
}
Seq::~Seq(){}
int Seq::empty(){
if(top==-1) return 1;
else return 0;
}
void Seq::push(int x){
//入栈考虑栈满
if(top==Size-1) throw"栈已满，无法入栈!";
data[++top]=x;
}
int Seq::pop(){
//出栈考虑栈空
if(top==-1) throw"无法完成出栈操作！" ;
int t;
t=data[top];
top--;
return t;
}
int Seq::gettop(){
int x;
x=data[top];
return x;
}
void Seq::print(){
cout<<"当前栈内元素为：";
for(int i=0;i<=top;i++) cout<<data[i]<<" ";
cout<<endl;
}
int main(){
int x;
Seq s;
//检测栈是否为空
if(s.empty()) cout<<"栈为空！"<<endl;
else cout<<"栈非空！"<<endl;
//入栈测试
cout<<"入栈操作！\n";
s.push(10);
s.push(15);
cout<<"当前栈顶元素为："<<s.gettop()<<endl;
s.print();
//执行出栈操作
x=s.pop();
cout<<"出栈操作!\n"<<"删除元素"<<x<<endl;
//检测插入删除操作
s.print();
//插入元素
cout<<"输入待入栈元素：";
cin>>x;
s.push(x);
//检测插入删除操作
s.print();
//检测栈是否为空
if(s.empty()) cout<<"栈为空！";
else cout<<"栈非空！";
return 0;
}
链栈
基本思想
链表实现数据的存储，由于动态存储，需要手动析构。基本功能用类封装。
注意：链栈不设置头指针first！进行插入、遍历操作时，初始值均为top
前期准备
1.链表结构体的声明
struct Node{
int data;
Node *next;
};
2.类的声明
class Seq{
public:
Seq();
~Seq();
void push(int x);
int pop();
int gettop();
int empty();
void print();
private:
Node *top;
};
功能实现
构造与析构
构造
构造就是建立空链表，只需将头指针置空。
Seq::Seq(){
top==NULL;
}
析构只需删除指针
Seq::~Seq(){
delete top;
}
判空
int Seq::empty(){
if(top==NULL) return 1;
else return 0;
}
出入栈
因动态存储，入栈无需考虑栈满，出栈需考虑栈空
入栈
思路：需要辅助指针s，用于存放数据、挂链。
【操作：s后指针指向top，最后将top指向插入的结点】
void Seq::push(int x){
//由于使用了链表，随用随建，无需判断栈满
Node *s;
s=new Node;
s->data=x;
s->next=top;
top=s;
}
出栈
思路：需要工作指针p，辅助变量t。
【操作：p用于指向栈顶结点，t存储栈顶数据，最后删除p指向的数据】
int Seq::pop(){
//出栈需要考虑是否栈空
if(top==NULL) throw"栈空！";
int t;
Node *p=NULL;
p=new Node;
t=top->data;
p=top;
top=top->next;
delete p;
return t;
}
遍历
void Seq::print(){
Node *p=new Node;
p=top;
while(p){
cout<<p->data;
p=p->next;
}
}
完整代码
#include<iostream>
using namespace std;
struct Node{
int data;
Node *next;
};
class Seq{
public:
Seq();
~Seq();
void push(int x);
int pop();
int gettop();
int empty();
void print();
private:
Node *top;
};
Seq::Seq(){
top==NULL;
}
Seq::~Seq(){
delete top;
}
void Seq::push(int x){
//由于使用了链表，随用随建，无需判断栈满
Node *s;
s=new Node;
s->data=x;
s->next=top;
top=s;
}
int Seq::empty(){
if(top==NULL) return 1;
else return 0;
}
int Seq::pop(){
//出栈需要考虑是否栈空
if(top==NULL) throw"栈空！";
int t;
Node *p=NULL;
p=new Node;
t=top->data;
p=top;
top=top->next;
delete p;
return t;
}
int Seq::gettop(){
return top->data;
}
void Seq::print(){
Node *p=top;
cout<<"当前栈内元素为：";
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main(){
int x;
Seq s;
//检测栈是否为空
if(s.empty()) cout<<"栈为空！"<<endl;
else cout<<"栈非空！"<<endl;
cout<<"进行入栈操作"<<endl;
s.push(10);
s.push(15);
cout<<"当前栈顶元素为："<<s.gettop()<<endl;
s.print();
//执行出栈操作
x=s.pop();
cout<<"出栈操作!\n"<<"删除元素"<<x<<endl;
//检测插入删除操作
s.print();
//插入元素
cout<<"输入待入栈元素：";
cin>>x;
s.push(x);
//检测插入删除操作
s.print();
//检测栈是否为空
if(s.empty()) cout<<"栈为空！";
else cout<<"栈非空！";
return 0;
}
例：进制转换
#include<iostream>
using namespace std;
struct Node{
int data;
Node *next;
};
class LinkStack{
public:
LinkStack();
~LinkStack();
void push(int x);
int pop();
int gettop();
int empty();
void print();
int get();
int getlength();
private:
Node *top;
};
LinkStack::LinkStack(){
top==NULL;
}
LinkStack::~LinkStack(){
delete top;
}
void LinkStack::push(int x){
Node *s=new Node;
s->data=x;
s->next=top;
top=s;
}
int LinkStack::pop(){
if(empty()) throw"栈空！";
Node *p=new Node;
int t;
t=top->data;
p=top;
top=top->next;
delete p;
return t;
}
int LinkStack::empty(){
if(top==NULL) return 1;
else return 0;
}
int LinkStack::get(){
return top->data;
}
void LinkStack::print(){
Node *p=new Node;
p=top;
while(p){
cout<<p->data;
p=p->next;
}
}
int main(){
int n;
LinkStack l;
int a[1000];
cin>>n;
if(n==0) l.push(0);
int i=n;
int j=0;
while(i)
{
a[j]=i%2;
l.push(a[j]);
i/=2;
j++;
}
l.print();
return 0;
}
|