CSC 3102 Chapter : Stacks Queues Dequeues
Document Summary
All of the operations on stacks, queues, and deques are o(1) . Interface: void push(t, void pop(, t top(, int size() top and pop might throw. Implementation: using an array, using a linked list push might throw, applications, sequence reversing, parenthesis matching, function calling. Interface: void enqueue(t, void dequeue(, t front(, int size() front and dequeue might throw. Use a circular indexing: using a linked list. Use a circular singularly-linked list, or a doubly-linked list: enqueue might throw. It"s easy to implement each of these in terms of a simpler existing, more general data structure, such as a doubly-linked list: node *firstnode() node *lastnode() void remove(node *n) void insertafter(node *n, t e) void insertbefore(node *n, t e) Interface: void insertfront(t, void insertback(t, void erasefront(, void eraseback(, t front(, t back(, int size() Easily implemented atop a doubly-linked list data structure. But commonly implemented as a doubly-linked list of arrays, to great effect. Stacks and queues present fundamentally the same api.
