Conteúdo do Curso
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
Stacks
A stack data structure is a so-called LIFO (Last In, First Out) data structure. It means that the last item inserted in the stack will be the first item removed. And, of course, it is very important that we can access only the last element in a data structure exclusively when dealing with the stack.
Stack implementation
It is important to remember that a stack is an abstract data type. It means that it only defines behavior but not a concrete implementation. The stack abstract data type can be implemented either with the help of the array or linked list data structure.
Usually, in concrete implementations of the stack, two basic methods are used:
push()
- inserts an item into a stack;pop()
- removes the last inserted item from a stack.
Basic operations time complexity
Method | Array Implementation | Doubly Linked List Implementation |
---|---|---|
push() | O(1) | O(1) |
pop() | O(1) | O(1) |
Tudo estava claro?
Conteúdo do Curso
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
Stacks
A stack data structure is a so-called LIFO (Last In, First Out) data structure. It means that the last item inserted in the stack will be the first item removed. And, of course, it is very important that we can access only the last element in a data structure exclusively when dealing with the stack.
Stack implementation
It is important to remember that a stack is an abstract data type. It means that it only defines behavior but not a concrete implementation. The stack abstract data type can be implemented either with the help of the array or linked list data structure.
Usually, in concrete implementations of the stack, two basic methods are used:
push()
- inserts an item into a stack;pop()
- removes the last inserted item from a stack.
Basic operations time complexity
Method | Array Implementation | Doubly Linked List Implementation |
---|---|---|
push() | O(1) | O(1) |
pop() | O(1) | O(1) |
Tudo estava claro?