Please enable JavaScript.
Coggle requires JavaScript to display documents.
M6 - Algorithms and Data Structures - Coggle Diagram
M6 - Algorithms and Data Structures
4 Lists, Stacks, and Queues
4.2 Stacks
4.2.1 Array-Based Stacks
The only important design decision to be made is which end of the array should represent the top of the stack.
One choice is to make
the top be at position 0
in the array. In terms of list functions,
all insert and remove operations would then be on the element in position 0
This implementation is
inefficient
, because now every
push or pop operation
will require that all elements currently in the stack be shifted one position in the array, for a cost of
Θ(n)
The other choice is have
the top element be at position n − 1
when there are n elements in the stack
In other words, as elements are pushed onto the stack, they are
appended to the tail of the list.
Method pop removes the tail element. In this case,
the cost for each push or pop operation is only Θ(1)
.
4.2.2 Linked Stacks
Elements are inserted and removed only from the head of the list.
The only data member is
top, a pointer to the first (top) link node of the stack.
Method push
first modifies the next field of the newly created link node to point to the top of the stack and then sets top to point to the new link node
Algorithms (linked):
Stack create stack();
4.2.3 Comparison of Array-Based and Linked Stacks
All operations for the array-based and linked stack implementations take constant time,
so from a time efficiency perspective, neither has a significant advantage.
the
total space required
: the array-based stack must declare a fixed-size array initially, and some of that space is wasted whenever the stack is not full. The linked stack can shrink and grow but requires the overhead of a link field for every element.
The stack is a list-like structure in which elements may be inserted or removed from only one end.
While this restriction makes stacks less flexible than lists, it also makes stacks both efficient (for those operations they can do) and easy to implement
Many applications require only the limited form of insert and remove operations that stacks provide
“Last-In, First-Out"
stacks remove elements in reverse order of their arrival
The accessible element of the stack is called the
top
element. Elements are not said to be inserted, they are
pushed
onto the stack.
When removed, an element is said to be
popped
from the stack.
Operations:
void clear(Stack s);
void push(Stack s, E it);
E pop(Stack s);
E topValue(Stack s);
int length(Stack s);
4.3 Queues
4.3.1 Array-Based Queues
The “
drifting queue
” problem can be solved by pretending that the array is
circular
and so allow the queue to continue directly from the highest-numbered position in the array to the lowest-numbered position
Assume that
front
stores the array index for the front element in the queue, and
rear
stores the array index for the rear element.
If both
front and rear have the same position
, then with this scheme there must be
one element in the queue.
Thus, an
empty queue
would be recognized by having
rear be one less than front
problem: the full queue is indistinguishable from the empty queue!
One obvious solution is to keep an explicit count of the number of elements in the queue, or at least a Boolean variable that indicates whether the queue is empty or not.
Another solution is to make the array be of size n + 1, and only allow n elements to be stored
4.3.2 Linked Queues
Composite Type (Queue):
Link front;
Link rear;
int size
Algorithms (linked):
Queue create queue();
4.3.3 Comparison of Array-Based and Linked Queues
All member functions for both the array-based and linked queue implementations require constant time
The space comparison issues are the same as for the equivalent stack implementations.
Unlike the array-based stack implementation, there is no convenient way to store two queues in the same array, unless items are always transferred directly from one queue to the other
the queue is a list-like structure that provides restricted access to its elements.
Queue elements may only be
inserted
at the back (called an
enqueue operation
) and
removed
from the front (called a
dequeue operation
)
queues release their elements in order of arrival
“First-In, First-Out.”
Operations:
void clear(Queue q);
void enqueue(Queue q, E it);
E dequeue(Queue q);
E frontValue(Queue q);
int length(Queue q);