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运行这些代码呀

[user-hlp]

//利用双端栈实现类似网页浏览前进后退的功能
#include<stdio.h>
#include<stdlib.h>

#define MAX 100

struct page_manager
{
    char **page;
    int lefttop;
    int righttop;
};
struct page_manager* init(){
    struct page_manager* p=(struct page_manager*)malloc(sizeof(struct page_manager));
    p->page=(char**)malloc(sizeof(char*)*MAX);
    p->lefttop =-1;
    p->righttop = MAX;
}
void add(struct page_manager *p,char *page){//增加新的网页
    if(p->lefttop == p->righttop-1){
        printf("stack is full!");
        return;
    }
    p->page[++p->lefttop] = page;  
}
char *forward(struct page_manager* p){ //按前进键
    if(p->righttop == MAX) return NULL;
    char *page = p->page[p->righttop++];
    p->page[++p->lefttop] = page;
    return page; 
}
char *backward(struct page_manager* p){ //按后退键
    if(p->lefttop == -1) return NULL;
    char *page=p->page[p->lefttop--];
    p->page[--p->righttop] = page;
    return page;
}
int main(){
    struct page_manager* p =init();
    add(p,"page1");add(p,"page2");add(p,"page3");
    add(p,"page4");add(p,"page5");add(p,"page6");
    int oper = 1;
    while(oper!=0){
        printf("input:");
        scanf("%d",&oper);
        if(oper == 1) printf("%s\n",forward(p));
        else if(oper == -1) printf("%s\n",backward(p));
    }
}

[Q1ufeng]

好好好，感谢作者

[zhengjiaxi]

链表实现栈的代码中，C语言实现ListNode并未定义；

[zhengjiaxi]

INT_MAX也未定义

[krahets]

请前往仓库 https://github.com/krahets/hello-algo 下载完整代码，并在本地运行

[zhengjiaxi]

动态数组实现栈的操作过程中，MAX_SIZE未定义，出栈时并未做判空处理；另外数组动态扩容功能并没有实现；

[zhengjiaxi]

另外在动态分配内存空间过程中，并未对扩容的数组进行判空处理，如果动态内存分配失败，调用分配失败的空间，会导致程序崩溃；

[krahets]

MAX_SIZE未定义

请前往仓库 https://github.com/krahets/hello-algo 下载完整代码

出栈时并未做判空处理

出栈的判空处理在调用的 peek() 函数中执行

数组动态扩容功能并没有实现

这不是本章的重点，我们用一个长度为 MAX_SIZE 的大数组来做代替

[quan-z00]

析构函数是删除该数据结构吗，为什么要叫析构啊

[2510466299]

析构函数是用来释放自己开辟在栈空间的动态空间的，因为在使用裸指针的情况下这些空间并不会在程序运行完时自动释放，这就有可能造成内存泄漏。

[TQLeung]

链表实现的栈，List 转 Array 用 迭代器会比递归调用好吧？

/* 将 List 转化为 Array 并返回 */
    pub fn to_array(&self, head: Option<&Rc<RefCell<ListNode<T>>>>) -> Vec<T> {
        if let Some(node) = head {
            let mut nums = self.to_array(node.borrow().next.as_ref());
            nums.push(node.borrow().val);
            return nums;
        }
        return Vec::new();
    }

[deyu9999]

浏览器的前进后退，不用出栈操作，用数组形式来实现，单独维护当前页的数组索引就可以实现前进后退了吧，一个数组就行

[krahets]

存储用数组，“逻辑”上还是栈

[dawangbowen]

js的pop实现是不是将出栈的节点的next置为null，更合理一些？

[dawangbowen]

这样方便垃圾回收

[dawangbowen]

这里是我写的js代码，有问题的话可以指出

pop() {
    if(this.#stackPeek) {
      const resNode = this.#stackPeek;
      this.#stackPeek = this.#stackPeek.next;
      resNode.next = null;
      this.#stackSize--;
      return resNode.val;
    } else {
      return undefined;
    }
}

[Lwinhow]

/* 入栈 */
public void push(int num) {
    ListNode node = new ListNode(num);
    node.next = stackPeek;
    stackPeek = node;
    stkSize++;
}

这里的入栈，新建一个节点，然后指向头节点（栈顶），然后这个新建节点的地址赋给了栈顶，不会形成环形链表吗，是哪里理解错了吗？

[haerker]

一开始栈顶节点指向null，新建节点入栈自然会压入栈顶，所以指向栈顶节点，此时，一开始指向null的栈顶结点因为加入了新的值，需要上移，指向加入的那个节点，也就是新建节点。我是这样理解

[joumm]

def is_empty(self) -> bool:
        """判断栈是否为空"""
        return self._stack == []

python这里是不可以直接return self._stack，判断是否相等是不有点多余？

[krahets]

是的。为使语义清晰，建议用：

    def is_empty(self) -> bool:
        """判断栈是否为空"""
        return self._size == 0

[joumm]

好的，感谢解答

[mithrasu]

在初始化列表时，系统会为列表分配“初始容量”，该容量可能超出实际需求。
空间效率这里所讲的列表应该是指数组吧

[krahets]

是的，列表是一种抽象数据结构，可以基于数组或链表实现。在各编程语言中，列表通常基于数组实现。因此在本书中，除特别说明外，可以将“列表”和“动态数组”看作同一概念

[miaotenone]

return [.. stack];

找个半天才发现是一个语法糖，展开运算符（集合表达式中的 ..）可将其参数替换为该集合中的元素。

[Liu2126]

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

[Liu2126]

C++代码

[krahets]

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

[wbzyo]

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

[krahets]

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

[LUZ-PINK]

打卡打卡，25一定上岸呀