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

[Ares-bit]

自己写的时候每次push都把新节点挂到top后面，结果写pop的时候卡住了，怎么想也想不到如何找到pop的前驱，甚至想到了双向链表。。。结果看作者的答案，每次push把top挂到新节点后面，怎么就没想到头插法呢，还是菜啊。。。。

[mmm369225]

c++代码中，/* 初始化栈 */
stack stack;这样写虽然没有问题，但是，变量名stack和容器名一样，会不会可能在后续有什么麻烦呀？有高手知道吗？

[Wacccccc]

使用stack时需要包含stack头文件且需要在std命名空间下，即std：：stack

[elk-9527]

对电脑应该没啥麻烦，就是对脑子有点麻烦

[xuaidongx]

#ifndef __CUSTOMSTACK_HPP__
#define __CUSTOMSTACK_HPP__

/**
 * @file customstack.hpp
 * @brief 基于数组和链表的栈
 * @example 
 * stackByList<int> stack{1, 2, 3, 4, 5, 6, 7};
 * stackByVector<int> stack{1, 2, 3, 4, 5, 6, 7};
 */

#include <cstddef>
#include <vector>
#include <memory>
#include <chrono>

template<typename T>
class linklist;

template<typename T, template<typename> typename ContainerType = std::vector>
class customStack
{
public:
    template<typename... Args>
    customStack(Args&&... args)
    {
        (push(std::forward<Args>(args)),...);
    };
    ~customStack(){};

    void push(const T& v){ m_elements.push_back(v);}
    void pop() { if (!m_elements.empty()) m_elements.pop_back();}
    const T& top() const {return m_elements.back();}
    T& top() {return const_cast<T&>(const_cast<const customStack*>(this)->top());}
    bool empty() const {return m_elements.empty();}
    std::size_t size() const {return m_elements.size();}
private:
    ContainerType<T> m_elements;
};

template<typename T>
class linklist
{
struct linknode
{
    T value;
    std::shared_ptr<linknode> next;
    linknode(const T& v, std::shared_ptr<linknode> node):value(v), next(node){};
};
public:
    void push_back(const T& v)
    {
       m_top = std::make_shared<linknode>(v, m_top);
       ++m_size;
    }

    void pop_back()
    {
        m_top = m_top->next;
        --m_size;
    }

    const T& back() const {return m_top->value;} 
    bool empty() const {return m_size == 0;}
    std::size_t size() const {return m_size;}
private:
    std::size_t m_size{0};
    std::shared_ptr<linknode> m_top{nullptr};
};

template<typename T>
using stackByVector = customStack<T>;

template<typename T>
using stackByList = customStack<T, linklist>;

#endif //__CUSTOMSTACK_HPP__

[bessy1986]

pop函数中
ListNode *tmp = s->top;
s->top = s->top->next;
free(tmp);
为什么不直接写成 s->top = s->top->next;

[XProfessorJ]

JS 版本:
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedListStack {
constructor() {
this.top = null;
this.stackSize = 0;
}

isEmpty() {
return this.stackSize === 0;
}

push(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.top = newNode;// 如果栈为空，直接将 this.top 指向 newNode,注意这里是引用赋值哦,所以23行的地方top原先的值不会被垃圾回收掉
} else {
newNode.next = this.top;
this.top = newNode;//此处也是引用赋值
}
this.stackSize++;
}

pop() {
  if (this.isEmpty()) {
    throw new Error("Stack is Empty");
  }
  const num = this.top.value;
  this.top = this.top.next;
  this.stackSize--;
  return num;
}

peek() {
  return !this.top ? new Error("Stack is Empty") : this.top.value;
}

toArray() {
  let node = this.top;
  const res = new Array(this.top);
  for (let i = res.length - 1; i >= 0; i--) {
    res[i] = node.val;
    node = node.next;
  }
  return res;
}

}

class ArrayStack{
constructor(){
this.stack = [];
}
push(num){
this.stack.push(num)
}
pop(){
if(this.stack.length==0) throw new Error("Stack is Empty")
this.stack.pop();
}
}

[XProfessorJ]

class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedListStack {
constructor() {
this.top = null;
this.stackSize = 0;
}

isEmpty() {
return this.stackSize === 0;
}

push(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.top = newNode; // 如果栈为空，直接将 this.top 指向 newNode,注意这里是引用赋值哦,所以23行的地方top原先的值不会被垃圾回收掉
} else {
newNode.next = this.top;
this.top = newNode; //此处也是引用赋值
}
this.stackSize++;
}

pop() {
if (this.isEmpty()) {
throw new Error("Stack is Empty");
}
const num = this.top.value;
this.top = this.top.next;
this.stackSize--;
return num;
}

peek() {
return !this.top ? new Error("Stack is Empty") : this.top.value;
}

toArray() {
let node = this.top;
const res = new Array(this.top);
for (let i = res.length - 1; i >= 0; i--) {
res[i] = node.val;
node = node.next;
}
return res;
}
}

class ArrayStack {
constructor() {
this.stack = [];
}
push(num) {
this.stack.push(num);
}
pop() {
if (this.stack.length == 0) throw new Error("Stack is Empty");
this.stack.pop();
}
}

