数据结构与算法——栈的实现（数组，链表，STL实现）

柔光的暖阳◎ 2022-02-27 23:58 260阅读 0赞

**概念**：栈（stack）是限定只能在表的一段进行插入或删除操作的线性表。在表中允许插入和删除的一端称为“栈顶（top）”，不允许插入和删除的叫“栈底（bottom）”。  
用四种方式实现，要会手写代码，理解栈的底层实现，注意边界条件的考虑

1.  //数组实现栈（要手撕）
2.  //链表实现栈（先判断头指针是否为NULL。否则不能pHead->next）
3.  //STL实现栈操作
4.  //vector实现栈

![在这里插入图片描述][20190323163323920.png]

1.  //数组实现栈（要手撕）

#include <iostream>
    using namespace std;
    
    class MyStack
    {
    public:
    
    	MyStack(int maxSize)
    	{
    		if (maxSize <= 0)
    		{
    			return;
    		}
    		arr = new int[maxSize];//errror :arr = new int(maxSize);
    		if (!arr)
    		{
    			cout << "arr new error " << endl;
    		}
    	}
    
    	void push(int elem)
    	{
    		arr[length++] = elem;
    	}
    	
    	void pop()
    	{
    	if (isEmpty())
    	{
    		return;
    	}
    		arr[--length] = 0;
    	}
    
    	int top()
    	{
    	if (isEmpty())
    	{
    		return;
    	}
    		return arr[length-1];
    	}
    
    	int getLength()
    	{
    		return length;
    	}
    
    	bool isEmpty()
    	{
    		return length == 0;
    	}
    
    	void destoryStack()
    	{
    		if (arr != NULL)
    		{
    			delete[] arr;
    			arr = NULL;
    		}
    		
    		length = 0;
    	}
    
    private:
    	int *arr = NULL;
    	int maxSize = 0;
    	int length = 0 ;
    };
    
    
    
    int main()
    {
    	MyStack myStack(10);
    	myStack.push(10);
    	myStack.push(20);
    	myStack.push(30);
    	
    	int len = myStack.getLength();
    	cout << len << endl;
    	for (int i = 0; i < len; i++)
    	{
    		cout << myStack.top() << " ";//返回但不删除栈头
    		myStack.pop();//删除栈头
    	}
    
    	myStack.destoryStack();
    	return 0;
    }

1.  //链表实现栈

#include <iostream>
    using namespace std;
    
    typedef struct Node
    {
    	Node *next;
    	int data;
    }Node;
    
    class MyStack
    {
    public:
    	MyStack()
    	{
    		pHead = (Node *)malloc(sizeof(Node));//创建节点
    		pHead->data = 0;
    		pHead->next = NULL;
    		cout << "malloc" << endl;
    	}
    	~MyStack()
    	{
    		if (pHead != NULL)
    		{
    			free(pHead);
    			pHead = NULL;
    		}
    			
    		cout << "free" << endl;
    	}
    
    	void push(int elem)
    	{
    		if (pHead == NULL)
    		{
    			return;
    		}
    
    		Node *p = (Node *)malloc(sizeof(Node));//创建节点
    		p->data = elem;
    		p->next = NULL;
    
    		Node *q = pHead->next;
    		pHead->next = p;//连接
    		p->next = q;
    
    		q = NULL;//为下次准备
    		p = NULL;
    	}
    
    	int top()
    	{
    		if (pHead->next != NULL)
    		{
    			return pHead->next->data;
    		}
    	}
    
    	void pop()
    	{
    		Node *p = pHead->next;
    		pHead->next = p->next;
    		p->next = NULL;
    		free(p);
    		p = NULL;
    	}
    
    	bool isEmpty()
    	{
    		if (pHead == NULL || pHead->next == NULL)
    			return true;
    		else
    			return false;
    	}
    
    	void destoryList()
    	{
    		while (pHead != NULL)
    		{
    			Node *p = pHead;
    			pHead = pHead->next;
    			free(p);
    			p = NULL;
    		}
    	}
    private:
    	Node *pHead = NULL;
    };
    
    int main()
    {
    	MyStack myStack;
    	myStack.push(10);
    	myStack.push(20);
    	myStack.push(30);
    	myStack.pop();//删除栈头
    	myStack.push(40);
    	
    	//myStack.destoryList();
    
    	while (!myStack.isEmpty())
    	{
    		cout << myStack.top() << " ";//返回但不删除栈头
    		myStack.pop();//删除栈头
    	}
    	cout << endl;
    
    	return 0;
    }

1.  //STL实现栈操作

#include <iostream>
    #include <stack>
    #include <string>//不加这句，打印会出错 cout << pStack->top() << " ";//返回
    using namespace std;
    
    int main()
    {
    	//stack<string> *pStack = new stack<string>;
    	//pStack->push("123");
    	//pStack->push("1222");
    	//pStack->push("12223");
    	//while (!pStack->empty())
    	//{
    	//	cout << pStack->top() << " ";//返回
    	//	pStack->pop();
    	//}
    
    	stack<int> iStack;
    	iStack.push(10);
    	iStack.push(20);
    	iStack.push(30);
    	cout << iStack.empty() << endl;
    	int len = iStack.size();
    
    	cout << endl;
    	cout << iStack.empty() << endl;
    
    
    	iStack.emplace(22);
    	iStack.emplace(33);
    	iStack.emplace(44);
    	while(!iStack.empty())
    	{
    		cout << iStack.top() << " ";//返回但不删除栈头
    		iStack.pop();//删除栈头,但无返回值
    	}
    	cout << endl;
    }

1.  //vector实现栈

#include <iostream>
    #include <vector>
    using namespace std;
    
    class MyStack
    {
    public:
    
    	MyStack()
    	{
    		//cout << "gouzaohanshu " << endl;
    	}
    
    	void push(int elem)
    	{
    		ivec.push_back(elem);
    	}
    	void pop()
    	{
    		//ivec.pop_back();
    		if (isEmpty())
    		{
    			return;
    		}
    		ivec.erase(ivec.end() - 1);
    	}
    
    	int top()
    	{
    		if (isEmpty())
    		{
    			return 0;
    		}
    		auto it = ivec.end() - 1;
    		return *it;
    	}
    
    	int getLength()
    	{
    		return ivec.size();
    	}
    
    	bool isEmpty()
    	{
    		return ivec.empty();
    	}
    
    	void destoryStack()
    	{
    		if (!ivec.empty())
    		{
    			ivec.clear();
    		}
    	}
    
    private:
    	vector<int> ivec;
    };
    
    
    
    int main()
    {
    	MyStack myStack;
    	myStack.push(10);
    	myStack.push(20);
    	myStack.push(30);
    
    	int len = myStack.getLength();
    	cout << len << endl;
    	for (int i = 0; i < len; i++)
    	{
    		cout << myStack.top() << " ";//返回但不删除栈头
    		myStack.pop();//删除栈头
    	}
    
    	myStack.destoryStack();
    	return 0;
    }

[20190323163323920.png]: /images/20220228/8cf4d49ee34e4207a59b1ee01f133725.png