chapter_stack_and_queue/stack/

[giscus[bot]]

chapter_stack_and_queue/stack/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_stack_and_queue/stack/

[NiceIICU]

想问一下，用链表实现栈的pop操作时，删除栈顶还需要把原来的栈顶的内存delete掉吗，或者说进行或不进行delete都行呢？

[NiceIICU]

因为这里每次入栈的时候都通过new在堆中开辟内存了，但是在pop操作时仅仅是改变栈顶，并没有把原本栈顶在堆中占据的内存释放掉

[NiceIICU]

我给出一个方案不知道是否正确，在链表实现栈的类里的pop函数里加上两行代码，在最开始，ListNode* temp=stackTop，临时创建一个变量记录原本的栈顶，之后在完成更换栈顶为下一个结点之后，再delete这个temp，这样temp指向的堆中的内存（通过new开辟的内存）就会被释放，并且pop函数结束后，由于这里的temp是在成员函数中进行定义的，它的内存默认被开辟在栈中，pop函数结束后他就自动被释放了，我尝试了一下代码是没有问题的

[krahets]

哈喽！在 C 和 C++ 中，最好手动释放内存，比如：

    /* 出栈 */
    int pop() {
        int num = top();
        ListNode *tmp = stackTop;
        stackTop = stackTop->next;
        // 释放内存
        delete tmp;
        stkSize--;
        return num;
    }

Java, Python 等语言有相对可靠的自动内存回收机制，一般不用手动释放内存。

[NiceIICU]

收到谢谢啦

[JackCmd233]

仅针对Java，给大家补充一点知识：Java中是有专门的栈实现类的，就是java.util.Vector，Stack在Java中是继承于Vector，这里说的是1.8版本，使用了Vector底层的数据结构，底层都是使用数组实现的。
具有以下的特点：

• 先进后出（FILO）
• 继承于Vector,同样基于数组实现
• 由于使用的几乎都是Vector，Vector的操作都是线程安全的，那么Stack操作也是线程安全的。

以后大家在LeetCode中刷题时，会经常用到这个类，可以提前先了解一下。

参考文章：https://www.cnblogs.com/Damaer/p/15783020.html

[JackCmd233]

应该是java.util.Stack

[is-liu]

