栈的概念及其基本操作–详细（C++）

基本概念及相关术语：

栈是只允许在一端进行插入和删除操作的线性表。

由此可见，栈也是线性表的一种，只是栈的操作受限制的线性表。

栈顶（top）：线性表允许插入和删除的那一段。值得注意的是，栈顶指针top的指向是有些两种方式的，一种是指向栈顶当前元素，一种是指向栈顶的下一位置。两种指向方式对栈的操作影响不大，只是在判断栈顶位置的时候略有差异，本文以指向当前栈顶元素为例。另一种指向方式读者可以自行实践。

栈底（bottom）：固定的，不允许进行插入和删除的另一端。

空栈：不含有任何元素的空表。

栈的存储方式：

栈有两种基本存储方式:

1. 顺序存储：利用一段连续的内存空间进行存储。
2. 链式存储：利用非连续的内存空间存储，元素之间使用指针进行链接。（通常单链表实现，栈顶是表头，栈底的表尾）

链栈的优点：

• 便于多个栈共享存储空间，提高空间效率；
• 不存在栈满上溢的情况

栈的特性：

先进后出

栈的基本操作–顺序存储：

栈的基本操作大致包括6个：

1. InitStack(&s):初始化一个空栈；
2. StackEmpty(s):判断一个在栈是否为空；
3. Push(&s,x):入栈，若栈S未满，这将x加入栈，使之称为栈顶；
4. Pop(&s):出栈，若栈S非空，则弹出栈顶元素；
5. GetTop(s,x):读栈顶元素；
6. DestroyStack(&s):销毁栈，释放栈S所占用内存空间；

1.InitStack(&s):初始化一个空栈：

创建一个空栈后，将栈顶指针指向-1；

void stackinit(sq& s)
{
	s.top = -1;
}

2.StackEmpty(s):判断一个在栈是否为空：

bool stackempty(sq s)
{
	if (s.top == -1) return true; //为空返回true
	else return false; //不为空返回false
}

3.Push(&s,x):入栈，若栈S未满，这将x加入栈，使之称为栈顶：

bool push(sq& s, int x)
{
	if (s.top == maxsize - 1) return false; //如果栈空间满，则不能再插入元素，否则导致内存溢出，直接返回false；
	s.data[++s.top] = x; //栈不满，则可以插入元素，将栈顶指针上移，再将需要插入的元素赋值给栈顶
	return true;
}

4.Pop(&s):出栈，若栈S非空，则弹出栈顶元素：

void pop(sq& s)
{
	if (s.top == -1) cout << "栈空"<<endl; //栈为空，则不能出栈。
	s.top--; //栈不空，能出栈，栈顶指针下移
}

5.GetTop(s,x):读栈顶元素：

int gettop(sq s)
{
	int x; //接收栈顶元素 
	if (s.top == -1) return -1; //栈空，无法读取元素
	x = s.data[s.top]; //栈不空，将当前栈顶元素赋值给x
	return x; //返回x的值，即读取x的值
}

6.DestroyStack(&s):销毁栈，释放栈S所占用内存空间：

void destorystack(sq &s) {
	if (s.top!=-1) free(s.data); //若栈不空，释放栈所占用的内存空间
	s.top = -1;
}

整体代码：

#include<iostream>
using namespace std;
#define maxsize 10
typedef struct {
	int data[maxsize];
	int top;
}sq;
void stackinit(sq& s)
{
	s.top = -1;
}
bool stackempty(sq s)
{
	if (s.top == -1) return true;
	else return false;
}
bool push(sq& s, int x)
{
	if (s.top == maxsize - 1) return false;
	s.data[++s.top] = x;
	return true;
}
void pop(sq& s)
{
	if (s.top == -1) cout << "栈空"<<endl;
	s.top--;
}
int gettop(sq s)
{
	int x;
	if (s.top == -1) return -1;
	x = s.data[s.top];
	return x;
}
void destorystack(sq &s) {
	if (s.top!=-1) free(s.data);
	s.top = -1;
}
int main() {
	sq s1;
	stackinit(s1);
	for (int i = 0; i < 10; i++)
	{
		push(s1, i);
	}
	while (!stackempty(s1))
	{
		cout << gettop(s1)<< " ";
		s1.top--;
	}	
	cout << endl;
	for (int i = 0; i < 10; i++)
	{
		push(s1, i);
	}
	pop(s1);
	while (!stackempty(s1))
	{
		cout << gettop(s1) << " ";
		s1.top--;
	}
	destorystack(s1);
	return 0;
}

执行结果：

链表的基本操作–链式存储

链式存储就是对链表的操作，在这里可以设置头节点也可以不设置头节点。

我这里以单链表有头结点的头插法为例。

链栈的节点定义：

typedef struct Linknode {
	int data;
	struct Linknode* next;
};

1.InitStack(*head):初始化一个空栈：

void initlink(Linknode *head) {
	if (head == nullptr) cout << "分配失败" << endl;
	else head->next = nullptr;
}

2.StackEmpty(*head):判断一个在栈是否为空：

bool isempty(Linknode* head) {
	if (head->next == nullptr)  return true;
	else return false;
}

3.Push(*head,x):入栈:

void enqueue(Linknode* head,int x) {
	Linknode* L = new Linknode[sizeof(Linknode)];
	L->data = x;
	L->next = head->next;
	head->next = L;
}

4.Pop(*head):出栈:

void dequeue(Linknode* head)
{
	Linknode* L = new Linknode[sizeof(Linknode)];
	L = head->next;
	head->next = L->next;
	delete[] L;
}

5.GetTop(s,x):读栈顶元素：

void gethead(Linknode* head)
{
	int x;
	x = head->next->data;
	cout << x << endl;
}

6.DestroyStack(&s):销毁栈:

void DestroyStack(Linknode* head) {
	Linknode* p = new Linknode[sizeof(Linknode)];
	p = head->next;
	if (!isempty(head)) {
		while (head->next != nullptr)
		{
			head->next = p->next;
			delete[]p;
			p = head->next;
		}
	}
	delete[]p;
}

整体代码：

#include<iostream>
using namespace std;
typedef struct Linknode {
	int data;
	struct Linknode* next;
};
void initlink(Linknode *head) {
	//head = new Linknode[sizeof(Linknode)];
	if (head == nullptr) cout << "分配失败" << endl;
	else head->next = nullptr;
}
bool isempty(Linknode* head) {
	if (head->next == nullptr)  return true;
	else return false;
}
void enqueue(Linknode* head,int x) {
	Linknode* L = new Linknode[sizeof(Linknode)];
	L->data = x;
	L->next = head->next;
	head->next = L;
}
void dequeue(Linknode* head)
{
	Linknode* L = new Linknode[sizeof(Linknode)];
	L = head->next;
	head->next = L->next;
	delete[] L;
}
void gethead(Linknode* head)
{
	int x;
	x = head->next->data;
	cout << x << endl;
}
void DestroyStack(Linknode* head) {
	Linknode* p = new Linknode[sizeof(Linknode)];
	p = head->next;
	if (!isempty(head)) {
		while (head->next != nullptr)
		{
			head->next = p->next;
			delete[]p;
			p = head->next;
		}
	}
	delete[]p;
}
int main() {
	Linknode* h = new Linknode[sizeof(Linknode)];
	initlink(h);
	if (isempty(h)) cout << "链表空" << endl;
	for (int i = 0; i < 10; i++)
	{
		enqueue(h, i);
	}
	gethead(h);
	dequeue(h);
	gethead(h);
	DestroyStack(h);
	return 0;
}

执行结果：