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

[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]

区别不大

[3Ajfdjsdsk2]

打开vscode转到定义在utils文件里有

[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]

[luoyaocray]

我记得是程序员会用一个下划线表示最好别更改这个参数，两个下划线表示禁止更改老子的参数（道听途说）

[Zhao-Yi-Ya]

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

[xiaohaoii]

c出栈在寻找栈顶元素的时候，就已经进行过栈是否为空的判断了

[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;
    }

}