线性结构的两种应用之一——栈

线性结构的两种应用之一——栈

• 定义：一种可以实现先进后出^[1]的存储结构。

• 分类：静态栈（数组），动态栈（链表）。

• 算法：压栈，出栈。

• 应用：函数调用，中断，表达式求值,内存分配，迷宫。

  ---

• 代码如下：

//2020.4.2/17.05
#include<iostream>
using namespace std;

typedef struct Node
{
	int data;
	struct Node* Next;
}NODE, * PNODE;

typedef struct Stack
{
	PNODE pTop;
	PNODE pBottom;
}STACK, * PSTACK;

void init(PSTACK);
void push(PSTACK,int);
void traverse(PSTACK);
bool pop(PSTACK,int*);
void clear(PSTACK);


int main()
{	
	int val;
	STACK S;
	PSTACK pS = &S;
	init(pS);// ==init(&S);
	push(pS, 5);
	push(pS, 3);
	push(pS, 2);
	push(pS, 0);
	traverse(pS);
	
	if (pop(pS, &val))
	{
		cout << "出栈成功，出栈的元素是" << val;
	}
	else
		cout << "出栈失败";
	traverse(pS);
	clear(pS);
	traverse(pS);
	return 0;

}
void init(PSTACK pS)
{
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	pS->pBottom = pS->pTop;
	pS->pBottom->Next = NULL;
}
void push(PSTACK pS, int val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	pNew->data = val;
	pNew->Next = pS->pTop;
	pS->pTop = pNew;
}
void traverse(PSTACK pS)
{
	PNODE p = pS->pTop;
	while (p->Next != NULL)
	{
		cout << p->data << " ";
		p = p->Next;
	}
}
bool pop(PSTACK pS, int* val)
{
	if (pS->pTop == pS->pBottom)
	{
		return false;
	}
	else
	{
		*val = pS->pTop->data;
		PNODE p = pS->pTop;
		pS->pTop = pS->pTop->Next;
		free(p);
		p->Next = NULL;
		return true;
	}
}
void clear(PSTACK pS)
{	
	PNODE p = pS->pTop;
	while (pS->pTop != pS->pBottom)
	{
		pS->pTop = pS->pTop->Next;
		free(p);
		p = pS->pTop;
	}
}

---

1. 推箱子大家都玩过吧，先推进去只能最后取出来 ↩︎