You are here

Introduction

15 January, 2016 - 09:02
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/402b20ad-c01f-45f1-9743-05eadb1f710e@37.6

Stacks and queues are examples of containers with special insertion and removal behaviors and a special access behavior.

Insertion and removal in a stack must be carried out in such a way that the last data inserted is the first one to be removed. One can only retrieve and remove a data element from a stack by way of special access point called the "top". Traditionally, the insertion and removal methods for a stack are called push and pop, respectively. push inserts a data element at the top of the stack. pop removes and returns the data element at the top of the stack. A stack is used to model systems that exhibit LIFO (Last In First Out) insert/removal behavior.

Data insertion and removal in a queue must be carried out in such a way that the first one to be inserted is the first one to be removed. One can only retrieve and remove a data element from a queue by way of special access point called the "front". Traditionally, the insertion and removal methods for a queue are called enqueue and dequeue, respectively. enqueue inserts a data element at the "end" of the queue. dequeue removes and returns the data element at the front of the queue. A queue is used to model systems that exhibit FIFO (First In First Out) insertion/removal behavior. For example, one can model a movie ticket line by a queue.

We abstract the behaviors of special containers such as stacks and queues into an interface called IRAContainer specified as follows.