Introduction to the Queue and Stack data structures

INTRODUCTION

The main objective of this is small article is to introduce data structures in the computer programming space, and give an introduction and details about the queue and the stack data structures.

DATA STRUCTURES

A very simple definition of data structure is: ways of organize and store data in computers. The concept of data structures exists since computers exist, and obviously a concept which is kept over the years and implemented in the programming languages. This article will present stack and queues as abstract data models (ADT), in other words, just presenting the concepts as a mathematical or a logical data model (MyCodeSchool, 2013).

STACK

Stacks implements the LIFO concept of the last item put in the stack is the first one to be picked off the stack. A stack operates basically with three operations: PUSH, POP and STACK-EMPTY. The PUSH operation basically puts an item at the last position of the stack, the POP operation basically pick off the top of the stack. STACK-EMPTY is used to check whether the stack is empty or not (Cormen, 2009).

Real world examples: Stack of dinner plates.

Complexity: Each operation takes: O(1) time.

QUEUES

Queues implements the FIFO concept of the first item put in the queue is the first one to be picked off the queue ā€“ this operations are called ENQUEUE and DEQUEUE. A queue operates basically with two operations: ENQUEUE and DEQUEUE. The ENQUEUE operation basically puts an item at the first position of the queue, the DEQUEUE operation basically pick it off. (Cormen, 2009).

Real world examples: A queue is very similar to a line, which customers are waiting to pay a bill.

Complexity: Each operation takes: O(1) time.

USAGE OF QUEUES AND STACKS

A good point to use a queue in an implementation of an operating system, would be the processes which are waiting to be processed in order. Let’s suppose a notification system in an operating system, for the user, it would be nice to have the first notifications coming out earlier than the last ones. On the other hand, considering a stack, program thread it would be good if the last item pushed to the stack to be the first one to be popped out. ā€œWhen a program begins executing in the function main(), space is allocated on the stack for all variables declared within main(). If main() calls a function, func1(), additional storage is allocated for the variables in func1() at the top of the stack.ā€ (University of Hawai, 1993).

REFERENCES

Cormen, T.H, 2009. Introduction to Algorithms. 3rd ed. Massachusetts: The MIT Press.

Data structures: Introduction to stack – MyCodeSchool@YouTube. 2016. Data structures: Introduction to stack – YouTube. [ONLINE] Available at: https://www.youtube.com/watch?v=F1F2imiOJfk. [Accessed 07 February 2016].

University of Hawai. 1993. Programming in C. [ONLINE] Available at: http://www-ee.eng.hawaii.edu/~tep/EE160/Book/chap14/subsection2.1.1.8.html. [Accessed 07 February 16].

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s