这个类效率和使用Deque接口来实现的栈相比效率太低，在leetcode上或者是平时环境基本不需要考虑线程是否安全的问题，并且ArrayList LinkedList来实现的栈功能上也比Stack更广泛。如果需要使用线程安全的环境的话，可以使用Collections.synchronizedList来包装ArrayList或者LinkedList`让它变成线程安全的类

[cs7eric]

现在是不建议使用，或者说很少使用 vector 实现的 stack的，他的效率较低，可以使用 ArrayDeque

[yuelinxin]

请问出栈的这个方法中返回被pop节点的值的意义是什么？

def pop(self):
        num = self.peek()
        self.__peek = self.__peek.next
        self.__size -= 1
        return num

[krahets]

哈喽，这是栈 pop() 接口的设计习惯，大多数语言的 pop() 方法都会返回出栈元素。
这样的设计的逻辑是，我们一般执行出栈操作，都是要对出栈元素做一些操作的。比如，我们在洗盘子，把最上面的盘子取出来，下一步应该拿着它去洗了。

[cs7eric]

洗盘子这个例子简直太生动了

[fbigm]

/* 出栈 */
void pop() {
    int num = top();
    ListNode *tmp = stackTop;
    stackTop = stackTop->next;
    // 释放内存
    delete tmp;
    stkSize--;
}

c++的版本，pop接口应该增加int返回值并在实现最后return num,以保持设计逻辑的同步（栈 pop() 接口的设计习惯，一般都会返回出栈元素），要不然int num = top();就多余了。

没找到修改的办法，只好评论麻烦作者自己修改了

[krahets]

哈喽，C++ 代码做了特殊处理，没有返回值，因为 C++ 内置的栈的 pop() 是没有返回值的。

[lymfwz]

Deque stack = new LinkedList<>();这样是否可以呢，如果是当作队列直接换个名称

[krahets]

没问题～ Deque 既可以用作栈、也可以用作队列

[is-liu]

在Java语言中
Deque接口继承了Queue接口，是双向队列，在不需要考虑线程安全的时候效率会很高。
Stack 类继承了Vector类，性能是不如ArrayList和LinkedList的。并且在jdk不断的迭代中，需要线程安全的环境可以用Collections.synchronizedList方法转为线程安全的，所以目前使用Stack进行栈操作比较少。

[zxz2004626]

初学者很多只学C，想求个C语言的代码~非常感谢

[krahets]

🫡收到，C 代码正在完善中

[abigail22222]

栈也可以用作括号检查

[abigail22222]

各种成对的括号

[xiaobao1231]

看了你的评论我去把力扣做了

[CuiKing1270]

麻烦问一下

[CuiKing1270]

/* 出栈 java基于链表实现的出栈操作 这里不需要将要出去元素的next设置为空吗? */
public int pop() {
    int num = peek();
    stackPeek = stackPeek.next;
    stkSize--;
    return num;
}

[krahets]

Hi 也可以显式地将 next 设置为空，不设置也行，stackPeek = stackPeek.next; ，这一步后原来的 stackPeek 已经无法被访问到了，可以视为已经从链表中删除了。

[Wizarder54088]

可以自动回收的吧

[CuiKing1270]

好的，谢谢你 超级开心😁帮我解答了我得困惑

…

---Original--- From: "Yudong ***@***.***&gt; Date: Fri, Apr 7, 2023 16:59 PM To: ***@***.***&gt;; Cc: ***@***.******@***.***&gt;; Subject: Re: [krahets/hello-algo] chapter_stack_and_queue/stack/ (Discussion#64) Hi 也可以显式地将 next 设置为空，不设置也行，stackPeek = stackPeek.next; ，这一步后原来的 stackPeek 已经无法被访问到了，可以视为已经从链表中删除了。 — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***&gt;

[F9rozen]

典型应用中
1.浏览器前进后退和软件的撤销应该是双向链表实现的吧
2.函数调用栈这个能称作内存管理么，我理解的内存管理指的内存空间的分配和释放。运算符匹配是一个很好的栈的应用

[krahets]

1. 从逻辑结构上看，核心是栈。使用双向队列是因为方便实现一些额外操作，这个在双向队列章节有提到。
2. 内存管理是一个比较宽泛的概念。在函数调用栈中，系统利用栈实现了合理的“内存空间的分配和释放”。

运算符匹配是一个很好的栈的应用 确实

[pzy25]

您好k哥，链表出栈的c语言代码，
ListNode *tmp = s->top;
s->top = s->top->next;
是不是把tmp写成s了
嘻嘻

[Gonglja]

这部分是没有问题的，
当出栈时，栈顶指针下移（使用 tmp 指针临时保存栈顶元素地址），指针下移结束后，释放掉栈顶元素所占用的空间

[pzy25]

谢谢g哥哥的回复，我明白了它 的意思

[zhuasdfg]

手敲了一遍链表实现的栈，很有成就感

[is-liu]

在Java中，Stack是一种继承自Vector的类，用于实现后进先出（LIFO）的数据结构。然而并不推荐使用Stack，主要有以下几个原因：

• 1.使用不直观：Stack的API和方法与Vector非常相似，对于不熟悉Java的人来说可能不太直观。而且，与ArrayList和LinkedList等其他集合类型相比，Stack的功能并不明显。
• 2.功能有限：Stack的主要操作是push、pop和peek，用于在堆栈上添加、删除和查看元素。然而，它缺乏一些常用的数据结构操作，如排序、查找或随机访问。这使得它在一些通用场景下不太实用。
• 3.使用其他数据结构更灵活：Java提供了许多其他数据结构，如ArrayList、LinkedList、ArrayDeque等，它们提供了更多功能和灵活性。例如，如果你需要实现一个栈，你可以使用LinkedList或ArrayDeque，它们提供了更好的性能和更多的功能。
• 4.线程安全问题：由于Stack继承自Vector，它是线程安全的。然而，在大多数情况下，使用线程安全的集合并不是必要的，因为它们通常在单线程环境中使用。此外，如果多个线程试图修改Stack，可能会导致竞争条件和其他并发问题。
• 5.性能问题：由于Stack是线程安全的，它的性能可能不如其他非线程安全的集合。特别是在高并发环境下，使用线程安全的集合可能会影响性能。

综上所述，Java更倾向于使用其他数据结构来实现栈的功能，如ArrayList、LinkedList或ArrayDeque。这些数据结构提供了更好的性能、更多功能和更高的灵活性。

[XMNXofficial]

[XMNXofficial]

谢谢!我知道啦,在上一章中

[ZhaiJason]

作者您好！
想请教一下LinkedListStack里pop方法中为什么包含了一行int num = top()，感谢！

[krahets]

这步是在获取栈顶元素，以便在最后 return 它。

[tomlfigure]

怎么在vs studio运行这些代码呀

[Liu2126]

基于链表的实现代码中出现一个报错：未定义标识符freeMemoryLinkedList，请问该函数定义在哪里呢？

[Liu2126]

C++代码

[krahets]

请前往 https://github.com/krahets/hello-algo 下载配套代码，可一键运行

[wbzyo]

5.1.2.1提到对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为“头插法”。意思尾插法也可以实现栈吗，我查资料说，头插法适用于栈FILO，因为它存储链表是逆序的，尾插法适用于队列这种先进先出FIFO的，因为它是顺序的，还是说头插法和尾插法都能用来实现栈，也都能用来实现队列呢？

[krahets]

是的，都可以的，只是代码实现会多一行 or 少一行的问题。头插法的好处是我们本来就记录了头节点 head ，因此方便操作

[1i9htning]

如果用尾插法实现stack的话，在pop操作时会先遍历一遍整个链表，导致效率为𝑂(𝑛)；除非使用双向循环链表

[krahets]

@1i9htning 我们可以用一个变量始终指向尾节点，这样就可以避免遍历链表了。尾插法可以达到和头插法一样的效率，只是代码实现会稍冗长。

[aerzha]

@krahets 并不可以吧，尾插法单链表实现，pop 操作没法搞了

[LUZ-PINK]

打卡打卡，25一定上岸呀

[Hihongboyang]

作者你好, 在基于链表实现栈的rust 代码中

pub struct LinkedListStack<T> {
    stack_peek: Option<Rc<RefCell<ListNode<T>>>>, // 将头节点作为栈顶
    stk_size: usize,                              // 栈的长度
}

根据上面的定义, 入栈操作应该是这样吧

     /* 入栈 */
    pub fn push(&mut self, num: T) {
        let node = ListNode::new(num);
        node.borrow_mut().next = self.stack_peek.take();
        self.stack_peek = Some(Rc::new(RefCell::new(node)));   <-----
        self.stk_size += 1;
    }

[lishengyu]

go代码里面，基于链表实现栈的操作，入栈使用PushBack()进行插入，那么这里就应该是 “将链表的尾节点视为栈顶，头节点视为栈底”

[lovebuizel]

基于数组的实现中JS和TS的peek方法為何是叫top而不是peek呢?有什麼考慮嗎?

[921000]

public class ArrayStack {

/**
 * 栈 数组
 */
private int[] stackArray;

/**
 * 栈 大小
 */
private int maxSize;

/**
 * 栈顶位置
 */
private int top;


public ArrayStack(int size) {
    this.maxSize = size;
    stackArray = new int[size];
    // 空栈 时栈顶为 -1
    top = -1;
}

public ArrayStack() {
    this.maxSize = 10;
    stackArray = new int[10];
    // 空栈 时栈顶为 -1
    top = -1;
}


public boolean isEmpty() {
    return top == -1;
}


public boolean isFull() {
    return top == maxSize - 1;
}


public void push(int data) {
    if (isFull()) {
        // 动态扩容
        int[] newStackArray = new int[maxSize * 2];
        System.arraycopy(stackArray, 0, newStackArray, 0, maxSize);
        maxSize = maxSize * 2;
        stackArray = newStackArray;
    }
    stackArray[++top] = data;
}


public int pop() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    return stackArray[top--];
}


public int peek() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    return stackArray[top];
}

public int size() {
    return top + 1;
}

}
基于数组实现，支持扩容

[yanhua-volvo]

pop是stackArray[top], 不是top--

[921000]

public class LinkStack {

// 指向栈顶的节点
private Node top;

private int size;

private class Node {

    // 节点数据
    private final int data;

    // 指向下一个节点
    private Node next;

    public Node(int data) {
        this.data = data;
    }
}


public LinkStack() {
    top = null;
    size = 0;
}

public boolean isEmpty() {
    return top == null;
}

/**
 * 入栈
 */
public void push(int data) {
   Node newNode = new Node(data);
   newNode.next = top;
   top = newNode;
   size = size + 1;
}

/**
 * 出栈
 */
public int pop() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    int data = top.data;
    top = top.next;
    size = size - 1;
    return data;
}

/**
 * 查询栈顶元素
 */
public int peek() {
    if (isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    return top.data;
}


/**
 * 获取长度
 */
public int size() {
    return size;
}

}
基于链表 实现栈

[selfboot]

做了一个可视化演示，欢迎来玩～
stack

[wsndehm]

怎么做的可以啊

[selfboot]

用 AI 辅助写的。。代码是开源的哈

[xlyyddy]

入栈操作需要初始化节点对象并修改指针，因此效率相对较低。不过，如果入栈元素本身就是节点对象，那么可以省去初始化步骤，从而提高效率。
上面这段话不太理解，主要是分不清入栈元素是节点对象和不是有什么区别（就是什么样的代码栈入的是节点对象，什么代码栈入的不是节点对象），有友友有代码表现一下两者的区别吗，

[chunleiding]

比如说int类型的栈;你入栈的时候传一个int类型的值;在使用链表实现的栈里面需要通过这个值初始化一个节点作为链表的连接;因为链表是通过节点的指针连接到一起的,节点除了持有对num的引用之外还有左右指针;如果直接在栈的实现里面传入节点,就节省了初始化的流程, 但是在栈外面还是得初始化的不过和栈这个数据结构无关了,操作不是在栈内进行的;使用数组的话就没有这种担心,因为数组不需要再对数据进行新的包装了;不过数组的缺点就是初始容量不够动态扩容的话会浪费空间;

[jack1415926]

你好，我想请问一下，在printStack函数中使用模板的意义所在，以及不使用模板的区别
template void printStack(stack stk) {
// Reverse the input stack
stack tmp;
while (!stk.empty()) {
tmp.push(stk.top());
stk.pop();
}
// Generate the string to print
ostringstream s;
bool flag = true;
while (!tmp.empty()) {
if (flag) {
s << tmp.top();
flag = false;
} else
s << ", " << tmp.top();
tmp.pop();
}
cout << "[" + s.str() + "]" << '\n';
}

[lin3187]

各位道友好：
在于5.1.2章节中，基于链表实现栈的C语言代码（linkedlist_stack.c）：
是否缺少了结构体'ListNode'的定义。

typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;

[lin3187]

#include <stdio.h>
#include <stdlib.h>

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

// 初始化一个栈，“哨兵”节点或者“头节点”
Node *intStack()
{
Node *S = (Node *)malloc(sizeof(Node));
S->next = NULL;
S->data = 0;
return S;
}

int isEmpty(Node *S)
{
return (S->next == NULL || S->data == 0);
}

int getTop(Node *S)
{
if (isEmpty(S))
{
printf("栈为空！\n");
return -1;
}
else
{
// 保存栈顶元素,
return S->next->data;
}
}

int pop(Node **S){
if (isEmpty(S)){
printf("栈为空！\n");
}else{
// 保存栈顶元素
Node node = (*S) -> next;
// 栈顶元素指向下一个元素
(*S) -> next = node -> next;
// 释放栈顶元素
free(node);
// 栈的元素个数减1
(*S) -> data --;
return node->data;
}
}

void push(Node *S,int data){
Node node = (Node *)malloc(sizeof(Node));
node->data = data;
// 将新元素的下一个元素指向栈顶
node->next = (*S) -> next;
// 将头结点指向新元素
(*S) -> next = node;
(*S) -> data ++;
}

void printStack(Node *S){
Node *node = S->next;
while(node){
printf("%d ->",node->data);
node = node->next;
}
printf("NULL\n");
}

int main() {
Node *S = intStack();
push(&S, 1);
push(&S, 2);
push(&S, 3);
push(&S, 4);
push(&S, 5);
printStack(S);
pop(&S);
pop(&S);
pop(&S);
pop(&S);
// pop(&S);
printStack(S);
return 0;
};

如果我加了一个“哨兵节点”，相对于原来的代码有什么较差的区别，是可用性变差了吗？

[ShijianWen3]

区别不大

[Kaidaotum1]

为什么在python实现中，类的属性中stack前面要加个下划线？

def init(self):
"""构造方法"""
self._stack: list[int] = []

[ListenCode]

_开头的属性在pyhton中相当于其他语言中的protected var，表示此变量不希望被类的实例变量直接访问。https://docs.python.org/zh-cn/3/tutorial/classes.html#private-variables

[ListenCode]

例如

stack_obj = ArrayStack()

# 不希望出现直接调用_stack属性
stack_obj._stack[1]

[izip-aTLa2]

打卡

[Zhao-Yi-Ya]

我使用的是C版本，对于链表和数组实现出栈的代码中，出栈的时候加上对栈判断是否为空是否更规范一些？