Linear data structures – Lists, Stacks and Queues

Leave a comment

February 8, 2013 by Ozgur Ozden

Operating systems uses lists and queues to organize the tasks in a system. Linear dataImage structure mainly has three components as Lists, Stacks and Queues. let us investigate these components one by one:
LISTS: “is a collection whose entries are arranged sequentially” [Brookshear, 2011, P.342] First item on the list is called head and the last one is called tail. Any kind of data we can use can be considered as a list such as shopping list, arrays or playlist
Advantages of using a List:
•  No need for big amounts of data
• Can be searched linearly
• No need to sort
• Data can be added or deleted anytime, any position
STACK: is a different kind of list that entries can be loaded only from head and again unloaded/removed from the head. This can be considered as pile of papers on a desk. This system is also called as Last In First Out (LIFO)
There are many advantages of using a stack in an operating system. For example:
• Recently visited sites stored on a stack in web browsers
• Every time a new site is visited, stack is “pushed” back the other web sites stored.
• Undo is an example for Stack. It contains all the commands runned in the document so they can be recalled starting from last to first.
QUEUE: In our everyday life queue can be considered as a line of customers waiting to be served in a pizza shop or any other place.
But in computer science queue represents data blocks in a specific order.
New data can be loaded from the end of the queue and executed or extracted from the tail of the queue.  We can call it as First In First Out, FIFO.
We have different operation/methods for queue such as enqueue (add/load item from the end), dequeue (remove item from the list), isEmpty( Empty).
Properties:
1- The queue has two points that we can load and unload information namely front and end
2- load, enqueue from the tail and unload, dequeue from the head.
2- length of the queue is changeable
3- First In First Out Service.  FIFO
4- Item waiting in the queue longest accessed by the system.
5- Used mainly in OS for I/O requests, Process/Task tracking
In an operating system many tasks, procedures require a use of queue such as:

  • printing a file: İf you have a network printer attached to your computer and  and if you decided to print something out,  your file attached to a queue at the print server from the tail and printed when your file reaches to the front, head of the queue. This ensures that printer is used one at a time
  • sending  a mail: Mail sent and queued for delivery at the mail server
  • SMS message: If you have a long list cell phone numbers in my case parent’s numbers. System queues these numbers and sends with an order of FIFO.
  • accessing to a file on disk: When you transfer file from one location to another. e.g., I/O, sockets
  • CPU usage shared by queue
  • Playlists at MP3’s adds the songs to the end of the queue and play from the head of the queue
  • Network routers receive many messages to be delivered to different locations, one part of the memory in the router responsible for queuing these messages and the other part is responsible for removing these messages by simply delivering them.
  • Multiprocessing: An operating system may run more than one application at the same time this is called multiprocessing. In this case there is a queue called “ready queue” which is responsible for which programs are waiting in line for execution. When a user runs the program it is added to the tail of the queue for execution.
    Some programs are given higher priority so they have privilege among the other programs.

References:
1- Stacks and Queues [Online]. Available from: http://www.toves.org/books/data/ch07-sq/index.html (Accessed: 25 January 2013)
2- Stacks, Queues, and ADTs  [Online]. Available from: http://math.hws.edu/javanotes/c9/s3.html (Accessed: 26 January 2013)
3-  Stacks and Queues [Online]. Available from: http://introcs.cs.princeton.edu/java/lectures/43stack-2×2.pdf (Accessed: 26 January 2013)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

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

%d bloggers like this: