Please enable JavaScript.
Coggle requires JavaScript to display documents.
Stacks & Queues - Coggle Diagram
Stacks & Queues
Stacks
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.
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.
Policy: LIFO = last-in, first-out
Note that one implication of the LIFO policy is that stacks remove elements
in reverse order of their arrival.
Operations:
- void clear(Stack s);
- void push(Stack s, E it);
- E pop(Stack s);
- E topValue(Stack s);
- int length(Stack s);
-
Linked Stacks
Composite type (Stack):
- Link top; // reference to the first element
- int size; // number of elements
Algorithm: Stack create stack()
- s.top ← NULL;
- s.size ← 0;
- return s;
Algorithm: void push(Stack s, E it)
- s.top ← create link(it, s.top);
- s.size++;
Algorithm: E pop(Stack s)
- if s.top = NULL then error;
- it ← s.top.element;
- s.top ← s.top.next;
- s.size--;
- return it;
-
Array-Based Stacks
Method top acts somewhat like a current position value (because the
“current” position is always at the top of the stack), as well as indicating the number of elements currently in the stack.
The array-based stack implementation is essentially a simplified version of the
array-based list. The only important design decision to be made is which end of the array should represent the top of the stack.
Queues
Policy: FIFO = 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);
-
Linked Queues
-
Composite Type (Queue):
- Link front; Link rear; int size ; // queue size
Algorithm: Queue create queue()
- q.front ← q.rear ← create link(NULL); // header node
- q.size ← 0;
- return q;
Algorithm: void enqueue(Queue q, E it)
- q.rear.next ← create link(it, NULL);
- q.rear ← q.rear.next;
- q.size++;
Algorithm: E dequeue(Queue q)
- if q.size = 0 then error;
- it ← q.front.next.element;
- q.front.next ← q.front.next.next;
- if q.front.next = NULL then q.rear ← q.front;
- q.size--;
- return it;
Array-Based Queues
The array-based queue is somewhat tricky to implement effectively. A simple conversion of the array-based list implementation is not efficient
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). Thus, queues release their elements in order of arrival.
-