Data Structures - Stacks, Queues, Linked Lists

Stacks

In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out,or LIFO, policy. The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP.

The array has an attribute S.top that indexes the most recently inserted element. The stack consists of elements S[1…S.top], where S[1] is the element at the bottom of the stack and S[S.top] is the element at the top.

When S.top = 0, the stack contains no elements and is empty. We can test to see whether the stack is empty by query operation STACK-EMPTY. If we attempt to pop an empty stack, we say the stack underflows, which is normally an error. If S.top exceeds n, the stack overflows.

Queues

The queue has a head and a tail. When an element is enqueued, it takes its place at the tail of the queue. The queue has an attribute Q.head that indexes, or points to, its head. The attribute Q.tail indexes the next location at which a newly arriving element will be inserted into the queue.

We call the INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE; like the stack operation POP, DEQUEUE takes no element argument.

If we attempt to dequeue an element from an empty queue, the queue underflows. When Q.head = Q.tail + 1, the queue is full, and if we attempt to enqueue an element, then the queue overflows.

Linked Lists

A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Each element of a doubly linked list L is an object with an attribute key and two other pointer attributes: next and prev.

Given an element x in the list, x.next points to its successor in the linked list, and x.prev points to its predecessor. If x.prev = NIL, the element x has no predecessor and is therefore the first element, or head, of the list. If x.next = NIL, the element x has no successor and is therefore the last element, or tail, of the list. An attribute L.head points to the first element of the list. If L.head = NIL, the list is empty

If a list is singly linked, we omit the prev pointer in each element. If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list. If the list is unsorted, the elements can appear in any order. In a circular list, the prev pointer of the head of the list points to the tail, and the next pointer of the tail of the list points to the head.

Comments: