博客

栈的特点：

1.压入栈时压在最上面

2.弹出栈时弹出最上面

链表的特点：

1.不用一开始就确定长度

2.链表的结构很适合栈的操作，比如压入和弹出

栈的应用：(反转数字或字符串)

源码(反转数字)：

#include<iostream>
using namespace std;
struct Node
{
	int data;
	Node* next;
};
class stack
{
public:
	Node* head;
	int len;	//结点数
public:
	//先实例化头节点
	stack()
	{
		head = new Node;
		head->next = NULL;
		len = 0;
	}
	//释放链表
	~stack()
	{
		if (len == 0)
			delete head;
		else
		{
			Node* p = head->next;
			Node* q = p->next;
			while (p->next != NULL)
			{
				delete p;
				p = q;
				q = p->next;
			}
			delete p;
			delete head;
		}
	}
	//压入栈
	void push(int n)
	{
		Node* temp;
		temp = new Node;
		temp->data = n;
		Node* p = head->next;
		head->next = temp;
		temp->next = p;
		len++;
	}
	//栈是否为空
	bool isempty()
	{
		if (len == 0)
			return 1;
		else
			return 0;
	}
	//打印栈
	void Print()
	{
		Node* head1 = head->next;
		while (head1 != NULL)
		{
			cout << head1->data << " ";
			head1 = head1->next;
		}
		cout << endl;
	}
	//弹出栈
	int pop()
	{
		Node* temp = head->next;
		int n = temp->data;
		head->next = temp->next;
		len--;
		delete temp;
		return n;
	}
};

int main()
{
	stack s;
	string isem = s.isempty() ? "empty" : "fill";
	s.push(1);
	s.push(2);
	s.push(8);
	s.push(3);
	int n = s.len;
	for (int i = 0; i < n; i++)
		cout << s.pop();
}

结果：

依次压入1，2，8，3

依次弹出3，8，2，1