2

I got one simple question: which kind of data structure is a stack? Is it a static or dynamic data structure? I was looking for the answer and couldn't find it, therefore I got my own "explanation" - I guess, when you can implement it either by using an array or a linked list, it can be... both?, depending on implementation? Does my reasoning make any sense?

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
Cleopatra
  • 55
  • 1
  • 7
  • Possible duplicate of [What and where are the stack and heap?](http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap) – scottb Jan 21 '16 at 00:38
  • 1
    @scottb It's not that kind of stack :) – Sergey Kalinichenko Jan 21 '16 at 00:40
  • 2
    @scottb I think the current question refers to the the usual data structure called *stack*, not the *stack* (in an operating system) vs *heap* difference. – vsoftco Jan 21 '16 at 00:40

2 Answers2

5

By definition, a static data structure has fixed size. If you can limit the size of your stack to some pre-determined number, your stack becomes a static data structure. Its size is the size of its storage, plus the size of the stack pointer or stack index indicating the current location.

A stack of an unlimited capacity is a dynamic data structure, regardless of its implementation. It could be implemented with a linked list or an array that you re-allocate upon reaching its capacity, but the size of such stack changes as you add or remove data.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • I think it's interesting to remark that e.g. C++ uses a [*std::deque*](http://en.cppreference.com/w/cpp/container/deque) by default to implement a stack, which consists of chunks of continuous blocks and hence it is a dynamic structure that guarantees amortized O(1) insertion (the reallocation happen only when exceeding the capacity of the current block). – vsoftco Jan 21 '16 at 00:45
0

Well, first of all, Stack is a data structure on its own. Stack are to be expandable which ever implementation used. Although stack can be fixed in size, maximum number of element it can contain. but often you will like to consider it as a dynamic structure that expands as the number of elements increase. Often it comes as ADT(Abstract data type) so that which ever structure(LinkedList, Array, ArrayList etc) is used to implement it, its functions and attributes are always the same

Ibukun Muyide
  • 1,294
  • 1
  • 15
  • 23