Stacks and Queues

Stacks

* Stores a set of elements in a particular order

* Stack principle: LAST IN FIRST OUT

* = LIFO

* It means: the last element inserted is the first one to be removed

* Example

* Which is the first element to pick up?

Real life Examples

· Pile of books

· Pile of plates

· Trays are only added and removed from the top.

· The batteries in flashlight
(You can not remove the second battery unless u remove the last in)

· Pringles! Last chip to go in the can is the first one in my stomach.

More applications related to computer science

o Program execution stack

o Evaluating expressions

Primary operations: Push and Pop

* Push

· Add an element to the top of the stack

* Pop

· Remove the element at the top of the stack

Stack Interface

Template class stack

{public:

stack ( ); // default constructor

stack (const stack&) // copy constructor

~ stack ( ); // destructor

stack operator=(const stack&); // assignment operator

int size ( ) const; // returns number of elements

bool empty ( ) const; // returns true if empty

T& top ( ); // returns the top element

void push(const T&); // inserts given element on top

void pop ( ); // removes top element

Application of Stacks

* Infix to Postfix conversion

[Evaluation of Expressions]

* Infix Notation - for arithmetic places binary operators between their operands.

* E.g. x+2

* Postfix Notation - for arithmetic places binary operators after both of their operands.

* e.g. x 2+

* Prefix Notation - for arithmetic places binary operators ahead of both of their operands.

* E.g. + x 2.

Queues

* Stores a set of elements in a particular order

* Stack principle: FIRST IN FIRST OUT

* = FIFO

* It means: the first element inserted is the first one to be removed

* Example

* The first one in line is the first one to be served

Queue Applications

* Real life examples

§ Waiting in line

§ Waiting in ATM

§ Paying Bank Bills

§ Drive-thru in MCDO
(You can not get your order unless the first one go away)

§ Line at the grocery store

§ Print queue... Printers use queues for print jobs

* Applications related to Computer Science

o Threads

o Job scheduling (e.g. Round-Robin algorithm for CPU allocation)

Enqueue and Dequeue

* Primary queue operations: Enqueue and Dequeue

* Like check-out lines in a store, a queue has a front and a back.

* Enqueue – insert an element at the back of the queue

* Dequeue – remove an element from the front of the queue