C++数据结构——栈

1.简介

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶，栈的特点是先进后出（后进先出）

2.基本结构

栈的基本结构如下图

我们可以发现其实栈的结构图横过来看就是一张使用了头插法的表，所以我们在创建时按照表的创建方法就行了

3.基本操作

栈的基本操作只有入栈(Push)、出栈(Pop)、判空(isEmpty)

3.1栈的类型声明

typedef struct node* Node;
struct node{
	int Element;
	Node next;
};

3.2入栈

void push(Node head,int x){//注意是传入参数是头结点
	Node temp=new node;
	temp->Element=x;
	temp->next=head->next;
	head->next=temp;
}

3.3出栈

void pop(Node head){
	if(!isEmpty(head)){
		Node temp=new node;
		temp=head->next;
		head->next=temp->next;
		delete(temp);
	}
}

3.4判空

bool isEmpty(Node head){
	return head->next==NULL;
}

这些操作与表那一节一模一样，如果有不懂的可以看我之前的博客

4.完整代码

#include<iostream>
using namespace std;
typedef struct node* Node;
struct node{
	int Element;
	Node next;
};
void push(Node head,int x){//参数节点注意是头结点
	Node temp=new node;
	temp->Element=x;
	temp->next=head->next;
	head->next=temp;
}
bool isEmpty(Node head){
	return head->next==NULL;
}
void pop(Node head){
	if(!isEmpty(head)){
		Node temp=new node;
		temp=head->next;
		head->next=temp->next;
		delete(temp);
	}
}
void print(Node head){
	while(head->next){
		cout<<head->next->Element<<" ";
		head=head->next;
	}
	cout<<endl;
}
//输入5个数入栈，出栈一次并输出
int main(){
	int x;
	Node head=new node;
	head->next=NULL;
	for(int i=0;i<5;i++){
		cin>>x;
		push(head,x);
	}
	pop(head);
	print(head);
	return 0;
}