Почему это так, что мы можем использовать односвязный список для представления стека только в том случае, если ссылки между узлами ориентированы в направлении сверху (новее) до нижнего (более старого)?Одиночный список, представляющий стек
Потому что в противном случае операции, такие как pop(), будут принимать O(n) вместо O(1), а также другие. Представление стека означает, что доступ к последнему вставленному элементу является самым простым (меньше времени).
ОК, я получаю это сейчас, удаляя головку связанного списка, беру время O (1) и удаляя хвост, занимает время O (n), так как вам нужно выполнить линейный поиск, чтобы найти узел, который указывает на хвост и сделать этот узел равным нулю. Поэтому, если стек был хвостом в голову (каждый указатель указывает вверх к вершине стека), он будет принимать O (n) каждый раз, когда вы выскакиваете, а не O (1) для стека, который реализован с головы до хвоста (каждый указатель указывает на нижний стека).