浅谈C++栈的实现

栈是只能在一端进行插入删除的线性表，操作只能在一端（栈顶）完成。栈内元素的出入顺序为先进后出.

以下为两种栈的存储结构：

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
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<>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<data;
		p=p->next;	
	}
}

#include
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<data<<" ";
			p=p->next;
	}
	cout<>x;
	s.push(x);
	
	//检测插入删除操作 
	s.print();
	 
	//检测栈是否为空
	if(s.empty()) cout<<"栈为空！";
		else cout<<"栈非空！"; 
	 
	return 0;
}

例：进制转换

#include
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<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;
}