AMIT-_-PANDEY's blog

STACK vs VECTOR
By AMIT-_-PANDEY, history, 6 months ago, In English

If in a vector we can use use push_back() and pop_back() and in a stack we do push and pop from the rear end of the stack . So what is the significance of stack over a vector ? Is it size related or something else ?

  • Vote: I like it
  • +22
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

One of the major differences is you can resize the vector and access the element using indexing but you cannot access the element using indexing in stack.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    The main question is what is the significance to use stack over vectors.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Only where is more intuitive to use a Stack. It's an interface, A Stack uses a Vector internally. It's the same as a Queue in BFS for example. In reality a Queue uses a Deque, a LinkedList or a Vector internally but makes more sense using the API of a Queue (front / pop / push) for the algorithm.

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        One little thing: by default stack uses deque internally (internal container is template parameter, so you can use vector too though)

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, didn't know.

          → Reply
»
6 months ago, # |
← Rev. 6   Vote: I like it +15 Vote: I do not like it

vector guarantees insertions by "new and copy", so when there are enough elements, it will request a new space and copy everything in it, which means that some operation may reach O(n).

This is safe to amortized analysis, so it's safe in CP, but not every where accept amortized analysis. For example, you wouldn't want an AI driving your car to cause a 0.5s brake failure because of vector.

on the other hand ,stack is implemented using linked lists, which can cause some constant problems with cache miss, but it guarantees that all operations are O(1).

here's why. This feature also leads to you can make a persistent stack with O(1), but you have to use persistent segment tree to make a persistent vector in O(log n). But this is not reflected in the C++.

this answer is not generate by chatGPT. it's generate by catGPT. meow

the cat used to generate the answer
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "For example, you wouldn't want an AI driving your car to cause a 0.5s brake failure because of vector."

    Huh. Never thought about that before. Interesting.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you only need 1 stack, a fixed size vector/array can run faster than the STL stack because of the way cache works. If you needed more, with dynamic size i'd recommend stack. Be aware declaring an array of stack can be dangerous, even if they are never used. Most STL data structures have internal values and even empty they use some memory which can lead to TLE/MLE.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Stack is a container adapter which uses std::deque container by default (it can use std::vector too if you declare it like stack<T, vector>).

std::vector and std::deque allocate memory differently. std::vector allocates memory like an dynamic array in a continuous block of memory where std::deque allocates memory like double linked list in a quite scattered way(not sure what is the accurate terminology for that).

Here are some performance benchmarks you can check.

→ Reply