2024.3.18
芝士wa
参考视频：bilibli-数据结构-栈
栈 Stack
定义
栈是一个列表或集合，它的插入和删除只能在一端进行，称之为栈顶。栈是一种LIFO(Last in first out)型ADT。
栈的基本操作：
- 入栈
- 出栈
- 返回栈顶元素
- 判断是否为空
以上操作的时间复杂度均为O(1)。
应用
- 递归
- 实现撤回操作
- 编译器语法检查，括号配对
- 前缀和后缀的计算，与中缀的转换
用数组实现栈很简单，在此不做赘述，下面介绍如何用链表实现一个栈
#pragma once
#include <iostream>
using namespace std;
class EmptyStackException : public std::exception {
public:
const char* what() const noexcept override {
return "Stack is empty.";
}
};
template<class T>
class Node
{
public:
T data;
Node* next;
};
template<class T>
class Stack
{
public:
Node<T>* top;
Stack();
~Stack();
void push(T x);
void pop();
void print();
T gettop();
bool isEmpty();
};
template<class T>
Stack<T>::Stack()
{
top = NULL;
}
template<class T>
Stack<T>::~Stack()
{
}
template<class T>
void Stack<T>::push(T x)
{
Node<T>* tmp = new Node<T>;
tmp->data = x;
tmp->next = top;
top = tmp;
}
template<class T>
void Stack<T>::pop()
{
Node<T>* tmp = new Node<T>;
if (top == NULL) {
return;
}
tmp = top;
top = top->next;
delete(tmp);
}
template<class T>
T Stack<T>::gettop()
{
if (top == NULL) {
throw EmptyStackException();
}
return top->data;
}
template<class T>
bool Stack<T>::isEmpty()
{
if (top == NULL) {
return true;
}
return false;
}
template<class T>
void Stack<T>::print()
{
if (top == NULL) {
cout << "null,nothing to print" << endl;
return;
}
Node<T>* tmp = top;
while (tmp != NULL)
{
cout << tmp->data << endl;
tmp = tmp->next;
}
return;
}
注意：当top为NULL时，由于T是泛型类型，没有一个默认值，因此无法直接返回一个默认值。一种常见的做法是抛出一个异常，表示栈为空。
leetcode-206反转链表
题目链接
有三种解题方法，分别是双指针法，递归法，栈。
由于栈具有先入后出的特性，因此可以解决反转问题。
栈方法的代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) {
return NULL;
}
stack<struct ListNode*> s;
ListNode* tmp = head;
while (tmp != NULL) {
s.push(tmp);
tmp = tmp->next;
}
tmp = s.top();
head = tmp;
s.pop();
while (!s.empty()) {
tmp->next = s.top();
s.pop();
tmp = tmp->next;
}
tmp->next = NULL;
return head;
}
};
总结
介绍了栈的基本特性，用链表的方式实现了栈，针对栈的应用，给出了leetcode-206题的解法。
标签：tmp,return,top,template,NULL,Stack From： https://www.cnblogs.com/cheese-wa/p/18080903