[ivy3h]

之前学data structure的时候只是单纯学习了stack的概念&代码，现在结合应用、array与linked list的对比就一下子变得更有趣了！

[elk-9527]

在linkedlist_stack.cpp好像没有定义freeMemoryLinkedList()这个函数，我写成（C++版本）
~LinkedListStack() {
// 遍历链表删除节点，释放内存
while (stackTop) {
ListNode* temp = stackTop;
stackTop = stackTop->next;
delete temp;
}
}

[zhjxhjj]

Java数组实现：

public class ArrayStacks<E> {

	//真实存储元素的数组
	private Object[] array;
	
	//栈大小
	private int size = 0;
	
	/* 一、初始化 */
	
	//空参构造，初始默认长度为20
	public ArrayStacks() {
		this.array = new Object[20];
	}
	
	//有参构造，接收Collection接口的实现类初始化数组元素
	public ArrayStacks(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
            	array = a;
            } else {
            	array = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            array = new Object[]{};
        }
	}
	
	/* 二、获取栈大小 */
	public int size() {
		return size;
	}
	
	/* 三、判断栈是否为空 */
	public boolean isEmpty() {
		return size==0;
	}
	
	/* 四、入栈 */
    public void push(E e) {
    	if (size == array.length) {
    		//扩容
    		expansion();
    	}
        array[size] = e;
        size += 1;
    }
    
    /* 五、出栈 */
	@SuppressWarnings("unchecked")
	public E pop() {
    	if(isEmpty()) {
    		throw new IndexOutOfBoundsException();
    	}
    	size -= 1;
    	return (E) array[size];
    }
	
	/* 六、访问栈顶元素 */
	@SuppressWarnings("unchecked")
	public E peek() {
		if(isEmpty()) {
    		throw new IndexOutOfBoundsException();
		}
		return (E) array[size-1];
	}
    
	/* 七、将 List 转化为 Array 并返回 */
    public Object[] toArray() {
    	Object[] t = new Object[size];
    	for (int i = 0; i < t.length; i++) {
			t[i] = array[i];
		}
        return t;
    }
	
    //数组扩容（如果扩容到大于int的取值范围后怎么办？？？）
    private void expansion() {
    	Object[] t = new Object[(int) Math.ceil(size * 1.5)];
    	for (int i = 0; i < array.length; i++) {
			t[i] = array[i];
		}
    	
    	array = t;
    }

}

[yuukidesu1]

5.1.2中实现栈的方法里「基于链表实现」中的Python代码中，「pop」函数的 「num = self.peek」是不是笔误？应该改为「num = self._peek」?

[yuukidesu1]

(浏览完完整代码后)抱歉抱歉，草率了🙏

[JoneKong]

人民邮电出版社24年2月第1版，86页，即本节内的5.1.2基于数组实现的栈，python代码，is_empty函数有错误，书中的是 return self._size == 0 ，我看到线上的已经更正为 return self.size() == 0 了

[Limit1996]

C#

namespace _1.Console;

/// <summary>
/// 链表栈
/// </summary>
/// <typeparam name="T"></typeparam>
public class CustomLinkedListStack<T>
{
    private Node<T>? _head;

    public int Count
    {
        get
        {
            var count = 0;
            var node = _head;
            while (node != null)
            {
                count++;
                node = node.Next;
            }

            return count;
        }
    }

    public void Push(T value)
    {
        if (_head == null)
        {
            _head = new Node<T>(value);
            return;
        }

        var temp = _head;
        _head = new Node<T>(value);
        _head.Next = temp;
    }

    public T Peek()
    {
        if (_head == null)
            throw new NullReferenceException("栈为空");
        return _head.Value!;
    }

    public T Pop()
    {
        if (_head == null)
            throw new NullReferenceException("栈为空");
        var head = _head;
        _head = head.Next;
        return head.Value!;
    }
}

/// <summary>
/// 数组栈
/// </summary>
/// <typeparam name="T"></typeparam>
public class CustomArrayStack<T>
{
    private readonly List<T> _items = new();
    public int Count => _items.Count;

    public void Push(T value) => _items.Add(value);

    public T Peek()
    {
        if (_items.Count == 0)
            throw new NullReferenceException("栈为空");
        return _items[^1];
    }

    public T Pop()
    {
        if (_items.Count == 0)
            throw new NullReferenceException("栈为空");
        var value = _items[^1];
        _items.RemoveAt(_items.Count - 1);
        return value;
    }
}

[jiuerya7]

你这个还用了索引运算符👍

[SLL0711]

_items[^1]; 索引反向运算符，获取集合最后一项

[xiaozhuge123]

day04

[Joanna-0427]

栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和
删除元素，因此栈可以视为一种受限制的数组或链表。因此栈可以视为一种受限制的数组或链表。

[Joanna-0427]

某些语言可能没有专门提供栈类，这时我们可
以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。

[yanqingyang]

栈的特点是先进后出，基本入栈和出栈都是在栈顶处理的，文中说“
使用链表实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底”，实际上使用链表实现栈时，应该是以链表的头节点为栈顶、尾节点为栈底 或 以链表的尾节点为栈顶、头节点为栈底都是可以的吧？