Головы и Хвосты Стек

Question

Push(A) 
Push(B) 
Pop 
Pop 
Push(C) 
Push(A) 
Pop 
Push(X) 

Это вызвало бы мне закончить с этим линейным списком:

X

C

Однако, как бы это выглядеть как массив? Будет ли это стек = {X, C} или stack = {C, X}?

Насколько я понимаю, это будет X, C, потому что вершина стека - это голова, а все остальное - нижняя (хвосты), поэтому в этом случае C должен быть хвостом и X головой, нас X, C. Однако, прежде чем я согласился с этим, я просто подумал, что было бы разумно получить второе мнение о ком-то, спасибо!

EDIT: Я только что вспомнил, что стеки представляют собой структуры LIFO (последний в первом), которые только что усложнили для меня вещи. Если «последний из них» первым удаляется первым, по этой логике массив будет выглядеть как C, X, не так ли? Так как X был добавлен в последний стек.

Answer 1

Одним из способов реализации было бы добавлять новые записи в конец вектора, и удалить их с конца, когда выскакивают:

template <typename T> 
class MyStack 
{ 
public: 
    void push(const T& value) { m_stack.push_back(value); } 
    void pop() { m_stack.pop_back(); } 

private: 
    vector<T> m_stack; 
}; 

Предполагая, лежащий в основе vector выглядит следующим образом: [] [] [] [] [] [] []:

Нажмите (А)

[A] [] [] [] [] [] [] 

Нажмите (В)

[A] [B] [] [] [] [] [] 

Поп

[A] [] [] [] [] [] [] 

Поп

[] [] [] [] [] [] [] 

Нажмите (С)

[C] [] [] [] [] [] [] 

Нажмите (А)

[C] [A] [] [] [] [] [] 

Поп

[C] [] [] [] [] [] [] 

Нажмите (Х)

[C] [X] [] [] [] [] [] 

Добавление и удаление от конца vector, как правило, довольно эффективным.

Answer 2

Это может быть либо. Это будет деталь реализации стека. Вы даже можете реализовать его с помощью связанного списка и вообще не иметь массив.

Answer 3

Давайте посмотрим, как выглядит ваш стек на каждом шаге, и давайте попробуем представить, как будет выглядеть массив.Для удобства, первая запись массива будет самым левым Стажер

Push(A) --> [A] 
Push(B) --> [B, A] 
Pop  --> [A] 
Pop  --> [] 
Push(C) --> [C] 
Push(A) --> [A, C] 
Pop  --> [C] 
Push(X) --> [X, C] 

Обратите внимание, что реализовать стек на массиве таким образом, является немного сложнее, так как вам нужно, чтобы переместить все предыдущие пункты уже хранятся в массив в одну позицию (вправо для каждого push и влево для каждого pop).

«Правило большого пальца», которое я использую: всегда первый элемент в стеке - это тот, который выскочит. В массиве первый элемент имеет индекс 0 (или 1, в зависимости от используемого вами языка).

---

Если вы отслеживать индекс последней записи, то все может быть проще:

Push(A) --> [A]  (lastIndex = 0) 
Push(B) --> [A, B] (lastIndex = 1) 
Pop  --> [A]  (lastIndex = 0) 
Pop  --> []  (lastIndex = -1) # Empty stack 
Push(C) --> [C]  (lastIndex = 0) 
Push(A) --> [C, A] (lastIndex = 1) 
Pop  --> [C]  (lastIndex = 0) 
Push(X) --> [C, X] (lastIndex = 1) 

Это более простой подход ... компромисс в том, что вы должны держать lastIndex хранится где-то.