Stacks
A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle.
The Stack ADT
A stack is an abstracts data type (ADT) such that an instance S supports the following two methods:
| Method | Description |
|---|---|
| S.push(e): | Add element e to the top of stack S. |
| S.pop( ): | Remove and return the top element from the stack S; an error occurs if the stack is empty. |
The following accessor methods are also defined for convenience:
| Method | Description |
|---|---|
| S.top( ): | Return a reference to the top element of stack S, without removing it; an error occurs if the stack is empty. |
| S.is_empty( ): | Return True if stack S does not contain any elements. |
| len(S): | Return the number of elements in stack S; in Python, we implement this with the special method __len__ . |
A stack S can be realized by an adaptation of a Python list L.
| Stack Method | Realization with Python list |
|---|---|
| S.push(e) | L.append(e) |
| S.pop( ) | L.pop( ) |
| S.top( ) | L[−1] |
| S.is_empty( ) | len(L) == 0 |
| len(S) | len(L) |
Queues
A queue is a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle.
The Queue ADT
The queue abstract data type (ADT) supports the following two fundamental methods for a queue Q:
| Method | Description |
|---|---|
| Q.enqueue(e): | Add element e to the back of queue Q. |
| Q.dequeue( ): | Remove and return the first element from queue Q; an error occurs if the queue is empty. |
The queue ADT also includes the following supporting methods:
| Method | Description |
|---|---|
| Q.first( ): | Return a reference to the element at the front of queue Q, without removing it; an error occurs if the queue is empty. |
| Q.is_empty( ): | Return True if queue Q does not contain any elements. |
| len(Q): | Return the number of elements in queue Q; in Python, we implement this with the special method __len__ . |
Double-Ended Queues
A double-ended queue, or deque, which is usually pronounced “deck” supports insertion and deletion at both the front and the back of the queue.
The Deque ADT
The deque abstract data type (ADT) supports the following methods for a deque D:
| Method | Description |
|---|---|
| D.add_first(e): | Add element e to the front of deque D. |
| D.add_last(e): | Add element e to the back of deque D. |
| D.delete_first( ): | Remove and return the first element from deque D; an error occurs if the deque is empty. |
| D.delete_last( ): | Remove and return the last element from deque D; an error occurs if the deque is empty. |
Additionally, the deque ADT will include the following accessors:
| Method | Description |
|---|---|
| D.first( ): | Return (but do not remove) the first element of deque D; an error occurs if the deque is empty. |
| D.last( ): | Return (but do not remove) the last element of deque D; an error occurs if the deque is empty. |
| D.is_empty( ): | Return True if deque D does not contain any elements. |
| len(D): | Return the number of elements in deque D; in Python, we implement this with the special method __len__ . |
[1] Goodrich, Michael, Roberto Tamassia, and Michael Goldwasser, Data Structures and Algorithms in Python, Hoboken, NJ: Wiley, 2013. pp. 228-254
RSLRuiz 2020